哈夫曼树及应用(1).docx

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

1、2.9.1 哈夫曼树及应用 哈夫曼树又称最优树（二叉树），是一类带权路径最短的树。构造这种树的算法最早是由哈夫曼(Huffman)1952年提出，这种树在信息检索中很有用。结点之间的路径长度：从一个结点到另一个结点之间的分支数目。树的路径长度：从树的根到树中每一个结点的路径长度之和。结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作： WPL为最小的二叉树就称作最优二叉树或哈夫曼树。 完全二叉树不一定是最优二叉树。 哈夫曼树的构造：（1）根据给定的n个权值w1,w2,.,wn构造n棵二叉树的集合F=T1,T2,.,Tn，

2、其中Ti中只有一个权值为wi的根结点，左右子树为空；（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。 例1：例2：结点的存储结构:构造哈夫曼树的算法说明：#define n /* 叶子总数 */#define m 2*n-1 /* 结点总数 */ 证：由性质3，叶子结点数 n0=n2+1，故哈夫曼树结点总数为 n0+n2=n0+(n0-1)=2*n0-1 例3 在解某些判定问题时

3、，利用哈夫曼树获得最佳判定算法。（a)WPL=0.05*1+0.15*2+0.4*3+0.3*4+0.1*4=3.15（b)(c)WPL=0.4*1+0.3*2+0.15*3+0.05*4+0.1*4=2.05 WPL=0.05*3+0.15*3+0.4*2+0.3*2+0.1*2=2.2哈夫曼编码 从哈夫曼树根结点开始，对左子树分配代码“0”，右子树分配代码“1”，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。例，对电文 EMCAD 编码。若等长编码，则设各字母的使用频度为 E,M,C,A,D=1,2,3,3,4。用频度为权值生成哈夫曼树，并在叶

4、子上标注对应的字母，树枝分配代码“0”或“1”: 2.9.2 二叉排序树 二叉排序树是一种特殊结构的二叉树，它作为一种表的组织手段，通常被称为树表。可以作为一种排序和检索的手段。定义 二叉排序树或是空树，或是具有下述性质的二叉树：其左子树上所有结点的数据值均小于根结点的数据值；右子树上所有结点的数据值均大于或等于根结点的数据值。左子树和右子树又各是一棵二叉排序树。对二叉排序树，若按中序遍历就可以得到由小到大的有序序列。如上图，中序遍历得：2，3，4，8，9，9，10，13，15，18二叉排序树的生成 对任意一组数据元素序列R1,R2,.,Rn，要生成一棵二叉排序树的过程为：（1）令R1为二叉树的根；（2）若R2RR1，令R2为R1左子树的根结点，否则R2为R1右子树的根结点；（3）对R3,.,Rn结点的插入方法同上。 例，数据元素序列10，18，3，8，12，2，7，3，其生成二叉排序树的过程如下： 二叉排序树中结点的删除 要求删除一个结点后的二叉树仍是一棵二叉排序树。算法思想，分以下几种情况考虑：（1）被删除的结点是叶子结点，则只需修改其双亲结点的指针既可；（2）被删除结点p只有左子树pL或右子树pR，此时只要使左子树pL或右子树pR成为p双亲结点q的左子树或右子树即可。（3）若被删除结点p的左、右子树均非空，有两种做法：