武汉软件工程职业学院《数据结构讲义》第15讲 哈夫曼树及其应用

《武汉软件工程职业学院《数据结构讲义》第15讲 哈夫曼树及其应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章树第十五讲哈夫曼树及其应用1．了解最优树的特性，掌握建立最优树。2．哈夫曼编码的方法。Ø教学重点：哈夫曼树的实现方法及哈夫曼编码的概念Ø教学难点：哈夫曼树的实现方法及哈夫曼编码的概念Ø授课内容4.6哈夫曼树及其应用哈夫曼树（Huffman），又称最优二叉树，是一类带权路径长度最短的树，有着广泛的应用。1．哈夫曼树的基本概念（1）路径长度由树中一个结点到另一个结点的分支构成这两个结点之间的路径，路径上分支的树目称为路径长度。（2）树的路径长度从根结点到每个结点的路径长度之和。（3）结点的带权路径长度从根结点到某

2、个结点的路径长度与该结点所带的权值的乘积。（4）树的带权路径长度树中所有叶子结点的带权路径长度之和，通常记作：WPL＝（5）哈夫曼树假设有n个权值{W1，W2，……，Wn}，试构造有n个叶子结点的二叉树，每个叶子结点拥有一个权值W，则其中带权路径长度WPL最小的二叉树，称为最优二叉树或哈夫曼树。图4－6－1给出了三棵二叉树以及它们的带权路径长度。为了直观起见，在图中把带权的叶子结点画成方形，其它非叶子结点仍为圆形。这三棵二叉树叶子结点树相同，权值也相同，但是它们的带权路径程度WPL各不相同。图4－6－1（a）的WP

3、L最小，它就是哈夫曼树。第四章树245845824528(a)WPL＝38(b)WPL＝49(c)WPL＝36图4－6－1具有不同带权路径长度的二叉树1．构造哈夫曼树1）构造哈夫曼树的方法（1）根据给定的n个权值{W1，W2，……，Wn}构成n棵二叉树的集合F＝{T1，T2，……，Tn}，其中每一棵二叉树Ti中只有一个带权为Wi的根结点，其左右子树均空。（2）在F中选出两棵根结点权值最小的树作为一棵新的二叉树的左右子树，且置新二叉树根结点的权值为两棵子树根结点的权值之和。（3）从F中删去这两棵树，同时把新二叉树加入

4、F中。（4）重复（2）和（3），直到F中只有一棵树为止，此树便是哈夫曼树。现根据上述的方法，对于一组具体的权值{2，4，5，8}构造哈夫曼树。图4－6－2为具体构造过程。245864258192458(a)(b)(c)图4－6－2哈夫曼树构造过程6112456118(d)6n个叶子构成的哈夫曼树的树形不一定是唯一的，因为将F中两棵权值最小和次小的子树合并时，哪一棵做左子树，哪一棵做右子树并无严格限制。一般习惯把权值较小的当做左子树，权值较大的当做右子树。但是其带权路径长度是唯一的。2）哈夫曼算法实现第四章树由于哈夫

5、曼树中没有度为1的结点，根据二叉树性质2可知一棵有N个叶子的哈夫曼树共有2N－1个结点，因此可以选用一个大小为2N－1的一维数组存储哈夫曼树。存储结构定义如下：#defineN8#defineM2*N-1Typedefstructhnode{intweight;intlchild,rchild;intparent;}Hnode;HnodeHt[M+1];数组Ht的前N个元素表示叶子结点，其weight域赋予权值，最后一个元素表示根结点。若以一组权值{2，4，5，8}为例，数组Ht的初始状态如图4－6－3（a）所示。

6、执行算法4.9后，数组Ht的最终结果如图4－6－3（b）所示。－1－1－1－－1－1－1－－1－1－1－－1－1－18－1－1－15－1－1－14－1－1－1253－119426111056－1－168－1－155－1－144－1－142weightParentlchildrchildweightParentlchildrchild01234560123456(a)Ht的初始状态(b)Ht的最终状态图4－6－3哈夫曼树存储结构示意算法4.9voidHuffman_tree(intw[N],HnodeHt[M]){f

7、or(i=0;i

8、rent==-1){m2=Ht[j].weight;p2=j;}}Ht[p1].parent=i;Ht[p2].parent=i;Ht[i].lchild=p1;Ht[i].rchild=p2;Ht[i].weight=Ht[p1].weight+Ht[p2].weight;}}1．哈夫曼树的应用（1）用于最佳判断过程在实际应用中常常用树型的程序结构形式来解