并统计其叶子结点的个数。方案二：哈夫曼树的建立和编

并统计其叶子结点的个数。方案二：哈夫曼树的建立和编内容摘要：

F中。 (4) 重复 (2) 和 (3) , 直到 F 只含一棵树为止。 这棵树便是 Huffman树。 怎样证明它就是 WPL最小的最优二叉树。 参考 《 信源编码 》 Huffman树的特点：没有度为 1的结点。 15 step1： 对权值进行合并、删除与替换 —— 在权值集合 {7,5,2,4}中，总是合并 当前值最小 的两个权 具体操作步骤： a. 初始 方框表示外结点（叶子，字符） 圆框表示内结点（合并后的权值） b. 合并 {2} {4} c. 合并 {5} {6} d. 合并 {7} {11} 16 step2： 按左 “ 0”右 “ 1” 对 Huffman树的所有分支编号 d a i n 1 1 1 0 0 0 Huffman编码结果： d=0, i=10, a=110, n=111 WPL=1bit 7＋ 2bit 5+3bit(2+4)=35（小于等长码的 WPL=36） 特征：每一码不会是另一码的前缀，译码时可惟一复原 Huffman编码也称为 前缀码 —— 将 Huffman树 与 Huffman编码 挂钩 17 二、 Huffman编码 （ 1） 由于 Huffman树的 WPL最小， 说明编码所需要的 比特数最少。 （ 4） Huffman编码时是从叶子走到根；而译码时又要从根走到叶子，因此每个结点需要增开 双亲 指针分量（连同结点 权值共要开 5个分量） （ 5） 用计算机实现时，顺序和链式两种存储结构都要用到。 分析 Huffman树和编码的特点： 霍夫曼 编码的基本思想是 —— 出现概率大的信息用短码，概率小的用长码 ,最小冗余 这种编码已广泛应用于网络通信中。 （ 2） Huffman树 肯定没有度为 1的结点； （ 3） 一棵有 n 0个叶子结点的 Huffman树，共有 2n01个结点； （因为 n=n0+n1+n2=2n01) 18 如何编程实现 Huffman编码。 建议 1： Huffman树中结点的结构可设计成 5分量形式： char weight parent lchild rchild 将整个 Huffman树的 结点 存储在一个数组 HT[1..n..m]中。 各叶子结点的 编码 存储在另一 “ 复合 ” 数组 HC[1..n]中。 请参见教材 P149图 （ a)和（ c) 建议 2： Huffman树的 存储结构可采用 顺序存储 结构： (1)教材 P147～ 149内容； (2)严蔚敏 “ 数据结构 ” 演示程序 ； (3)习题集 P149 实习 ； (4)自测卷第 6章上机方案二的源程序。 可参考： 19 typedef struct{ unsigned int weight； //权值分量（可放大取整） unsigned int parent， lchild， rchild； //双亲和孩子分量 }HTNode， *HuffmanTree； //用动态数组存储 Huffman树 typedef char**HuffmanCode； //动态数组存储 Huffman编码表 Huffman树和 Huffman树编码的存储表示： 0 0 0 r 0 9 2 0 0 19 0 0 7 l p w 3 2 1 双亲 *HuffmanTree或 HT向量 HT[3].parent=9 指针型指针 20 如何编程实现 Huffman编码。 参见教材 P147 先构造 Huffma。