6.6 Huffman树 基本概念 构造 编码 ,1. 基本概念 路径:从一个结点到另一个结点之间的分支. 路径长度:路径上分支数目. 结点的路径长度:从根结点到该结点的路径长度. 树的路径长度:树中每个结点的路径长度之和. 完全二叉树这种长度最短的二叉树. 结点的带权路径长度:该结点的路径长度*结点的权值 树的带权路径长度:树中所有叶子结点的带权路径长度之和.记作:WPL=wklk 例如 最优二叉树：在所有含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=wklk =7*2+5*2+2*3 +4*3+9*2 =60,WPL2=wklk =7*4+9*4+5*3 +4*2+2*1 =89,在解决某些判定问题时,利用Huffman树可得 到最佳判定算法 例如,某厂生产螺钉,要求直径为d,误差.现测量某螺钉直径,方法与标准的比较,判定树?,d,d+ ,=d, d- ,5%,10%,50%,25%,10%,WPL=5%*3+10%*3+50%*2+25%*2+10%*2=?,概率最大的最靠近根判断,2. Huffman树的构造(自底向上),A,7,D,5,E,9,F2=,F3=,W=7,2,4,5,9,接上页:,F4=,F5=,根的权值为27 WPL=7*2+2*3+4*3+5*2+9*2=60,Huffman树形态不唯一!,构造过程(Huffman算法) (1) n个权值构成n棵独立二叉树的森林F=T1,Tn (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,(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编码,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树概念,构造和编码,