数据结构哈弗曼树.doc

6.7 哈夫曼树一、Huffman树 二、Huffman编码 6.7.1 Huffman树（最优二叉树）若干术语：路 径：由一结点到另一结点间的分支所构成。路径长度：路径上的分支数目。 例如：ae的路径长度2二叉树的路径长度：从二叉树根到所有叶子结点的路径长度之和。树路径长度8二叉树的带权路径长度：从二叉树根结点到所有叶子结点的路径长度与相应叶子结点权值的乘积之和（WPL）即树中所有叶子结点的带权路径长度之和 Huffman树：带权路径长度最小的树。Huffman常译为哈夫曼、赫夫曼、霍夫曼等树的带权路径长度如何计算？ WPL = wklk 构造Huffman树的基本思想：权值大的结点用短路径，权值小的结点用长路径。构造Huffman树的步骤（即Huffman算法）：(1) 由给定的 n 个权值 w1, w2, , wn 构造n棵二叉树的集合F = T1, T2, , Tn （即森林） ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。(2) 在F 中选取两棵根结点权值最小和次小的树分别做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。(3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。(4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。具体操作步骤：对权值进行合并、删除与替换在权值集合7,5,2,4中，总是合并当前值最小的两个权具体操作步骤：对权值进行合并、删除与替换在权值集合7,5,2,4中，总是合并当前值最小的两个权 Huffman树特点：肯定没有度为1的结点；一棵有n 0个叶子结点的Huffman树，共有2n0-1个结点；讨论：Huffman树有什么用？例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4， 怎样编码才能使它们组成的报文在网络中传得最快？法1：等长编码 令d=00，i=01，a=10，n=11，则：WPL12bit(7524）36法2：不等长编码 令d=0;i=10,a=110,n=111，则：WPL2=1bit72bit5+3bit(2+4)=356.7.2 哈夫曼编码问题 哈夫曼树可用于构造代码总长度最短的编码方案。具体构造方法如下： 设需要编码的字符集合为d1,d2,dn，各个字符在电文中出现的次数集合为w1,w2,wn，以d1,d2,dn作为叶结点，以w1,w2,wn作为各叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码称之为哈夫曼编码。明确：要实现哈夫曼编码，就要先构造哈夫曼树按左“0”右“1” 对哈夫曼树的所有分支编号 在 哈夫曼树的基础上构造哈夫曼编码 哈夫曼编码结果：d=0, i=10, a=110, n=111WPL=1bit72bit5+3bit(2+4)=35（小于等长码的WPL=36）在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的惟一性。例：若字符a的编码为01，b的编码为010， c的编码为10对于代码串01010，在译码时无法判定是将前两位码01译成字符a还是将前三位码010译为字符b。在哈夫曼树中，由于每个字符结点都是叶子结点，而叶子结点不可能在根结点到其他叶子结点的路径上，所以任何一个字符的哈夫曼树编码不可能是另一个字符的哈夫曼编码的前缀。练习：假设用于通信的电文仅由5个字母A，B，C，D，E组成，字母在电文中出现的次数分别为2，4，5，7，8。试为这5个字母设计哈夫曼编码。A：010 B：011 C：00 D：10 E：116.8 树与二叉树的转换 讨论1：树如何转为二叉树？转换步骤：step1: 将树中兄弟结点之间加一连线; step2: 保留结点的最左孩子连线，删除其它孩子连线；step3: 整理保留和添加的连线。讨论3：森林如何转为二叉树？即F=T1, T2, ,Tm B=root, LB, RB法一： 各森林先各自转为二叉树； 依次连到前一个二叉树的右子树上。法二：森林直接变兄弟，再转为二叉树法一和法二得到的二叉树是完全相同的、惟一的。森林转二叉树举例：（用法一，各森林先转二叉树，在连接成一棵二叉树）森林转二叉树举例：（用法二，森林直接变兄弟，再转为二叉树）讨论4：二叉树如何还原为森林？即B=root, LB, RB F=T1, T2, ,Tm要点：把最右边的子树变为森林，其余右子树变为兄弟 6.9 树的遍历树的遍历 深度优先遍历（先根、后根） 树没有中序遍历（因子树不分左右） 先根遍历 访问根结点； 按照从左到右依次先根遍历根结点的每棵子树。 后根遍历 按照从左到右依次后根遍历根结点的每棵子树； 访问根结点。 先根序列：a b c d e 后根序列：b d c e a讨论：树若采用“先转换，后遍历”方式，结果是否一样？ 前序遍历：a b c d e 中序遍历：b d c e a 后序遍历：d e c b a 树的先根序列：a b c d e树的后根序列：b d c e a结论：1. 树的先根遍历与二叉树的前序遍历相同； 2. 树的后根遍历相当于二叉树的中序遍历；3. 树没有中序遍历，因为子树无左右之分。孩子兄弟 先根遍历 后根遍历 本 章 小 结存