6.6 Huffman树• 基本概念 • 构造 • 编码 哈夫曼树总结习题(2学时) 1. 基本概念• 路径:从一个结点到另一个结点之间的分支.• 路径长度:路径上分支数目.• 结点的路径长度:从根结点到该结点的路径长度.• 树的路径长度:树中每个结点的路径长度之和. 完全二叉树这种长度最短的二叉树.• 结点的带权路径长度:该结点的路径长度*结点的权值• 树的带权路径长度:树中所有叶子结点的带权路径长度之和.记作:WPL=∑wklk 例如• 最优二叉树：在所有含n个叶子结点、并带相同权值的二叉树中，必 存在WPL最小的二叉树.又叫Huffman树哈夫曼树总结习题(2学时) W={7，2，4，5，9}AEDBCBCDAE7249572459WPL1=∑wklk =7*2+5*2+2*3 +4*3+9*2 =60WPL2=∑wklk =7*4+9*4+5*3 +4*2+2*1 =89哈夫曼树总结习题(2学时) 在解决某些判定问题时,利用Huffman树可得到最佳判定算法 例如,某厂生产螺钉,要求直径为d,误差σ.现测量某螺钉直径,方法与标准的比较,判定树?d- σ dd+ σ5%10%50%25%10%>d>d>d+ σ=d=d> d- σ5%10%50%25%10%WPL=5%*3+10%*3+50%*2+25%*2+10%*2=? 概率最大的最靠近根判断哈夫曼树总结习题(2学时) 2. Huffman树的构造(自底向上)A 7B 2C 4D 5E 9F1=A 7B 2C 4D 5E 9F2=B 2C 46A 7D 5E 9F3=B 2C 46W={7,2,4,5,9}D 5B 2C 4611哈夫曼树总结习题(2学时) 接上页:A 7E 9F4=D 5B 2C 4611A 7E 916F5=D 5B 2C 4611A 7E 916AEDBC724956111627根的权值为27WPL=7*2+2*3+4*3+5*2+9*2=60Huffman树形态不唯一!哈夫曼树总结习题(2学时) 构造过程(Huffman算法) (1) n个权值构成n棵独立二叉树的森林F={T1,…Tn} (2)在森林中选出两棵根权值最小的二叉树作为左右子树,构造二叉树,根权值为左右子树的和 (3) 在F中删除这两棵,新构成的添加到F中 (4)重复(2)和(3),直到F中含一棵二叉树为止.哈夫曼树总结习题(2学时) 两个结论: (1) 在Huffman树中没有度为1的结点. (2) 一棵有n个叶子结点的Huffman树共有2n-1个结点.证明? 设总结点数为m个,叶子n个,度为1的n1个,度为2的n2个m=n+n1+n2由性质3 n=n2+1 所以 n2=n-1m=n+n1+n2 =n+n1+n-1 =2n+n1-1有(1)得 n1=0所以 m=2n+0-1=2n-1 哈夫曼树总结习题(2学时) 3. Huffman编码 (1) 等长编码 (2) 不等长编码:出现多的字符采用短码,总长短了! 但出现二义性! (3) 前缀编码:一个字符的编码都不是另一个字符的编码的前缀.A B C D00 01 10 11两位一分进行译码A B C D0 00 1 11用二叉树实现:左分支0;右分支1A: 00B: 01C: 1CBA0110哈夫曼树总结习题(2学时) (4) Huffman编码:设计Huffman树而得到的编码. 例如例如:有有8种字符种字符,概率如下概率如下: {0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11} 解解:同时扩大同时扩大100倍倍,得权值集合得权值集合: {5，，29，，7，，8，，14，，23，，3，，11}设计设计HuffmanHuffman编码编码5387815961119142923422954WPL=0.23*2+0.11*3+……HuffmanHuffman编码编码0.05: 0110 0.29: 100.07: 1110 0.08: 11110.14: 110 0.23: 000.03: 0111 0.11: 010哈夫曼树总结习题(2学时) 作业:哈夫曼树总结习题(2学时) 本章小结1. 掌握树的定义,表示形式和术语(二叉树通用) 掌握树的存储结构(孩子-兄弟表示) 掌握树与二叉树的转换 了解树的ADT定义与树和森林遍历2. 掌握二叉树的ADT定义,特点,结点的形态,性质,存储结构(二叉链表) 掌握二叉树的遍历,线索的方法 掌握遍历算法的应用 掌握二叉树与树和森林的转换 掌握Huffman树概念,构造和编码哈夫曼树总结习题(2学时) 。