哈夫曼树及应用.docx

《哈夫曼树及应用.docx》由会员分享，可在线阅读，更多相关《哈夫曼树及应用.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2. 9. 1哈夫曼树及应用哈夫曼树又称最优树（二叉树），是一类带权路径最短的树。构造这种树的算法最早是 由哈夫曼（Huffman） 1952年提出，这种树在信息检索中很有用。结点之间的路径长度：从一个结点到另一个结点之间的分支数目。树的路径长度：从树的根到树中每一个结点的路径长度之和。(3) PL=0+l+2+2+3+4+5=17(3) PL=0+l+2+2+3+4+5=17(3) PL=0+l+2+2+3+4+5=17(b) PL=0+1+1+2*4+3=13结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：WP

2、L为最小的二叉树就称作最优二叉树或哈夫曼树。WPL=7*3+5*3+2*1+4*2=46WPL=7+2+5*2+2*2+4+2=36WPL=7*1+5*2+2*3+4*3=35完全二叉树不一定是最优二叉树。哈夫曼树的构造：（1）根据给定的。个权值稹小，川构造11棵二叉树的集合F二T,T,.，T ,其中Ti中只有一个权值为W1的根结点，左右子树为空；（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且 置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树;(4)例1：(4)例1：重复（2）和（3）直到F中

3、只含一棵树为止，这棵树就是哈夫曼树。7524CD0(a)例2： O 0,4030.10,10.40.30.10.10,020.08(a )初始集合F（c） C和D合并（切日和尸合并（e） B与E、F、C、D的合并0.40.3E和F与C和D合并图12.16哈夫曼树的构造过程结点的存储结构:1childdata 结点值weight 权指rchildparent构造哈夫曼树的算法说明:define n/*叶子总数*/(a)(a)(a)define m 2*nT /* 结点总数 */证：由性质3,叶子结点数n=n+1,故哈夫曼树结点总数为n+n=n+(n T)=2*n T0202000例3在解某些判定

4、问题时，利用哈夫曼树获得最佳判定算法。学生成绩分布情况(a)分数段0-5960-6970-7980-8990-100比例0. 050.150. 400. 300.10分级EDCBA设有10000名学生,则需比较的次数为:比较10000次，分离出60分以下学生500名,剩9500人 比较9500次,分离出60-69分学生1500名,剩8000人 比较8000次,分离出70-79分学生4000名，剩4000人比较比较比较4000 次,分离出80-89分学生3000名.剩1000名90-100学生共比较：31500次WPL=0.05*1+0. 15*2+0. 4*3+0. 3*4+0. 1*4=3.

5、 15(b) (c)WPL=O. 4*1+0. 3*2+0. 15*3+0. 05*4+0. 1*4=2. 05WPL=O. 4*1+0. 3*2+0. 15*3+0. 05*4+0. 1*4=2. 05WPL=0. 05*3+0. 15*3+0,4*2+0. 3*2+0. 1*2=2. 2哈夫曼编码从哈夫曼树根结点开始，对左子树分配代码“0”，右子树分配代码“1”，一直到达叶子 结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。例， 对电文EMCAD编码。若等长编码，则000 001 010011 100 八EMCAD = 000001010011100 共 1

6、5 位设各字母的使用频度为E,M, C, A, D = 1,2,3, 3,4o用频度为权值生成哈夫曼树，并在叶子上 标注对应的字母，树枝分配代码“0”或“1” ：由哈夫曼编码树获得每个字母编的：EICAD000 001011011各字母的编码即为哈夫曼编码：EMCAD=000001011011共12位2. 9. 2二叉排序树二叉排序树是一种特殊结构的二叉树，它作为一种表的组织手段，通常被称为树表。可以 作为一种排序和检索的手段。定义 二叉排序树或是空树，或是具有下述性质的二叉树：其左子树上所有结点的数据值均 小于根结点的数据值；右子树上所有结点的数据值均大于或等于根结点的数据值。左子树和右 子

7、树又各是一棵二叉排序树。对二叉排序树，若按中序遍历就可以得到由小到大的有序序列。如上图，中序遍历得: 2, 3, 4, 8, 9, 9, 10, 13, 15, 18）二叉排序树的生成对任意一组数据元素序列R , R ,.，R ,要生成一棵二叉排序树的过程为： 12n（1）令R1为二叉树的根；（2）若R2RR1,令R2为R1左子树的根结点，否则R2为R1右子树的根结点；（3）对R3,.，Rn结点的插入方法同上。例，数据元素序列10, 18, 3, 8, 12, 2, 7, 3）,其生成二叉排序树的过程如下：(h )插入10(d )插入3图 12.20二叉排序树的生成过程二叉排序树中结点的删除要

8、求删除一个结点后的二叉树仍是一棵二叉排序树。算法思想，分以下几种情况考虑：（1）被删除的结点是叶子结点，则只需修改其双亲结点的指针既可；（2）被删除结点p只有左子树pL或右子树pR,此时只要使左子树pL或右子树pR成为p 双亲结点q的左子树或右子树即可。（3）若被删除结点p的左、右子树均非空，有两种做法：令PL直接链接到q的左（或右）孩子链域上，pR链接到p结点中序前趋结点s上（s是pL 最右下的结点）；以p结点的直接中序前趋或后继替代p所指结点，然后再从原二叉排序树中删去该直接前趋 或后继。图12.21二叉排序树的结点删除C）的中序遍历结 杲：(12, 13,；小14, 3, 25, 27, 28, 30)