算法 6.18.txt

数据结构各种算法原代码及图形示例

算法 6.18
void CreateHuffmanTree(HuffmanTree &HT,  int *w,  int n) {
      // w存放n个权值(均>0)，构造赫夫曼树HT
      if (n<=1)  return;
      m = 2 * n - 1;
      HT.HTree = new HTNode[m];              // 为赫夫曼树分配一组顺序空间
      for (p=HT.Tree, i=1; i<=n; ++i, ++p, ++w)  *p = { *w, -1, -1 }; 
                    // n个带权结点形成初始化的森林，每个结点的左、右孩子为空
      for ( ; i<=m; ++i, ++p)  *p = { 0, -1, -1 };         // 对尚未使用的结点赋初值
      for (i=n; i<m; ++i) {                 // 建赫夫曼树
        Select(HT.Htree, i-1, s1, s2);
                                            // 在HT.Htree[0..i-1]当前可选的结点中选择权值
                                            // 最小的两个结点，其序号分别为s1和s2。
        HT.Htree [i].lchild = s1;  HT.Htree[i].rchild = s2;
        HT.Htree[i].weight = HT.Htree[s1].weight + HT.Htree[s2].weight;
                                            // 取左、右子树根结点权值之和
      }
      HT.root = m-1;
} // CreatHuffmanTree