数据结构哈夫曼树和哈夫曼编码.pptx

《数据结构哈夫曼树和哈夫曼编码.pptx》由会员分享，可在线阅读，更多相关《数据结构哈夫曼树和哈夫曼编码.pptx（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、6.8 哈夫曼树与哈夫曼编码 1.1.最优二叉树的定义最优二叉树的定义 2.2.如何构造最优二叉树如何构造最优二叉树 3.3.前缀编码前缀编码 第1页/共55页树的路径长度定义为：最优二叉树的定义从根结点到该结点的路径上分支的数目。结点的路径长度定义为：树中每个结点的路径长度之和。ACBED树的路径长度为5 第2页/共55页最优二叉树的定义 树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和 WPL(T)=wklk(对所有叶子结点)nk=1ABCHIDEFG75249WPL(T)=7 2+5 2+2 3+4 3+9 2=60第3页/共55页最优二叉树的定义ABHDGCIFE74952W

2、PL(T)=7 4+9 4+5 3+4 2+2 1=89 第4页/共55页最优二叉树的定义 最优二叉树定义为：带权路径长度WPL最小的二叉树，又称为哈夫曼树。第5页/共55页例如:已知权值 W=5,6,2,9,7 95627769713952761)2)3)527哈夫曼树 第6页/共55页WPL=2 3+5 3+6 2+7 2+9 2=65哈夫曼树713952764)16713952765)1629第7页/共55页练习:已知权值 W=5,6,2,9,8 9562876865271)2)3)529哈夫曼树8913第8页/共55页4)5)WPL=2 3+5 3+6 2+8 2+9 2=67哈夫曼树

3、6527891317652789131730第9页/共55页哈夫曼树(哈夫曼算法)以二叉树为例:1.根据给定的n 个权值w1,w2,wn，构造n 棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值为wi 的根结点,其左、右子树为空树;第10页/共55页 2.在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;哈夫曼树第11页/共55页 3.从F中删去这两棵树，同时将刚生成的新树加入到F中;4.重复(2)和(3)两步，直至 F 中只含一棵树为止。哈夫曼树第12页/共55页哈夫曼树特点

4、：1、有n个叶子结点2、没有度为1的结点3、总的结点数为 2n-14、深度n-15、形态不唯一第13页/共55页编码编码：用二进制数表示字符例如：ASCII码，扩展的ASCII码特点：等长编码第14页/共55页编码假设有8个符号:a0a1a2a3a4a5a6a7000001010011100101110111第15页/共55页前缀编码有时候，每个字符出现的频率不一样，采用变长编码，使得出现频率多的编码短，频率低的编码长假设 A 0.4 B 0.3 C 0.2 D 0.1ABCD0100010001011?第16页/共55页前缀编码 任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。利

5、用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，即:所传电文的总长度最短。第17页/共55页前缀编码ABCDE67259假设有5个符号以及它们的频率：求前缀编码第18页/共55页95271667132901010011000110010111前缀编码1、建立哈夫曼树2、对边编号3、求出叶子结点的路径4、得到字符编码ABCDE67259000110010111第19页/共55页EDC716AB132901010011前缀编码如何译码？001011110001？ADECBABCDE000110010111第20页/共55页回朔策略回朔策略假设问题的解为 n 元

6、组(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第26页/共55页回朔策略回朔策略求幂集求幂集ABCABACBCABC第27页/共55页回朔策略回朔策略求幂集求幂集000100000010100110000001010011100101110111000第28页/

7、共55页回朔策略回朔策略求幂集求幂集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）高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？【答案】（1）结点个数为n时，高度最小的树的高度为2，有2层；它有n-1个叶结点，1个分支结点；（2）高度最大的树的高度为n，有n层；它有1个叶结点，n-1个分支结点。第34页/共5

8、5页例题讲解例题讲解2、试分别找出满足以下条件的所有二叉树：(1)二叉树的前序序列与中序序列相同;(2)二叉树的中序序列与后序序列相同;(3)二叉树的前序序列与后序序列相同。【解答】(1)二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；(2)二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；(3)二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。第35页/共55页例题讲解例题讲解3、深度为k（根的层次为1）的完全二叉树至少有多少个结点？至多有多少个结点？k与结点数目n之间的关系是什么？【分析】由完全二叉树的定义可知，对于k层的完全二叉树，其上的k-1层是一棵深度为k-1的

9、满二叉树。所以对于所有深度为k的完全二叉树，它们之间的结点数目之差等于各树最后一层的结点数目之差。第36页/共55页例题讲解例题讲解3、深度为k（根的层次为1）的完全二叉树至少有多少个结点？至多有多少个结点？k与结点数目n之间的关系是什么？【解答】深 度 为 k的 完 全 二 叉 树，其 最 少 的 结 点 数=深 度 为 k-1的 满 二 叉 树 的 结 点 数+1=；其最多的结点数=深度为k的满二叉树的结点数=。k与结点数目n之间的关系可以根据二叉树的性质4得出：第37页/共55页例题讲解例题讲解4、对于深度为h，且只有度为0或2的结点的二叉树，结点数 至少有多少？至多有多少？(分析)【分

10、析】对于结点数至多为多少的问题比较好回答，我们知道满二叉树中只有度为0或2的结点，所以结点数至多为同等深度的满二叉树的结点数。对于结点数至少为多少的问题，由于树中只存在度为0或2的结点，即对一个结点而言，要么它没有子结点，要么就有两个子结点，所以在这样的树中，除第一层（根所在的层）外，每一层至少有两个结点。第38页/共55页例题讲解例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG，后序序列为DECBHGFA，求对应的二叉树。(分析)【分析】根据各种遍历方法的定义，可知：二叉树先序序列=根+左子树先序序列+右子树先序列；二叉树中序序列=左子树中序序列+根+右子树中序列；二叉树后序序列=左子

11、树后序序列+右子树后序序列根；第39页/共55页例题讲解例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG，后序序列为DECBHGFA，求对应的二叉树。(分析)【分析】从先序和后序序列中可以很容易的知道那一个结点是根，而在中序序列中，可以根据根得到左、右子树的中序序列，相应的也就知道左、右子树的结点集合了。可以根据集合中的结点划分先序或后序序列中除根以外的结点序列，从而得到左、右子树的先序或后序序列。依次类推，便可以递归得到整棵二叉树。中序序列左子树中序序列 根 右子树中序序列前序序列根 左子树前序序列 右子树前序序列第40页/共55页例题讲解例题讲解5、已知一棵二叉树的中序序列为BDCE

12、AFHG，后序序列为DECBHGFA，求对应的二叉树。(分析)【解答】构造这棵二叉树的过程如下所示：中序序列：BDCE A FHG后序序列：DECB HGF A中序：BDCE 后序：DECB 中序：FHG后序：HGF 中序：D C E 后序：D E C 中序：HG后序：HG 中序：D 后序：D 中序：E 后序：E 中序：H 后序：H 第41页/共55页AFGHEDCB可以画出这棵二叉树为：例题讲解第42页/共55页例题讲解1、二叉树的先序遍历和中序遍历为：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是（）A）E B）F C）G D）H【答案】1、C 2、B 3、D

13、2、某二叉树结点的对称序（中序）序列为ABCDEFG，后序序 列为BDCAFGE。该二叉树结点的前序序列为（）A）EGFACDB B）EACBDGF C）EAGCFBD D）EGACDFB 3、如果一棵二叉树结点的前序序列是ABC，后序序列是CBA，则该二叉树 结点的对称序序列 A)必为ABC B)必为ACB C)必为BCA D)不能确定 第43页/共55页6、分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。并判断下列论述是否正确，为什么？（1）二叉树是一种特殊的树；（2）度为2的树是一棵二叉树；（3）度为2的有序树是一棵二叉树。【解答】具有3个结点的树有两种形态，如图1所示；而

14、具有3个结点的二叉树有5种形态，如图2所示。图1图2 具有3个结点的二叉树的5种形态例题讲解第44页/共55页6、分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。并判断下列论述是否正确，为什么？（1）二叉树是一种特殊的树；（2）度为2的树是一棵二叉树；（3）度为2的有序树是一棵二叉树。【答案】（1）错误 例题讲解（2）错误（3）错误第45页/共55页7、在二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序 A）都不相同 B）先序和中序相同，而与后序不同 C）完全相同 D）中序和后序相同，而与先序不同8、在完全二叉树中，若一个结点只有一个子结点，则它没 A）左子结点

15、 B）左子结点和右子结点 C）右子结点 D）左子结点、右子结点和兄弟结点9、在下列存储形式中，哪一个不是树的存储形式 A）双亲表示法 B）孩子链表表示法 B）孩子兄弟表示法 D）顺序存储表示法 【答案】课堂练习7、C8、C9、D第46页/共55页10、在树中，一个结点的直接子结点的个数称为该结点 的_。11、如果对于给定的一组权值，所构造出的二叉树的带权路径 长度最小，则该树称为_。12、用数组A1.n顺序存储完全二叉树的各结点,则当i=(n-1)/2时,结点Ai的右孩子是 结点_。13、完全二叉树中某结点无左子树，则它必是_。课堂练习度哈夫曼树(Huffman)A2i+1叶子第47页/共55

16、页14、对于如图所示的森林 （1）将其转换为相应的二叉树；（2）写出该森林的先序遍历序列和中序遍历序列。A图题 14BCEFDGHIJKL课堂练习第48页/共55页【答案】ABCEFDGHIJKLABCEFDGHIJKL先序序列为：ABDEFCGHIJKL中序序列为：DEFBCAHIJGLK 课堂练习第49页/共55页15、已知一棵树的先根遍历序列为ABCED，后根遍历序列为BECDA，求对应的树。(分析)【分析】根据树与二叉树之间的转换关系，可知：树的先序序列=对应二叉树先序序列 树的后跟序列=对应二叉树中序序列 因此，可以先这两个序列构造对应的二叉树，再将 二叉树转换为树。课堂练习第50页

17、/共55页15、已知一棵树的先根遍历序列为ABCED，后根遍历序列为BECDA，求对应的树。(分析)【答案】ABCDEABCDE课堂练习第51页/共55页16、设电文中出现的字母为A、B、C、D和E，每个字母在 电文中出现的次数分别9、27、3、5、和11。按哈夫曼 编码，则C的编码为:(分析)A、10 B、110 C、1110 D、1111【分析】先构造哈夫曼树，再根据哈夫曼树进行编码。注意：在构造哈夫曼树时，应注意左右孩子的排列。课堂练习第52页/共55页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课堂练习第53页/共55页作业：6.26作业第54页/共55页感谢您的观看！第55页/共55页