资源描述：
《严蔚敏数据结构 (11).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1第6章树和二叉树（Tree&BinaryTree）6.1树的基本概念6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用6.5Huffman树及其应用一、Huffman树二、Huffman编码最优二叉树Huffman树Huffman编码带权路径长度最短的树不等长编码是通信中最经典的压缩编码2树的带权路径长度如何计算？WPL=wklkk=1nabdc7524(a)cdab2457(b)bdac7524(c)经典之例：WPL=WPL=WPL=Huffman树是WPL最小的树树中所有叶子结点的带权路径长度之和3646353一、Huff
2、man树（最优二叉树）路径：路径长度：树的路径长度：带权路径长度：树的带权路径长度：Huffman树：由一结点到另一结点间的分支所构成。路径上的分支数目。从树根到每一结点的路径长度之和。结点到根的路径长度与结点上权的乘积（WPL）若干术语：debacfg即树中所有叶子结点的带权路径长度之和带权路径长度最小的树。例如：a→e的路径长度＝树长度＝210Huffman常译为赫夫曼、霍夫曼、哈夫曼、胡夫曼等WeightedPathLength41.构造Huffman树的基本思想：例：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4，怎样编码才能使它们组成
3、的报文在网络中传得最快？法1：等长编码（如二进制编码）令d=00，i=01，a=10，n=11，则：WPL1＝2bit×(7＋5＋2＋4）＝36法2：不等长编码（如Huffman编码）令d=0;i=10,a=110,n=111，则：明确：要实现Huffman编码，就要先构造Huffman树讨论：Huffman树有什么用？权值大的结点用短路径，权值小的结点用长路径。WPL最小的树频度高的信息用短码，低的用长码，传输效率肯定高！WPL2=1bit×7＋2bit×5+3bit×(2+4)=35最小冗余编码、信息高效传输52.构造Huffman树的步骤（即Huff
4、man算法）：(1)由给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}（即森林），其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。(2)在F中选取两棵根结点权值最小的树做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。(3)在F中删去这两棵树，同时将新得到的二叉树加入F中。(4)重复(2)和(3),直到F只含一棵树为止。这棵树便是Huffman树。怎样证明它就是WPL最小的最优二叉树？参考《信源编码》总之，每次合并当前值最小的两个权。(此树特征：没有度为1的结点)6
5、step1：对权值进行合并、删除与替换——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权具体操作步骤：a.初始方框表示外结点（叶子，字符）圆框表示内结点（合并后的权值）b.合并{2}{4}c.合并{5}{6}d.合并{7}{11}谁左谁右？不规定就不会惟一7step2：按左“0”右“1”对Huffman树的所有分支编号dain111000Huffman编码结果：d=0,i=10,a=110,n=111WPL=1bit×7＋2bit×5+3bit(2+4)=35（小于等长码的WPL=36）特征：每一码不会是另一码的前缀，译码时可惟一复原Huffm
6、an编码也称为前缀码——将Huffman树与Huffman编码挂钩8二、Huffman编码哈夫曼编码的基本思想是——出现概率大的信息用短码，概率小的用长码,最小冗余Huffman编码不等长编码是通信中最经典的压缩编码按左“0”右“1”对Huffman树的所有分支编号如何将Huffman树与Huffman编码挂钩?9本节重点：如何编程实现Huffman编码？建议1：Huffman树中结点的结构可设计成4或5分量形式：charweightparentlchildrchild将整个Huffman树的结点存储在一个数组HT[1..n..m]中;（Huffman树内
7、外结点总数m=2n-1）各叶子结点的编码存储在另一“复合”数组HC[1..n]中。(n个权值就是n个叶子,将对应n个不同码串)建议2：Huffman树的存储结构可采用顺序存储结构：即：先构造Huffman树HT再求出n个权值/字符的Huffman编码HC参见教材P14710m=n0+n2=n+(n-1)=2n-1Huffman编码举例解：先将概率放大100倍，以方便构造哈夫曼树。放大后的权值集合w={7,19,2,6,32,3,21,10}，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。例1【严题集6.26③】：假设用于通信的电文仅由8个字母{a
8、,b,c,d,e,f,g,h}构成，它们在电文中出现的概率分别为{
