资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,6.6 Huffman,树,基本概念,构造,编码,1.,基本概念,路径,:,从一个结点到另一个结点之间的分支,.,路径长度,:,路径上分支数目,.,结点的路径长度,:,从,根结点,到该结点的路径长度,.,树的路径长度,:,树中,每个结点,的路径长度之和,.,完全二叉树,这种长度,最短,的二叉树,.,结点的带权路径长度,:,该结点的路径长度,*,结点的权值,树的带权路径长度,:,树中所有叶子结点的带权路径长度之和,.,记作,:WPL=,w,k,l,k,例如,最优二叉树：,在所有含,n,个叶子结点、并带相同权值的二叉树中，必 存在,WPL,最小的二叉树,.,又叫,Huffman,树,W=7,，,2,，,4,，,5,，,9,A,E,D,B,C,B,C,D,A,E,7,2,4,9,5,7,2,4,5,9,WPL1=,w,k,l,k,=7*2+5*2+2*3,+4*3+9*2,=60,WPL2=,w,k,l,k,=7*4+9*4+5*3,+4*2+2*1,=89,在解决某些判定问题时,利用,Huffman,树可得,到最佳判定算法,例如,某厂生产螺钉,要求直径为,d,误差,.,现测量某螺钉直径,方法与标准的,比较,判定树,?,d-,d,d+,5%,10%,50%,25%,10%,d,d+,=d,d-,5%,10%,50%,25%,10%,WPL=5%*3+10%*3+50%*2+25%*2+10%*2=,?,概率最大的最靠近,根,判断,2. Huffman,树的构造,(,自底向上,),A,7,B,2,C,4,D,5,E,9,F1=,A,7,B,2,C,4,D,5,E,9,F2=,B,2,C,4,6,A,7,D,5,E,9,F3=,B,2,C,4,6,W=7,2,4,5,9,D,5,B,2,C,4,6,11,接上页,:,A,7,E,9,F4=,D,5,B,2,C,4,6,11,A,7,E,9,16,F5=,D,5,B,2,C,4,6,11,A,7,E,9,16,A,E,D,B,C,7,2,4,9,5,6,11,16,27,根的权值为,27,WPL=7*2+2*3+4*3+5*2+9*2=60,Huffman,树形态不唯一,!,构造过程,(Huffman,算法,),(1) n,个权值构成,n,棵独立二叉树的森林,F=T,1,T,n,(2),在森林中选出,两棵根权值最小,的二叉树作为左右子树,构造,二叉树,根权值为左右子树的和,(3),在,F,中,删除这两棵,新构成的添加到,F,中,(4),重复,(2),和,(3),直到,F,中含,一棵,二叉树为止,.,两个结论,:,(1),在,Huffman,树中没有度为,1,的结点,.,(2),一棵有,n,个叶子结点的,Huffman,树共有,2n-1,个结点,.,证明,?,设总结点数为,m,个,叶子,n,个,度为,1,的,n1,个,度为,2,的,n2,个,m=n+n1+n2,由性质,3 n=n2+1,所以,n2=n-1,m=n+n1+,n2,=n+n1+,n-1,=2n+n1-1,有,(1),得,n1=0,所以,m=2n+0-1=2n-1,3. Huffman,编码,(1),等长编码,(2),不等长编码,:,出现多的字符采用短码,总长短了,!,但出现二义性,!,(3),前缀编码,:,一个字符的编码都不是另一个字符的编码的前缀,.,A B C D,00 01 10 11,两位一分进行译码,A B C D,0 00 1 11,用二叉树实现,:,左分支,0;,右分支,1,A: 00,B: 01,C: 1,C,B,A,0,1,1,0,(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,设计,Huffman,编码,5,3,8,7,8,15,96,11,19,14,29,23,42,29,54,WPL=0.23*2+0.11*3+,Huffman,编码,0.05: 0110 0.29: 10,0.07: 1110 0.08: 1111,0.14: 110 0.23: 00,0.03: 0111 0.11: 010,作业,:,本章小结,1.,掌握树的定义,表示形式和术语,(,二叉树通用,),掌握树的存储结构,(,孩子,-,兄弟表示,),掌握树与二叉树的转换,了解树的,ADT,定义与树和森林遍历,2.,掌握二叉树的,ADT,定义,特点,结点的形态,性质,存储结构,(,二叉链表,),掌握二叉树的遍历,线索的方法,掌握遍历算法的应用,掌握二叉树与树和森林的转换,掌握,Huffman,树概念,构造和编码,
展开阅读全文