《树转为二叉树的方法》由会员分享，可在线阅读，更多相关《树转为二叉树的方法（19页珍藏版）》请在金锄头文库上搜索。
1、第第6章章 树和二叉树（树和二叉树（ Tree & Binary Tree ）6.1 树的基本概念树的基本概念6.2 二叉树二叉树6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树6.4 树和森林树和森林6.5 赫夫曼树及其应用赫夫曼树及其应用1提前介绍：二叉树的应用提前介绍：二叉树的应用平衡树平衡树排序树排序树字典树字典树带权树带权树最优树最优树特点：左右子树深度差特点：左右子树深度差 1特点：特点：“左小右大左小右大”由字符串构成的二叉树排序树由字符串构成的二叉树排序树特点：路径长度带权值特点：路径长度带权值 带权路径长度最短的树，又称带权路径长度最短的树，又称 Huffman树，用途之
2、一是通信中的压缩编码。树，用途之一是通信中的压缩编码。2路路 径径：路径长度路径长度：树的路径长度树的路径长度：带权路径长度带权路径长度：树的带权路径长度树的带权路径长度：霍霍 夫夫 曼曼 树树：6.5 Huffman6.5 Huffman树及其应用树及其应用一、最优二叉树（一、最优二叉树（霍夫曼霍夫曼树）树）由一结点到另一结点间的分支所构成由一结点到另一结点间的分支所构成路径上的分支数目路径上的分支数目从树根到从树根到每一结点每一结点的路径长度之和。的路径长度之和。结点到根的路径长度与结点上权的乘积结点到根的路径长度与结点上权的乘积预备知识：若干术语预备知识：若干术语debacf g树中所有
3、树中所有叶子结点叶子结点的带权路径长度之和的带权路径长度之和带权路径长度最小的树。带权路径长度最小的树。aeae的路径长度的路径长度树长度树长度2 210103HuffmanHuffman树简介：树简介：树的带权路径长度如何计算？树的带权路径长度如何计算？WPLWPL = = w wk kl lk k k=1k=1n nabdc7524(a)cdab2457(b)bdac7524(c)经典之例：经典之例：经典之例：经典之例：WPL=36WPL=46WPL= 35哈夫曼哈夫曼树树则则是是：WPL WPL 最小的树。最小的树。Huffman树树Weighted Path LengthWeighte
4、d Path Length4(1)(1) 由给定的由给定的由给定的由给定的 n n 个权值个权值个权值个权值 w w0 0, , w w1 1, , w w2 2, , , , w wn n-1-1 ，构造具有，构造具有，构造具有，构造具有 n n 棵扩棵扩棵扩棵扩充二叉树的充二叉树的充二叉树的充二叉树的森林森林森林森林F F = = T T0 0, , T T1 1, , T T2 2, , , , T Tn n-1 -1 ，其中每一棵扩充二，其中每一棵扩充二，其中每一棵扩充二，其中每一棵扩充二叉树叉树叉树叉树 T Ti i 只有一个带有权值只有一个带有权值只有一个带有权值只有一个带有权值
5、w wi i 的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。的根结点，其左、右子树均为空。 (2)(2) 重复以下步骤重复以下步骤重复以下步骤重复以下步骤, , 直到直到直到直到 F F 中仅剩下一棵树为止：中仅剩下一棵树为止：中仅剩下一棵树为止：中仅剩下一棵树为止： 在在在在 F F 中中中中选取两棵根结点的权值最小选取两棵根结点的权值最小选取两棵根结点的权值最小选取两棵根结点的权值最小的扩充二叉树的扩充二叉树的扩充二叉树的扩充二叉树, , 做为左、做为左、做为左、做为左、右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉
6、树的右子树构造一棵新的二叉树。置新的二叉树的右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为根结点的权值为根结点的权值为根结点的权值为其左、右子树上根结点的权值之和其左、右子树上根结点的权值之和其左、右子树上根结点的权值之和其左、右子树上根结点的权值之和。 在在在在 F F 中删去这两棵二叉树。中删去这两棵二叉树。中删去这两棵二叉树。中删去这两棵二叉树。 把新的二叉树加入把新的二叉树加入把新的二叉树加入把新的二叉树加入 F F。构造霍夫曼树的基本思想：构造霍夫曼树的基本思想：构造构造HuffmanHuffman树的步骤（即树的步骤（即HuffmanHuffman算法）：算法）：权值大的结
7、点用短路径，权值小的结点用长路径。权值大的结点用短路径，权值小的结点用长路径。权值大的结点用短路径，权值小的结点用长路径。权值大的结点用短路径，权值小的结点用长路径。先举例！先举例！5例例1：设有设有4 4个字符个字符d,i,a,nd,i,a,n，出现的频度分别为，出现的频度分别为7,5,2, 7,5,2, 4 4，怎样编码才能使它们组成的报文在网络中传得最快，怎样编码才能使它们组成的报文在网络中传得最快？法法1 1：等长编码等长编码。例如用二进制编码来实现。例如用二进制编码来实现。 取取 d= d=0000，i=i=0101，a=a=1010，n=n=1111怎样实现怎样实现HuffmanH
8、uffman编码？编码？法法2 2：不等长编码不等长编码，例如用哈夫曼编码来实现。，例如用哈夫曼编码来实现。 取取 d= d=0 0; i=; i=1010, a=, a=110110, n=, n=111111最快的编码是哪个？最快的编码是哪个？ 是非等长的是非等长的HuffmanHuffman码！码！先要构造先要构造HuffmanHuffman树！树！6操作要点操作要点1 1：对权值的合并、删除与替换对权值的合并、删除与替换在权值集合在权值集合7,5,2,47,5,2,4中，总是合并中，总是合并当前值最小当前值最小的两个权的两个权构造构造HuffmanHuffman树的步骤：树的步骤：注：
9、方框表示外结点（叶子，字符对应的权值），注：方框表示外结点（叶子，字符对应的权值）， 圆框表示内结点（合并后的权值）。圆框表示内结点（合并后的权值）。7操作要点操作要点2 2：按左按左0 0右右1 1对对HuffmanHuffman树的所有分支编号！树的所有分支编号！d da ai in n1 11 11 10 00 00 0HuffmanHuffman编码结果：编码结果：d=d=0 0, i=, i=1010, a=, a=110110, n=, n=111111WPL=1bit7WPL=1bit72bit5+3bit(2+4)=2bit5+3bit(2+4)=3535特点：每一码都不是另一
10、码的前缀，绝不会错译特点：每一码都不是另一码的前缀，绝不会错译! ! 称为前缀码称为前缀码将将将将 HuffmanHuffman树树 与与 Huffman Huffman编码编码 挂钩挂钩8例例2 2（严题集（严题集6.266.26）：假设用于通信的电文仅由假设用于通信的电文仅由8 8个字母个字母 a, b, c, d, e, f, g, ha, b, c, d, e, f, g, h 构成，它们在电文中出现的概率分构成，它们在电文中出现的概率分别为别为 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 0.07, 0.19, 0.02, 0.06,
11、 0.32, 0.03, 0.21, 0.10，试为这试为这8 8个字母设计哈夫曼编码。个字母设计哈夫曼编码。如果用如果用0 07 7的二进制编码方案的二进制编码方案又如何？又如何？霍夫曼霍夫曼编码的基本思想是：编码的基本思想是：概率大的字符用短码，概率小的用概率大的字符用短码，概率小的用长码长码。由于。由于霍夫曼树的霍夫曼树的WPLWPL最小，最小，说明编码所需要的比特数最说明编码所需要的比特数最少。这种编码已广泛应用于网络通信中。少。这种编码已广泛应用于网络通信中。解：解：先将概率放大先将概率放大100100倍，以方便构造哈夫曼树。倍，以方便构造哈夫曼树。权值集合权值集合 w=7, 19,
12、 2, 6, 32, 3, 21, 10 w=7, 19, 2, 6, 32, 3, 21, 10，按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。按哈夫曼树构造规则（合并、删除、替换），可得到哈夫曼树。9w4=19, 21, w4=19, 21, 28,28, 32 32为清晰起见，重新排序为为清晰起见，重新排序为: :w=2, 3, 6, 7, 10, 19, 21, 32w=2, 3, 6, 7, 10, 19, 21, 322 23 35 56 6w1=w1=5,5, 6, 7, 10, 19, 21, 32 6, 7, 10, 19, 21, 32w2=7, 10, w2=7
13、, 10, 11,11, 19, 21, 32 19, 21, 32w3=w3=11, 17,11, 17, 19, 21, 32 19, 21, 32111110107 717172828212119194040w5=w5=28,28,32,32,4040 32326060w6=w6=40,6040,60 w7=w7=100100 100100b bc ca ad de eg gf fh h哈夫曼树哈夫曼树 10对应的哈夫曼编码（左对应的哈夫曼编码（左0右右1）：）：2 23 35 56 6111110107 73232171728282121191940406060100100b bc c
14、a ad de eg gf fh h0 00 00 00 00 01 11 11 11 11 11 11 10 00 0符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman码的码的WPL2(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.61 WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 但哈夫曼编
15、码不唯一但哈夫曼编码不唯一11001100000011110111101110111010101111111111010111011101000001010011100101110111二进制码二进制码二进制码二进制码11另一种结果表示：另一种结果表示：12哈夫曼译码译码过程是分解电文中字符串，从根出发，按字母0或1确定找左孩子或右孩子，（即遇0向左，遇1向右）直到叶子结点，便求得该子串相应的子串。13例例3 3（实验二方案（实验二方案3 3）：设字符集为设字符集为2626个英文字母，其出个英文字母，其出现频度如下表所示。现频度如下表所示。51481156357203251频度频度zyxwvu
16、t t字符字符11611882380频度频度p21fq15gr47hsonmlkj字符字符5710332221364186频度频度ie edcba空格空格空格空格字符字符先建哈夫曼树，再利用此树对报文先建哈夫曼树，再利用此树对报文“This program is my favorite”进行编码和译码。进行编码和译码。要求编程实现：要求编程实现：14提示提示1 1：霍夫曼树中各结点的结构霍夫曼树中各结点的结构可以定义为如下可以定义为如下5 5个分量个分量：charweightparentlchildRchild将整个将整个霍夫曼树的霍夫曼树的结点结点存储在一个数组中：存储在一个数组中：HT1.
17、nHT1.n; ; 将结点的将结点的编码编码存储在存储在HC1.nHC1.n中。中。提示提示3 3：霍夫曼树如何构造？霍夫曼树如何构造？构造好之后又如何求得构造好之后又如何求得各结点对应的霍夫曼编码？各结点对应的霍夫曼编码？算法参见教材算法参见教材P147P147。提示提示2 2：霍夫曼树的霍夫曼树的存储结构存储结构可采用可采用顺序存储顺序存储结构：结构：15小结：哈夫曼树及其应用小结：哈夫曼树及其应用1.Huffman1.Huffman算法的思路：算法的思路：权值大的结点用短路径，权值小的结点用长路径。权值大的结点用短路径，权值小的结点用长路径。2.2.构造构造HuffmanHuffman树
18、的步骤：树的步骤： 对权值的合并、删除与替换对权值的合并、删除与替换3. Huffman3. Huffman编码规则：编码规则： 左左“0” “0” 右右“1”“1”，是一种前，是一种前缀码缀码也称为最小冗余编码、紧致码，等等，它是数据压缩也称为最小冗余编码、紧致码，等等，它是数据压缩学的基础。学的基础。补充补充1 1：构造构造HuffmanHuffman树的过程描述树的过程描述16怎样生成怎样生成HuffmanHuffman树？树？ 步骤如下：步骤如下：(1)(1) 由给定的由给定的由给定的由给定的 n n 个权值个权值个权值个权值 w w1 1, , w w2 2, , , , w wn
19、n 构成构成构成构成n n棵二叉树的集棵二叉树的集棵二叉树的集棵二叉树的集合（即森林）合（即森林）合（即森林）合（即森林）F F = = T T1 1, , T T2 2, , , , T Tn n ，其中每棵二叉树，其中每棵二叉树，其中每棵二叉树，其中每棵二叉树 T Ti i 中中中中只有一个带权为只有一个带权为只有一个带权为只有一个带权为 w wi i 的根结点，其左右子树均空。的根结点，其左右子树均空。的根结点，其左右子树均空。的根结点，其左右子树均空。(2)(2) 在在在在F F 中中中中选取两棵根结点的权值最小的树选取两棵根结点的权值最小的树选取两棵根结点的权值最小的树选取两棵根结点
20、的权值最小的树 做为左右子树做为左右子树做为左右子树做为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值构造一棵新的二叉树，且置新的二叉树的根结点的权值构造一棵新的二叉树，且置新的二叉树的根结点的权值构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的为其左右子树上根结点的为其左右子树上根结点的为其左右子树上根结点的权值之和权值之和权值之和权值之和。(3) (3) 在在在在F F 中删去这两棵树，同时将新得到的二叉树加入中删去这两棵树，同时将新得到的二叉树加入中删去这两棵树，同时将新得到的二叉树加入中删去这两棵树，同时将新得到的二叉树加入 F F中中中中。(4) (4
21、) 重复重复重复重复(2) (2) 和和和和(3) (3) , , 直到直到直到直到 F F 只含一棵树为止。这棵树便是只含一棵树为止。这棵树便是只含一棵树为止。这棵树便是只含一棵树为止。这棵树便是赫夫曼树。赫夫曼树。赫夫曼树。赫夫曼树。17二叉树小结1 1、定义和性质定义和性质2 2、存储结构存储结构3 3、遍历遍历4 4、线索化线索化：线索树：线索树顺序结构顺序结构链式结构链式结构二叉链表二叉链表三叉链表三叉链表先序线索树先序线索树中序线索树中序线索树后序线索树后序线索树树二叉树二叉树森林中序遍历中序遍历后序遍历后序遍历先序遍历先序遍历霍夫曼树霍夫曼树霍夫曼编码霍夫曼编码18本章小结1 1、定义和性质定义和性质2 2、存储结构存储结构3 3、遍历遍历4 4、线索化线索化：线索树：线索树顺序结构顺序结构链式结构链式结构二叉链表二叉链表三叉链表三叉链表先序线索树先序线索树中序线索树中序线索树后序线索树后序线索树树树树树二叉树二叉树二叉树二叉树森林森林森林森林先先序序遍遍历历中中序序遍遍历历遍历遍历存储结构存储结构遍历遍历双亲表示双亲表示孩子表示孩子表示孩子兄弟孩子兄弟先序遍历先序遍历后序遍历后序遍历中序遍历中序遍历后序遍历后序遍历先序遍历先序遍历霍夫曼树霍夫曼树霍夫曼编码霍夫曼编码19
