《数据结构-哈夫曼树和哈夫曼编码PPT》由会员分享，可在线阅读，更多相关《数据结构-哈夫曼树和哈夫曼编码PPT（56页珍藏版）》请在金锄头文库上搜索。
1、6.8 哈夫曼树与哈夫曼编码 1. 哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码 2. 回溯策略回溯策略 3. 章末复习章末复习 4. 例题讲解例题讲解 5. 课堂练习课堂练习 6. 作业作业 6.8 哈夫曼树与哈夫曼编码 1. 1.最优二叉树的定义最优二叉树的定义 2. 2.如何构造最优二叉树如何构造最优二叉树 3. 3.前缀编码前缀编码 树的路径长度树的路径长度定义为：最优二叉树的定义从根结点到该结点的路径上分支的数目。 结点的路径长度结点的路径长度定义为：树中每个结点的路径长度之和。ACBED树的路径长度为树的路径长度为5 5 最优二叉树的定义 树的带权路径长度树的带权路径长度定义为：树中所
2、有叶子结点的带权路径长度结点的带权路径长度之和 WPL(T) = wklk (对所有叶子结点)nk=1ABCHIDEFG75249WPL(T)= 7 2+5 2+2 3+4 3+9 2 =60最优二叉树的定义ABHDGCIFE74952WPL(T)= 7 4+9 4+5 3+4 2+2 1=89 最优二叉树的定义 最优二叉树最优二叉树定义为：带权路径长度WPL最小的二叉树，又称为哈夫曼树。例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 95627769713952761)2)3)527哈夫曼树 WPL=2 3 + 5 3 +6 2 + 7 2 + 9 2=65哈夫曼树713
3、952764)16713952765)1629练习练习: : 已知权值已知权值 W= 5, 6, 2, 9, 8 9562876865271)2)3)529哈夫曼树89134)5)WPL=2 3 + 5 3 +6 2 + 8 2 + 9 2=67哈夫曼树6527891317652789131730哈夫曼树( (哈夫曼算法哈夫曼算法) )以二叉树为例以二叉树为例: : 1. 1.根据给定的根据给定的n 个权值个权值w1, w2, , wn，构，构造造n 棵二叉树的集合棵二叉树的集合F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权值为其中每棵二叉树中均只含一个带权值为w wi i
4、 的根结点的根结点, ,其左、右子树为空树其左、右子树为空树; ; 2. 2.在在 F F 中选取其根结点的权值为最小的两中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和其左、右子树根结点的权值之和; ;哈夫曼树 3. 3.从从F中删去这两棵树，同时将刚生成的新中删去这两棵树，同时将刚生成的新树树加入到加入到F中中; ; 4. 4.重复重复 (2) (2) 和和 (3) (3) 两步，直至两步，直至 F F 中只含中只含一棵树
5、为止。一棵树为止。哈夫曼树哈夫曼树特点：1、有n个叶子结点2、没有度为1的结点3、总的结点数为 2n-14、深度n-15、形态不唯一编码编码：用二进制数表示字符例如：ASCII码，扩展的ASCII码特点：等长编码编码假设有8个符号:a0a1a2a3a4a5a6a7000001010011100101110111011110000100001 ?前缀编码有时候，每个字符出现的频率不一样，采用变长编码，使得出现频率多的编码短，频率低的编码长假设 A 0.4 B 0.3 C 0.2 D 0.1ABCD0100010001011 ?前缀编码 任何一个字符的编码都不是同一字符集中任何一个字符的编码都不是
6、同一字符集中另一个字符的编码的前缀另一个字符的编码的前缀。 利用哈夫曼树可以构造一种不等长的二利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的进制编码，并且构造所得的哈夫曼编码哈夫曼编码是一是一种种最优前缀编码最优前缀编码，即即: :所传电所传电文的总长度最短文的总长度最短。前缀编码ABCDE67259假设有5个符号以及它们的频率：求前缀编码95271667132901010011000110010111前缀编码1、建立哈夫曼树2、对边编号3、求出叶子结点的路径4、得到字符编码ABCDE67259000110010111EDC716AB132901010011前缀编码如何译码？001
7、011110001 ？ADECBABCDE000110010111回朔策略回朔策略假设问题的解为 n 元组 (x1, x2, , xn)，其中 xi 取值于集合 Si。n 元组的子组 (x1, x2, , xi) (in)的一个合法布局时，输出之。*/ if (in) 输出棋盘的当前布局; else for (j=1; jn) else while ( ! Empty(Si) 从 Si 中取 xi 的一个值 viSi; if (x1, x2, , xi) 满足约束条件 B( i+1, n); / 继续求下一个部分解 从 Si 中删除值 vi; / B回朔策略回朔策略求幂集求幂集ABCABACB
8、CABC回朔策略回朔策略求幂集求幂集000100000010100110000001010011100101110111000回朔策略回朔策略求幂集求幂集void powerSet(int num)if (num=len-1) for (int i=0; i2; i+)if (i = = 0)masknum=1;elsemasknum=0;powerSet(num+1);elsefor (int j=0; j1)的各棵树中，的各棵树中， （1）高度最小的树的高度是多少？它有多少个叶结点？）高度最小的树的高度是多少？它有多少个叶结点？ 多少个分支结点？多少个分支结点？ （2）高度最大的树的高度是
9、多少？它有多少个叶结点？）高度最大的树的高度是多少？它有多少个叶结点？ 多少个分支结点？多少个分支结点？ 【答案】【答案】 （1）结点个数为）结点个数为n时，高度最小的树的高度为时，高度最小的树的高度为2，有，有2层；层； 它有它有n -1个叶结点，个叶结点，1个分支结点；个分支结点； （2）高度最大的树的高度为）高度最大的树的高度为n，有，有n层；层； 它有它有1个叶结点，个叶结点，n- -1个分支结点。个分支结点。例题讲解例题讲解2、试分别找出满足以下条件的所有二叉树：、试分别找出满足以下条件的所有二叉树：(1) 二叉树的前序序列与中序序列相同二叉树的前序序列与中序序列相同;(2) 二叉树
10、的中序序列与后序序列相同二叉树的中序序列与后序序列相同;(3) 二叉树的前序序列与后序序列相同。二叉树的前序序列与后序序列相同。【解答】【解答】(1) 二叉树的前序序列与中序序列相同：二叉树的前序序列与中序序列相同： 空树或缺左子树的单支树；空树或缺左子树的单支树；(2) 二叉树的中序序列与后序序列相同：二叉树的中序序列与后序序列相同： 空树或缺右子树的单支树；空树或缺右子树的单支树；(3) 二叉树的前序序列与后序序列相同：二叉树的前序序列与后序序列相同： 空树或只有根结点的二叉树。空树或只有根结点的二叉树。例题讲解例题讲解3、深度为、深度为k（根的层次为（根的层次为1）的完全二叉树至少有多少
11、个结）的完全二叉树至少有多少个结点？点？ 至多有多少个结点？至多有多少个结点？k与结点数目与结点数目n之间的关系是什么？之间的关系是什么？【分析】【分析】 由由完完全全二二叉叉树树的的定定义义可可知知，对对于于k层层的的完完全全二二叉叉树树，其其上上的的k-1层层是是一一棵棵深深度度为为k-1的的满满二二叉叉树树。所所以以对对于于所所有有深深度度为为k的的完完全全二二叉叉树树，它它们们之之间间的的结结点点数数目目之之差差等等于于各各树树最最后后一一层层的的结点数目之差。结点数目之差。例题讲解例题讲解3、深度为、深度为k（根的层次为（根的层次为1）的完全二叉树至少有多少个结）的完全二叉树至少有多
12、少个结点？点？ 至多有多少个结点？至多有多少个结点？k与结点数目与结点数目n之间的关系是什么？之间的关系是什么？【解答】【解答】 深深度度为为k的的完完全全二二叉叉树树，其其最最少少的的结结点点数数=深深度度为为k-1的的满满二二叉叉树树的的结结点点数数+1= ；其其最最多多的的结结点点数数=深深度度为为k的的满满二叉树的结点数二叉树的结点数= 。 k与结点数目与结点数目n之间的关系可以根据二叉树的性质之间的关系可以根据二叉树的性质4得出：得出：例题讲解例题讲解4、对于深度为、对于深度为h，且只有度为，且只有度为0或或2的结点的二叉树，结点数的结点的二叉树，结点数 至少有多少？至多有多少？至少
13、有多少？至多有多少？(分析分析)【分析】【分析】 对对于于结结点点数数至至多多为为多多少少的的问问题题比比较较好好回回答答，我我们们知知道道满满二二叉叉树树中中只只有有度度为为0或或2的的结结点点，所所以以结结点点数数至至多多为为同同等等深深度度的满二叉树的结点数。的满二叉树的结点数。 对对于于结结点点数数至至少少为为多多少少的的问问题题，由由于于树树中中只只存存在在度度为为0或或2的的结结点点，即即对对一一个个结结点点而而言言，要要么么它它没没有有子子结结点点，要要么么就就有有两两个个子子结结点点，所所以以在在这这样样的的树树中中，除除第第一一层层（根根所所在在的的层）外，每一层至少有两个结
14、点。层）外，每一层至少有两个结点。例题讲解例题讲解5、已知一棵二叉树的中序序列为、已知一棵二叉树的中序序列为BDCEAFHG ， 后序序列为后序序列为DECBHGFA ，求对应的二叉树。，求对应的二叉树。(分析分析)【分析】【分析】根据各种遍历方法的定义，可知：根据各种遍历方法的定义，可知： 二叉树先序序列二叉树先序序列=根根+左子树先序序列左子树先序序列+右子树先序列；右子树先序列； 二叉树中序序列二叉树中序序列=左子树中序序列左子树中序序列+根根+右子树中序列；右子树中序列； 二叉树后序序列二叉树后序序列=左子树后序序列左子树后序序列+右子树后序序列根；右子树后序序列根；例题讲解例题讲解5
15、、已知一棵二叉树的中序序列为、已知一棵二叉树的中序序列为BDCEAFHG ， 后序序列为后序序列为DECBHGFA ，求对应的二叉树。，求对应的二叉树。(分析分析)【分析】【分析】从先序和后序序列中可以很容易的知道那一个结点是根，从先序和后序序列中可以很容易的知道那一个结点是根，而在中序序列中，可以根据根得到左、右子树的中序序而在中序序列中，可以根据根得到左、右子树的中序序列，相应的也就知道左、右子树的结点集合了。可以根列，相应的也就知道左、右子树的结点集合了。可以根据集合中的结点划分先序或后序序列中除根以外的结点据集合中的结点划分先序或后序序列中除根以外的结点序列，从而得到左、右子树的先序或
16、后序序列。依次类序列，从而得到左、右子树的先序或后序序列。依次类推，便可以递归得到整棵二叉树。推，便可以递归得到整棵二叉树。中序序列中序序列左子树中序序列左子树中序序列 根根 右子树中序序列右子树中序序列前序序列前序序列根根 左子树前序序列左子树前序序列 右子树前序序列右子树前序序列例题讲解例题讲解5、已知一棵二叉树的中序序列为、已知一棵二叉树的中序序列为BDCEAFHG ， 后序序列为后序序列为DECBHGFA ，求对应的二叉树。，求对应的二叉树。(分析分析)【解答】 构造这棵二叉树的过程如下所示： 中序序列：BDCE A FHG后序序列：DECB HGF A中序：BDCE 后序：DECB
17、中序： FHG后序： HGF 中序： D C E 后序：D E C 中序： HG后序： HG 中序：D 后序：D 中序：E 后序：E 中序：H 后序：H AFGHEDCB可以画出这棵二叉树为：例题讲解例题讲解例题讲解例题讲解1、二叉树的先序遍历和中序遍历为：先序遍历：、二叉树的先序遍历和中序遍历为：先序遍历：EFHIGJK； 中序遍历：中序遍历：HFIEJKG 。该二叉树根的右子树的根是。该二叉树根的右子树的根是 （ ） A）E B）F C）G D）H【答案】【答案】 1、C 2、B 3、D2、某二叉树结点的对称序（中序）序列为、某二叉树结点的对称序（中序）序列为ABCDEFG，后序序，后序序
18、 列为列为BDCAFGE。该二叉树结点的前序序列为。该二叉树结点的前序序列为 （ ） A）EGFACDB B）EACBDGF C）EAGCFBD D）EGACDFB 3、如果一棵二叉树结点的前序序列是、如果一棵二叉树结点的前序序列是ABC，后序序列是，后序序列是CBA， 则该二叉树则该二叉树 结点的对称序序列结点的对称序序列 A) 必为必为ABC B) 必为必为ACB C) 必为必为BCA D) 不能确定不能确定 6、分分别别画画出出具具有有3个个结结点点的的树树和和具具有有3个个结结点点的的二二叉叉树树的的所所有不同形态。并判断下列论述是否正确，为什么？有不同形态。并判断下列论述是否正确，为
19、什么？ （1）二叉树是一种特殊的树；）二叉树是一种特殊的树； （2）度为）度为2的树是一棵二叉树；的树是一棵二叉树； （3）度为）度为2的有序树是一棵二叉树。的有序树是一棵二叉树。 【解答】具有【解答】具有3个结点的树有两种形态，如图个结点的树有两种形态，如图1所示；所示； 而具有而具有3个结点的二叉树有个结点的二叉树有5种形态，如图种形态，如图2所示。所示。 图图1图图2 具有具有3个结点的二叉树的个结点的二叉树的5种形态种形态例题讲解例题讲解6、分分别别画画出出具具有有3个个结结点点的的树树和和具具有有3个个结结点点的的二二叉叉树树的的所所有不同形态。并判断下列论述是否正确，为什么？有不同
20、形态。并判断下列论述是否正确，为什么？ （1）二叉树是一种特殊的树；）二叉树是一种特殊的树； （2）度为）度为2的树是一棵二叉树；的树是一棵二叉树； （3）度为）度为2的有序树是一棵二叉树。的有序树是一棵二叉树。 【答案】【答案】（1）错误）错误 例题讲解例题讲解（2）错误）错误 （3）错误）错误7、在二叉树结点的先序序列、中序序列和后序序列中，所有、在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序叶子结点的先后顺序 A）都不相同）都不相同 B）先序和中序相同，而与后序不同）先序和中序相同，而与后序不同 C）完全相同）完全相同 D）中序和后序相同，而与先序不同）中序和后序相
21、同，而与先序不同8、在完全二叉树中，若一个结点只有一个子结点，则它没、在完全二叉树中，若一个结点只有一个子结点，则它没 A）左子结点）左子结点 B）左子结点和右子结点）左子结点和右子结点 C）右子结点）右子结点 D）左子结点、右子结点和兄弟结点）左子结点、右子结点和兄弟结点9、在下列存储形式中，哪一个不是树的存储形式、在下列存储形式中，哪一个不是树的存储形式 A）双亲表示法）双亲表示法 B）孩子链表表示法）孩子链表表示法 B）孩子兄弟表示法）孩子兄弟表示法 D）顺序存储表示法）顺序存储表示法 【答案】【答案】课堂练习课堂练习7、C8、C9、D10、在树中，一个结点的直接子结点的个数称为该结点、
22、在树中，一个结点的直接子结点的个数称为该结点 的的_ 。11、如果对于给定的一组权值，所构造出的二叉树的带权路径、如果对于给定的一组权值，所构造出的二叉树的带权路径 长度最小，则该树称为长度最小，则该树称为_ 。12、用数组、用数组A1.n顺序存储完全二叉树的各结点顺序存储完全二叉树的各结点,则当则当i=(n-1)/2时时, 结点结点Ai的右孩子是的右孩子是 结点结点_。13、完全二叉树中某结点无左子树，则它必是、完全二叉树中某结点无左子树，则它必是_。 课堂练习课堂练习度度哈夫曼树哈夫曼树(Huffman)A2i+1叶子叶子14、对于如图所示的森林、对于如图所示的森林 （1）将其转换为相应的
23、二叉树；）将其转换为相应的二叉树； （2）写出该森林的先序遍历序列和中序遍历序列。）写出该森林的先序遍历序列和中序遍历序列。A图题图题 14BCEFDGHIJKL课堂练习课堂练习【答案】【答案】ABCEFDGHIJKLABCEFDGHIJKL先序序列为：先序序列为：ABDEFCGHIJKL中序序列为：中序序列为：DEFBCAHIJGLK 课堂练习课堂练习15、已知一棵树的先根遍历序列为、已知一棵树的先根遍历序列为ABCED，后根遍历序列，后根遍历序列为为BECDA，求对应的树。，求对应的树。 (分析分析)【分析】【分析】 根据树与二叉树之间的转换关系，可知：根据树与二叉树之间的转换关系，可知：
24、 树的先序序列树的先序序列 = 对应二叉树先序序列对应二叉树先序序列 树的后跟序列树的后跟序列 = 对应二叉树中序序列对应二叉树中序序列 因此，可以先这两个序列构造对应的二叉树，再将因此，可以先这两个序列构造对应的二叉树，再将 二叉树转换为树。二叉树转换为树。课堂练习课堂练习15、已知一棵树的先根遍历序列为、已知一棵树的先根遍历序列为ABCED，后根遍历序列，后根遍历序列为为BECDA，求对应的树。，求对应的树。 (分析分析)【答案】【答案】ABCDEABCDE课堂练习课堂练习16、设电文中出现的字母为、设电文中出现的字母为A、B、C、D和和E，每个字母在，每个字母在 电文中出现的次数分别电文
25、中出现的次数分别9、27、3、5、和、和11。按哈夫曼。按哈夫曼 编码，则编码，则C的编码为的编码为 : (分析分析) A、10 B、110 C、1110 D、1111【分析】【分析】 先先构构造造哈哈夫夫曼曼树树，再再根根据据哈哈夫夫曼曼树树进进行行编编码码。注注意意：在构造哈夫曼树时，应注意左右孩子的排列。在构造哈夫曼树时，应注意左右孩子的排列。课堂练习课堂练习16、设电文中出现的字母为、设电文中出现的字母为A、B、C、D和和E，每个字母在，每个字母在 电文中出现的次数分别电文中出现的次数分别9、27、3、5、和、和11。按哈夫曼。按哈夫曼 编码，则编码，则C的编码为的编码为 : (分析分析) A、10 B、110 C、1110 D、1111【分析】【分析】 A B C D E 9 27 3 5 11 8 9 27 11 8 17 27 11 17 28 27 28 55【答案】【答案】 C55273511281789课堂练习课堂练习作业：作业：6.26作业作业 刚才的发言，如刚才的发言，如有不当之处请多指有不当之处请多指正。谢谢大家！正。谢谢大家！56
