辐射4 火箭筒有双弹吗:哈夫曼树

     1.哈夫曼树概述    哈夫曼树（Huffman Tree），又称最优二叉树，是带权路径长度最短的二叉树。在实际应用中，路径长度是一个重要概念，特别是在涉及算法分析和数据编码中。因此，我们首先讨论路径长度及相关概念。（1）在许多应用中，常常将树中的结点赋上一个有着某种意义的树值，称此树值为该结点的权。从树根结点到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度。树中所有叶子结点的带权路径长度之和称为该树的带权路径长度，通常记为：WPL。（2）在n个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树（或最优二叉树）。  2.哈夫曼树的构造算法    假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为： 　　(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)； 　　(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； 　　(3)从森林中删除选取的两棵树，并将新树加入森林； 　　(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。为了实现构造哈夫曼树的算法，设计哈夫曼树中每个结点类型如下：typedef struct{   char data;    //结点值   double weight;//权重   int parent;   //双亲结点   int lchild;   //左孩子结点   int rchild;   //右孩子结点  }HTNode;构造哈夫曼树的算法如下：  void CreateHT(HTNode ht[],int n)
{
 int i,k,lnode,rnode;
 int min1,min2;
 for(i=0;i<2*n-1;i++)  //所有结点的相关域置为-1
  ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
 for(i=n;i<2*n-1;i++)   //构造哈夫曼树
 {
  min1=min2=32767;      //lnode和rnode为最小权重的两个结点位置
  lnode=rnode=-1;
  for(k=0;k<=i-1;k++)
   if(ht[k].parent==-1)   //在ht[]中找权值最小的两个结点
   {
    if(ht[k].weight    {
     min2=min1;
     rnode=lnode;
     min1=ht[k].weight;
     lnode=k;
    }
    else if(ht[k].weight    {
     min2=ht[k].weight;
     rnode=k;
    }
   }
   ht[lnode].parent=i;
   ht[rnode].parent=i;
   ht[i].weight=ht[lnode].weight+ht[rnode].weight; 
   ht[i].lchild=lnode;          //ht[i]作为双亲结点
   ht[i].rchild=rnode;
 }
}