资源描述：
《数据结构哈弗曼树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、6.7哈夫曼树一、Huffman树二、Huffman编码6.7.1Huffman树（最优二叉树）若干术语：路径：由一结点到另一结点间的分支所构成。路径长度：路径上的分支数目。例如：a→e的路径长度＝2二叉树的路径长度：从二叉树根到所有叶子结点的路径长度之和。树路径长度＝8二叉树的带权路径长度：从二叉树根结点到所有叶子结点的路径长度与相应叶子结点权值的乘积之和（WPL）即树中所有叶子结点的带权路径长度之和Huffman树：带权路径长度最小的树。Huffman常译为哈夫曼、赫夫曼、霍夫曼等树的带权路径长度如何计算？WPL=åwklk构造Huffman树的基本思想：权值大的结点用短路径，权
2、值小的结点用长路径。构造Huffman树的步骤（即Huffman算法）：(1)由给定的n个权值{w1,w2,…,wn}构造n棵二叉树的集合F={T1,T2,…,Tn}（即森林），其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。(2)在F中选取两棵根结点权值最小和次小的树分别做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。(3)在F中删去这两棵树，同时将新得到的二叉树加入F中。(4)重复(2)和(3),直到F只含一棵树为止。这棵树便是Huffman树。具体操作步骤：对权值进行合并、删除与替换——在权值集合{7,5,2,4}中，总是
3、合并当前值最小的两个权具体操作步骤：对权值进行合并、删除与替换——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权Huffman树特点：肯定没有度为1的结点；一棵有n0个叶子结点的Huffman树，共有2n0-1个结点；讨论：Huffman树有什么用？例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4，怎样编码才能使它们组成的报文在网络中传得最快？法1：等长编码令d=00，i=01，a=10，n=11，则：WPL1＝2bit×(7＋5＋2＋4）＝36法2：不等长编码令d=0;i=10,a=110,n=111，则：WPL2=1bit×7＋2bit×5+3bit×(
4、2+4)=356.7.2哈夫曼编码问题哈夫曼树可用于构造代码总长度最短的编码方案。具体构造方法如下：设需要编码的字符集合为{d1,d2,…,dn}，各个字符在电文中出现的次数集合为{w1,w2,…,wn}，以d1,d2,…,dn作为叶结点，以w1,w2,…,wn作为各叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码称之为哈夫曼编码。明确：要实现哈夫曼编码，就要先构造哈夫曼树按左“0”右“1”对哈夫曼树的所有分支编号——在哈夫曼树的基础上构造哈夫曼编码哈
5、夫曼编码结果：d=0,i=10,a=110,n=111WPL=1bit×7＋2bit×5+3bit(2+4)=35（小于等长码的WPL=36）在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的惟一性。例：若字符a的编码为01，b的编码为010，c的编码为10对于代码串01010，在译码时无法判定是将前两位码01译成字符a还是将前三位码010译为字符b。在哈夫曼树中，由于每个字符结点都是叶子结点，而叶子结点不可能在根结点到其他叶子结点的路径上，所以任何一个字符的哈夫曼树编码不可能是另一个字符的哈夫曼编码的前缀。练习：假设用于通信的电文仅由5个字母
6、{A，B，C，D，E}组成，字母在电文中出现的次数分别为2，4，5，7，8。试为这5个字母设计哈夫曼编码。A：010B：011C：00D：10E：116.8树与二叉树的转换讨论1：树如何转为二叉树？转换步骤：step1:将树中兄弟结点之间加一连线;step2:保留结点的最左孩子连线，删除其它孩子连线；step3:整理保留和添加的连线。讨论3：森林如何转为二叉树？即F={T1,T2,…,Tm}B={root,LB,RB}法一：①各森林先各自转为二叉树；②依次连到前一个二叉树的右子树上。法二：森林直接变兄弟，再转为二叉树法一和法二得到的二叉树是完全相同的、惟一的。森林转二叉树举例：（用法
7、一，各森林先转二叉树，在连接成一棵二叉树）森林转二叉树举例：（用法二，森林直接变兄弟，再转为二叉树）讨论4：二叉树如何还原为森林？即B={root,LB,RB}F={T1,T2,…,Tm}要点：把最右边的子树变为森林，其余右子树变为兄弟6.9树的遍历树的遍历深度优先遍历（先根、后根）树没有中序遍历（因子树不分左右）先根遍历Ø访问根结点；Ø按照从左到右依次先根遍历根结点的每棵子树。后根遍历Ø按照从左到右依次后根遍历根结点的每棵子树；Ø访问根结点。先根序列：a
