树转为二叉树的方法：.ppt

《树转为二叉树的方法：.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树和二叉树（Tree&BinaryTree）6.1树的基本概念6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用1提前介绍：二叉树的应用平衡树——排序树——字典树——带权树——最优树——特点：左右子树深度差≤1特点：“左小右大”由字符串构成的二叉树排序树特点：路径长度带权值带权路径长度最短的树，又称Huffman树，用途之一是通信中的压缩编码。2路径：路径长度：树的路径长度：带权路径长度：树的带权路径长度：霍夫曼树：6.5Huffman树及其应用一、最优二叉树（霍夫曼树）由一结点到另一结点间的分支所构成路径上的分支数目从树根到每一结点的路径长度

2、之和。结点到根的路径长度与结点上权的乘积预备知识：若干术语debacfg树中所有叶子结点的带权路径长度之和带权路径长度最小的树。a→e的路径长度＝树长度＝2103Huffman树简介：树的带权路径长度如何计算？WPL=wklkk=1nabdc7524(a)cdab2457(b)bdac7524(c)经典之例：WPL=36WPL=46WPL=35哈夫曼树则是：WPL最小的树。Huffman树WeightedPathLength4(1)由给定的n个权值{w0,w1,w2,…,wn-1}，构造具有n棵扩充二叉树的森林F={T0,T1,T2,…,Tn-1}，其中每一棵扩充二叉树Ti

3、只有一个带有权值wi的根结点，其左、右子树均为空。(2)重复以下步骤,直到F中仅剩下一棵树为止：①在F中选取两棵根结点的权值最小的扩充二叉树,做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。②在F中删去这两棵二叉树。③把新的二叉树加入F。构造霍夫曼树的基本思想：构造Huffman树的步骤（即Huffman算法）：权值大的结点用短路径，权值小的结点用长路径。先举例！5例1：设有4个字符d,i,a,n，出现的频度分别为7,5,2,4，怎样编码才能使它们组成的报文在网络中传得最快？法1：等长编码。例如用二进制编码来实现。取d=00，i=

4、01，a=10，n=11怎样实现Huffman编码？法2：不等长编码，例如用哈夫曼编码来实现。取d=0;i=10,a=110,n=111最快的编码是哪个？是非等长的Huffman码！先要构造Huffman树！6操作要点1：对权值的合并、删除与替换——在权值集合{7,5,2,4}中，总是合并当前值最小的两个权构造Huffman树的步骤：注：方框表示外结点（叶子，字符对应的权值），圆框表示内结点（合并后的权值）。7操作要点2：按左0右1对Huffman树的所有分支编号！dain111000Huffman编码结果：d=0,i=10,a=110,n=111WPL=1bit×7＋2bi

5、t×5+3bit(2+4)=35特点：每一码都不是另一码的前缀，绝不会错译!称为前缀码——将Huffman树与Huffman编码挂钩8例2（严题集6.26③）：假设用于通信的电文仅由8个字母{a,b,c,d,e,f,g,h}构成，它们在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}，试为这8个字母设计哈夫曼编码。如果用0～7的二进制编码方案又如何？霍夫曼编码的基本思想是：概率大的字符用短码，概率小的用长码。由于霍夫曼树的WPL最小，说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。解：先将概率放大100倍，以

6、方便构造哈夫曼树。权值集合w={7,19,2,6,32,3,21,10}，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。9w4={19,21,28,32}为清晰起见，重新排序为:w={2,3,6,7,10,19,21,32}2356w1={5,6,7,10,19,21,32}w2={7,10,11,19,21,32}w3={11,17,19,21,32}111071728211940w5={28,32,40}3260w6={40,60}w7={100}100bcadegfh哈夫曼树××××××××××××××10对应的哈夫曼编码（左0右1）：235611107321

7、72821194060100bcadegfh00000111111100符编码频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符编码频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman码的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=