1、1,赫夫曼树及其应用,路径从一个结点到另一个结点的分支构成路径长度路径上的分支的个数树的路径长度从树根到每一个结点的路径长度之和,2,赫夫曼树及其应用,以下我们只讨论二叉树问题：树的路径长度最短的是哪一种？完全二叉树,3,赫夫曼树及其应用,权(weight)给结点赋予一定的数值结点的带权路径长度从树根到该节点的路径长度该结点的权树的带权路径长度Weighted Path Length所有叶结点的带权路径长度之和WPL =,4,赫夫曼树及其应用,例,5,赫夫曼树及其应用,最优二叉树又称赫夫曼树(Huffman)有n个权值w1,w2,.,wn构造一棵有n个叶结点的二叉树每个叶结点的权值为wi其中W
2、PL最小的那一棵称作最优二叉树，即赫夫曼树最优又能怎样？,6,赫夫曼树及其应用,例一个判断成绩等级的程序if(a 60) b = “不及格”else if(a 70) b = “及格” else if(a 80) b = “中等” else if(a 90) b = “良好” else b = “优秀”一个a最多要经过4次比较才能得出b我们当然希望比较的总次数最小,7,假设有如下统计数据原判定树为：,8,若一共有10000个输入数据则总共的比较次数= 500*1 + 1500*2 + 4000*3 + 3000*4 + 1000*4 = 31500,9,构造一棵赫夫曼树有5个叶结点，权值分别为
3、：0.05, 0.15, 0.4, 0.3, 0.1,10,根据这棵赫夫曼树导出新的判定树：总的比较次数= 500*3 + 1500*3 + 4000*2 + 3000*2 + 1000*2= 22000,11,赫夫曼树及其应用,赫夫曼树的构造算法(1)根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树只含一个带权的根结点，其左右子树均空(2)在F中选取两棵根结点的权值最小的树作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树根结点的权值之和(3)在F中删除这两棵二叉树，同时将新得到的二叉树加入F(4)重复(2)和(3)，直到F
4、只含一棵二叉树,12,赫夫曼树及其应用,例：设结点a,b,c,d的权值分别为7,5,2,4，试构造赫夫曼树(1)F = (2)F = ,13,(3)F = (4)F = ,14,赫夫曼树及其应用,理解为什么赫夫曼树的带权路径长度最小？它把权值小的结点放在底层权值大的结点放在上层,15,赫夫曼树的应用赫夫曼编码,例某系统在通信联络中只可能出现八种字符(A,B,C,D,E,F,G,H)，其使用概率分别为0.05、0.29、0.07、0.08、0.14、0.23、0.03、0.11，如何设计这些字符的二进制编码，以使通信中总码长尽可能短？方案一：固定长度编码8个字符，只需要3位二进制数就能表示比如0
5、00代表A，001代表B，.111代表H这样平均每个字符用3位二进制数表示,16,赫夫曼树的应用赫夫曼编码,方案二：赫夫曼编码平均每个字符的编码长度= 4*0.05 + 2*0.29 + 4*0.07 + 4*0.08 + 3*0.14 + 2*0.23 + 4*0.03 + 3*0.11= 2.71,17,赫夫曼树的应用赫夫曼编码,赫夫曼编码的方法以字符出现频率为权值，构造赫夫曼树左分支表示0，右分支表示1，把从根到叶子的路径上所有分支构成的0,1作为叶子的二进制编码，即为赫夫曼编码比如A：0110B：10C：1110.,18,赫夫曼树的应用赫夫曼编码,【数据结构】typedef struc
6、tunsigned weight;unsigned p;unsigned lc;unsigned rc;HTNode,*HuffmanTree;typedef char * *HuffmanCode;,19,赫夫曼树的应用赫夫曼编码,15,14,13,12,11,10,9,0,0,0,11,8,0,0,0,3,7,0,0,0,23,6,0,0,0,14,5,0,0,0,8,4,0,0,0,7,3,0,0,0,29,2,0,0,0,5,1,0,rc,lc,p,weight,HT,为赫夫曼树的存储开辟空间，含 n 个叶子结点的赫夫曼树共2n-1 个结点；生成 n 个叶子结点，使它们的权值为给定的
7、n 个权值，双亲和左右孩子均为0 ；,20,赫夫曼树的应用赫夫曼编码,15,14,13,12,11,10,7,1,0,8,9,0,0,0,11,8,0,0,9,3,7,0,0,0,23,6,0,0,0,14,5,0,0,0,8,4,0,0,0,7,3,0,0,0,29,2,0,0,9,5,1,0,rc,lc,p,weight,HT,在双亲为的结点中选两个权值最小的，生成以这两个结点为左、右孩子的分支结点。重复，直至生成 n-1 个分支结点。,21,赫夫曼树的应用赫夫曼编码,15,14,13,12,11,4,3,0,15,10,7,1,0,8,9,0,0,0,11,8,0,0,9,3,7,0,0
8、,0,23,6,0,0,0,14,5,0,0,10,8,4,0,0,10,7,3,0,0,0,29,2,0,0,9,5,1,0,rc,lc,p,weight,HT,在双亲为的结点中选两个权值最小的，生成以这两个结点为左、右孩子的分支结点。重复，直至生成 n-1 个分支结点。,22,赫夫曼树的应用赫夫曼编码,求出编码 对赫夫曼树中的每个叶子结点，求从根到它的路径： 开辟 n 个存储空间，用以保存分别指向 n 个编码串的指针变量； 开辟空间，用以暂存当前所求编码串 对每个叶子结点，从该结点开始向根逆向求编码。,23,12,2,15,58,14,6,11,15,42,13,10,5,14,29,12,8,9,13,19,11,4,3,12,15,10,1,7,11,8,9,0,0,11,11,8,0,0,9,3,7,0,0,13,23,6,0,0,12,14,5,0,0,10,8,4,0,0,10,7,3,0,0,14,29,2,0,0,9,5,1,0,rc,lc,p,weight,HT,HC,7,6,5,4,3,2,1,0,0,0,0,1,0,0,0,0,1,0,cd,start,3,14,13,0,100,15,
