《数据结构6树和二叉树D》由会员分享，可在线阅读，更多相关《数据结构6树和二叉树D（15页珍藏版）》请在金锄头文库上搜索。
1、第6章 树和二叉树（ Tree i=10, a=110, n=1113路 径：路径长度：树的路径长度：带权路径长度：树的带权路径长度 ：霍 夫 曼 树：6.5 Huffman树及其应用一、最优二叉树（霍夫曼树）由一结点到另一结点间的分支所构成路径上的分支数目从树根到每一结点的路径长度之和 。 结点到根的路径长度与结点上权的乘积debacf g树中所有叶子结点的带权路径长度之和带权路径长度WPL最小的树。ae的路径长度树长度210怎样实现Huffman编码？先要构造Huffman树！ 4(1)(1) 由给定的由给定的 n n 个权值个权值 w w0 0, , w w1 1, , w w2 2,
2、, , , w wn n-1-1 ，构造具有构造具有 n n 棵扩充二棵扩充二 叉树的叉树的森林森林F F = = T T0 0, , T T1 1, , T T2 2, , , , T Tn n-1 -1 ，其中每一棵扩充二叉树其中每一棵扩充二叉树 T Ti i 只有一个带有权值只有一个带有权值 w wi i 的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。(2)(2) 重复以下步骤重复以下步骤, , 直到直到 F F 中仅剩下一棵树为止：中仅剩下一棵树为止： 在在 F F 中中选取两棵根结点的权值最小选取两棵根结点的权值最小的扩充二叉树的扩充二叉树, , 做为左做为左 、右子树
3、构造一棵新的二叉树。置新的二叉树的、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值根结点的权值 为其左、右子树上根结点的权值之和为其左、右子树上根结点的权值之和。 在在 F F 中删去这两棵二叉树。中删去这两棵二叉树。 把新的二叉树加入把新的二叉树加入 F F。构造霍夫曼树的基本思想：构造Huffman树的步骤（即Huffman算法） ：权值大的结点用短路径，权值小的结点用长路径。权值大的结点用短路径，权值小的结点用长路径。5操作要点1：对权值的合并、删除与替换 在权值集合7,5,2,4中，总是合并当前值最小的两个权构造Huffman树的步骤：注：方框表示外结点（叶子，字符对应的权值），
4、圆框表示内结点（合并后的权值）。6操作要点2：按左0右1对Huffman树的所有分支编号 ！dain111000Huffman编码结果：d=0, i=10, a=110, n=111 WPL=1bit72bit5+3bit(2+4)=35特点2：每一码都不是另一码的前缀，绝不会错译! 称为前缀码将将 Huffman树 与 Huffman编码 挂钩特点1：不存在度为1的结点7例2（严题集6.26）：假设用于通信的电文仅由8个字母 a, b, c, d, e, f, g, h 构成，它们在电文中出现的概率分 别为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21,
5、0.10， 试为这8个字母设计哈夫曼编码。如果用07的二进制编码方案 又如何？霍夫曼编码的基本思想是：概率大的字符用短码，概率小的用 长码。由于霍夫曼树的WPL最小，说明编码所需要的比特数最 少。这种编码已广泛应用于网络通信中。解：先将概率放大100倍，以方便构造哈夫曼树。 权值集合 w=7, 19, 2, 6, 32, 3, 21, 10， 按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树 。8w4=19, 21, 28, 32为清晰起见，重新排序为: w=2, 3, 6, 7, 10, 19, 21, 322356w1=5, 6, 7, 10, 19, 21, 32 w2=7, 10
6、, 11, 19, 21, 32 w3=11, 17, 19, 21, 32111071728211940w5=28,32,403260w6=40,60w7=100100bcadegfh哈夫曼树 a7, b19, c2, d6, e32, f3, g21, h109weightparentlchildrchild 1/a7000 2/b19000 3/c20/9/00 4/d6000 5/e32000 6/f30/9/00 7/h21000 8/g10000 9/-0/5/00/2/0/3/ 10/-0000 11/-0000 12/-0000 13/-0000 14/-0000 15/-00
7、00L1-7L8-14 (32,63)L8-14 (46,95)10对应的哈夫曼编码（左0右1） ：23561110732172821194060100bcadegfh00000111111100符编码编码频频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符编码编码频频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman码的WPL2(0.19+0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61 WPL3(0.19+0.32+0.21+0
8、.07+0.06+0.10+0.02+0.03)=3 11001100000011110111101110111010101111111111010111011101000001010011100101110111二进制码二进制码11另一种结果表示 ：12二叉树的应用平衡树 排序树 判定树字典树 带权树 最优树左右子树深度差 1“左小右大” 查找判断由字符串构成的二叉树排序树路径长度带权值带权路径长度最短的树，又称 Huffman 树，用途之一是通信中的压缩编码。13例3（实验三，可选）：设字符集为26个英文字母，其出 现频度如下表所示。注：若圆满实现了此方案，平时成绩将以满分计。514811
9、56357203251频度zyxwvut t字符11611882380频度p21fq15gr47hsonmlkj字符5710332221364186频度ie edcba空格空格字符先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。要求编程实现：14提示1：霍夫曼树中各结点的结构可以定义为如下 5个分量： charweightparentlchildrchild将整个霍夫曼树的结点存储在一个数组中：HT1.n; 将结点的编码存储在HC1.n中。提示3：霍夫曼树如何构造？构造好之后又如何求得 各结点对应的霍夫曼编码？算法参见教材P147。提示2：霍夫曼树的存储结构可采用顺序存储结构：15
