c14-树第四讲

1、1执行校长李 伟赫夫曼树及其应用赫夫曼树及其应用数据结构数据结构( (第十四讲第十四讲 ) )2课程回顾课程回顾n 树的存储结构有哪些？各有什么优缺点？树的存储结构有哪些？各有什么优缺点？n 如何实现森林与二叉树的转换？如何实现森林与二叉树的转换？n 怎样遍历森林怎样遍历森林?3本讲目录本讲目录n 赫夫曼树赫夫曼树n 赫夫曼编码赫夫曼编码 基本概念基本概念 构造赫夫曼树构造赫夫曼树4本讲重点、难点本讲重点、难点n 重点重点p赫夫曼树n 难点难点p赫夫曼编码5本讲目录本讲目录n 赫夫曼树赫夫曼树n 赫夫曼编码赫夫曼编码 相关概念相关概念 构造赫夫曼树构造赫夫曼树 相关概念相关概念 赫夫曼编码赫夫

2、曼编码6赫夫曼树赫夫曼树n 赫夫曼树（最优二叉树）赫夫曼树（最优二叉树）p相关概念路径：连接从一个结点到另一个结点之间的分支路径长度：连接两结点的路径上的分支数树的路径长度：根结点到各结点的路径长度之和带权路径长度：结点到根结点的路径长度与结点上权 值的乘积树的带权路径长度：树中所有叶子结点的带权路径长 度之和记作：WPL=wklk最优二叉树：相同条件下，树的带权路径长度最小的 二叉树7n 示例示例WPL=72+52+22+42=36WPL= 71+52+23+43 =35754225477542WPL=73+53+21+42=46最优二叉树8n赫夫曼树的应用赫夫曼树的应用p在解决某些判定问题

3、时，利用赫夫曼树可以得到最佳判定算法 p145图6.23p用于通讯和数据传送时的赫夫曼编码9n 构造赫夫曼树构造赫夫曼树p由给定的n个权值w1,w2,wn，构造具有n棵二叉树的森林F = T1,T2,Tn，其中每一棵二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。p重复以下步骤, 直到F中仅剩下一棵树为止：u在F中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。u在F中删去这两棵二叉树。u把新的二叉树加入F。10n 赫夫曼树的构造过程赫夫曼树的构造过程 P146 图图6.2411n 示例示例: : 已

4、知权值已知权值 W= 5, 6, 2, 9, 7 W= 5, 6, 2, 9, 7 9562752796767913527527169671329527169671312n 赫夫曼编码赫夫曼编码p哈夫曼编码是哈夫曼树在电讯通信中的应用之一。p通讯中常需要将文字转换成二进制字符串电文进行传送。 文字转换为电文，称为编码。p收到电文后要将电文转换成原来的文字，电文转换为文字，称为译码。p在电报通信中，电文是以二进制的0，1序列传送的。在发送端需要将电文中的字符转换成0，1序列（编码）发送，在接收端又需要把接收到的0，1序列还原成相应的字符序列（译码）。13n 相关概念相关概念p等长编码 最简单的二

5、进制编码方式是等长编码。假定需传送的电文最简单的二进制编码方式是等长编码。假定需传送的电文是是ABACCDAABACCDA ，在电文中仅使用在电文中仅使用A A，B B，C C，D4D4种字符，可依次对种字符，可依次对其编码为：其编码为：0000，0101，1010，1111。上述需发送的的电文是。上述需发送的的电文是“00010010101100”。译码员可按两位一组进行译码，恢复。译码员可按两位一组进行译码，恢复原来的电文。原来的电文。 译码时，只需每译码时，只需每2位一译即可。位一译即可。特点特点：等长等频率编码，译码容易，但电文不一定最短：等长等频率编码，译码容易，但电文不一定最短。

6、A B C D00 01 10 11编码方案编码方案114p不等长编码 使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。 需发送的电文为 “000011010” 接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。 A B C D0 00 1 01编编码方案码方案2：15p前缀编码u任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。u利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。 则上述文字的电文为“

7、0110010101110” 共13位。 A B C D0 110 10 111编码方案编码方案3：16n 赫夫曼编码赫夫曼编码 设有n种字符，每种字符出现的次数为Wi , 其编码长度为Li (i=1,2,n)， 则整个电文总长度为 Wi Li ， 要得到最短的电文，即使得 Wi Li最小。 也就是以字符出现的次数为权值，构造一棵Huffman树，并规定左分支编码位0，右分支编码为1，则字符的编码就是从根到该字符所在的叶结点的路径上的分支编号序列。 用构造Huffman树编出来的码，称为Huffman编码。17n 示例：示例：设给出一段报文：CAST CAST SAT AT A TASAp字符

8、集合是 C, A, S, T ，各个字符出现的频度(次数)是 W 2, 7, 4, 5 。p以它们为各叶结点上的权值，建立赫夫曼树。p左分支赋 0，右分支赋 1，得赫夫曼编码(变长编码)。p A : 0 T : 10 C : 110 S : 111p 赫夫曼编码是一种无前缀的编码。解码时不会混淆。18n 赫夫曼树和赫夫曼编码的存储表示赫夫曼树和赫夫曼编码的存储表示typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; / / 动态分配数组存储赫夫曼树/ / typedef char *HuffmanCode; / / 动态分配数组存储赫夫曼编码表/ /n 赫夫曼编码的算法实现（见赫夫曼编码的算