哈夫曼树及应用.docx
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结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。 树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：WPL为最小的二叉树就称作最优二叉树或哈夫曼树。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中只含一棵树为止，这棵树就是哈夫曼树。7524©CD©0(a)例2：© ® O ®0,4030.10,1®®©®©®0.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在解某些判定问题时，利用哈夫曼树获得最佳判定算法。学生成绩分布情况(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. 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 共 15 位设各字母的使用频度为E,M, C, A, D = 1,2,3, 3,4o用频度为权值生成哈夫曼树，并在叶子上 标注对应的字母，树枝分配代码“0”或“1” ：由哈夫曼编码树获得每个字母编的：EICAD000 001011011各字母的编码即为哈夫曼编码：EMCAD=000001011011共12位2. 9. 2二叉排序树二叉排序树是一种特殊结构的二叉树，它作为一种表的组织手段，通常被称为树表。可以 作为一种排序和检索的手段。定义 二叉排序树或是空树，或是具有下述性质的二叉树：其左子树上所有结点的数据值均 小于根结点的数据值；右子树上所有结点的数据值均大于或等于根结点的数据值。左子树和右 子树又各是一棵二叉排序树。对二叉排序树，若按中序遍历就可以得到由小到大的有序序列。如上图，中序遍历得: 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二叉排序树的生成过程二叉排序树中结点的删除要求删除一个结点后的二叉树仍是一棵二叉排序树。算法思想，分以下几种情况考虑：（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)
