构造哈夫曼树.txt

数据结构C实现对二叉树的操作

#define MAX 100
typedef  struct
{  int data;
   int pa,lc,rc;
}JD;

void huffman(int n,int w[],JD t[])    // t是存储结点的数组，n是叶子结点数，W是权值（即叶子）数组
{  int i,j,k,x1,x2,m1,m2;
  
   for(i=1;i<(2*n);i++)    //一棵有n个叶子结点的Huffman树有2n-1个结点
   {  t[i].pa=t[i].lc=t[i].rc=0;  //清零
      if (i<=n)
         t[i].data=w[i];
      else
         t[i].data=0;  // 将n个权值（即叶子）放入数组t
   } //准备工作结束

   for(i=1;i<n;i++) // 数组t 在准备工作结束后，下剩n-1个空位置来存放合成的新结点
   {  m1=m2=MAX;
      x1=x2=0;  //赋初值
      for(j=1;j<(n+i);j++)
      {  if( (t[j].data<m1) && ( t[j].pa==0) )
         {  m2=m1;  x2=x1;
            m1=t[j].data;  x1=j;  //当前最小权值放在m1中
         }
         else if( (t[j].data<m2) && ( t[j].pa==0) )  //当前次小权值放在m2中
         {  m2=t[j].data; x2=j; }
      } //查找一对未被处理过的最小权值
      k=n+i; //合成的新结点在数组中的下标
      t[x1].pa=t[x2].pa=k; 
      t[k].data=m1+m2;  //为合成的新结点赋值
      t[k].lc=x1;
      t[k].rc=x2;
   }//继续查找下一对未被处理过的最小权值
}