数据结构导论第四章.ppt

《数据结构导论第四章.ppt》由会员分享，可在线阅读，更多相关《数据结构导论第四章.ppt（149页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、复习前节复习前节1 1、数据结构的基本概念、数据结构的基本概念2 2、顺序表、链表、顺序表、链表3 3、顺序栈、链栈、顺序栈、链栈4 4、顺序队、链队、顺序队、链队5 5、顺序串、链串、顺序串、链串6 6、数组和广义表、数组和广义表线性表线性表线性表的推广线性表的推广树的推广树的推广1 1第第4 4章章 树树4.1 4.1 树的基本概念树的基本概念4.2 4.2 二叉树二叉树4.3 4.3 二叉树的存储结构二叉树的存储结构4.4 4.4 二叉树的遍历二叉树的遍历4.5 4.5 递归消除递归消除4.6 4.6 树和林树和林4.7 4.7 判定树和哈夫曼树判定树和哈夫曼树2 2本章项目：本章项目：

2、本章项目：本章项目：电文编码电文编码电文编码电文编码3 3文字文字文字文字电文编码电文编码电文编码电文编码电波电波电波电波译码译码译码译码摩尔斯电码（又译为摩斯电码）是一种时通时断的信号代码，这种信号代摩尔斯电码（又译为摩斯电码）是一种时通时断的信号代码，这种信号代摩尔斯电码（又译为摩斯电码）是一种时通时断的信号代码，这种信号代摩尔斯电码（又译为摩斯电码）是一种时通时断的信号代码，这种信号代码通过不同的排列顺序来表达不同的英文字母、数字和标点符号等。它由码通过不同的排列顺序来表达不同的英文字母、数字和标点符号等。它由码通过不同的排列顺序来表达不同的英文字母、数字和标点符号等。它由码通过不同的排

3、列顺序来表达不同的英文字母、数字和标点符号等。它由美国人艾尔菲德美国人艾尔菲德美国人艾尔菲德美国人艾尔菲德维尔发明（维尔发明（维尔发明（维尔发明（1835183518351835年）。年）。年）。年）。4 4网络信息传输：网络信息传输：网络信息传输：网络信息传输：文字文字文字文字数字编码数字编码数字编码数字编码电电电电信信信信号号号号电文电文电文电文编码编码编码编码发送者发送者发送者发送者数字编码数字编码数字编码数字编码文字文字文字文字电文电文电文电文编码编码编码编码接收者接收者接收者接收者你好你好你好你好0101010101010101010101010101010101010101你好你好

4、你好你好核心问题：电文如何编码称为核心问题：电文如何编码称为核心问题：电文如何编码称为核心问题：电文如何编码称为01010101串？串？串？串？5 5本章项目：电文编码问题本章项目：电文编码问题本章项目：电文编码问题本章项目：电文编码问题涉及知识点：涉及知识点：涉及知识点：涉及知识点：1 1 1 1、树的概念、树的概念、树的概念、树的概念2 2 2 2、树的专业术语、树的专业术语、树的专业术语、树的专业术语3 3 3 3、二叉树的概念、二叉树的概念、二叉树的概念、二叉树的概念4 4 4 4、哈夫曼树和哈夫曼编码、哈夫曼树和哈夫曼编码、哈夫曼树和哈夫曼编码、哈夫曼树和哈夫曼编码核心问题：如何将电

5、报文字转换成可传送编码核心问题：如何将电报文字转换成可传送编码核心问题：如何将电报文字转换成可传送编码核心问题：如何将电报文字转换成可传送编码6 6自自然然中中的的树树抽抽象象的的树树知识点知识点1 1：树的概念：树的概念7 7旋转后旋转后8 8适当进行调整适当进行调整ABCDEFGHI9 9数据结构中树的形态，具有分层特点数据结构中树的形态，具有分层特点ABCDEFGHI1010某姓氏族谱某姓氏族谱1111ABCDEFGHIJKLMNOPQRSTUV WXY Z.对树中的结点给定一个符号名称，具有一对多的特点对树中的结点给定一个符号名称，具有一对多的特点1212树描述的是一种层次结构，树描述

6、的是一种层次结构，是一种一对多的逻辑关系是一种一对多的逻辑关系FGIJABCEDH1313树树树树(Tree)(Tree)(Tree)(Tree)是是是是n(n=0)n(n=0)n(n=0)n(n=0)个个个个结结结结点点点点的的的的有有有有限限限限集。集。集。集。n=0n=0n=0n=0时称为空树。时称为空树。时称为空树。时称为空树。n1n1n1n1时，时，时，时，有且仅有一个称为根的结点；有且仅有一个称为根的结点；有且仅有一个称为根的结点；有且仅有一个称为根的结点；其其其其余余余余结结结结点点点点可可可可分分分分为为为为m(m0)m(m0)m(m0)m(m0)个个个个互互互互不不不不相相相

7、相交交交交的的的的有有有有限限限限集集集集T1,T2,T1,T2,T1,T2,T1,T2,Tm,Tm,Tm,Tm,其其其其中中中中每每每每个个个个集集集集合又是一棵树，称为子树合又是一棵树，称为子树合又是一棵树，称为子树合又是一棵树，称为子树知识点知识点1 1：树的概念：树的概念FGIJABCEDH根根根根1414树树树树的的的的其其其其他他他他表表表表示示示示形形形形式式式式ABCDEFHGM1515n n结点：结点：结点：结点：数据元素的内容及其指向其子树根的分支数据元素的内容及其指向其子树根的分支数据元素的内容及其指向其子树根的分支数据元素的内容及其指向其子树根的分支n n结点的度结点的

8、度结点的度结点的度：结点拥有的子树的数目。结点拥有的子树的数目。结点拥有的子树的数目。结点拥有的子树的数目。n n树的度：树的度：树的度：树的度：树内各结点的度的最大值；树内各结点的度的最大值；树内各结点的度的最大值；树内各结点的度的最大值；知识点知识点2 2：树的专业术语：树的专业术语ABCDEFHGMA A A A、B B B B、C C C C、D D D D、E E E E、F F F F、G G G G、H H H H、M M M M均称为结点均称为结点均称为结点均称为结点A A A A 结点的度为结点的度为结点的度为结点的度为 2 2 2 2C C C C 结点的度为结点的度为结点

9、的度为结点的度为 3 3 3 3M M M M 结点的度为结点的度为结点的度为结点的度为 0 0 0 0树的度为树的度为树的度为树的度为3 3 3 31616n n叶子（终端结点），非终端结点：叶子（终端结点），非终端结点：叶子（终端结点），非终端结点：叶子（终端结点），非终端结点：度为度为度为度为0 0 0 0的结点称为的结点称为的结点称为的结点称为叶子结点；度不为叶子结点；度不为叶子结点；度不为叶子结点；度不为0 0 0 0的结点称为非终端结点。的结点称为非终端结点。的结点称为非终端结点。的结点称为非终端结点。ABCDEFHGM1717n n结结结结点点点点的的的的层层层层数数数数：树树树

10、树中中中中根根根根结结结结点点点点的的的的层层层层次次次次为为为为1 1 1 1，根根根根结结结结点点点点子子子子树树树树的的的的根为第根为第根为第根为第2 2 2 2层，以此类推。层，以此类推。层，以此类推。层，以此类推。n n树的高度（深度）：树的高度（深度）：树的高度（深度）：树的高度（深度）：树中所有结点层次的最大值树中所有结点层次的最大值树中所有结点层次的最大值树中所有结点层次的最大值ABCDEFHGM1818n n孩孩孩孩子子子子，双双双双亲亲亲亲，兄兄兄兄弟弟弟弟，堂堂堂堂兄兄兄兄：结结结结点点点点的的的的子子子子树树树树的的的的根根根根称称称称为为为为该该该该结结结结点点点点的

11、的的的孩孩孩孩子子子子；该该该该结结结结点点点点称称称称为为为为孩孩孩孩子子子子的的的的双双双双亲亲亲亲；同同同同一一一一个个个个双双双双亲亲亲亲的的的的孩孩孩孩子子子子之之之之间间间间互互互互称称称称兄兄兄兄弟弟弟弟；双双双双亲亲亲亲在在在在同同同同一一一一层层层层的的的的结结结结点点点点互互互互为为为为堂堂堂堂兄弟。兄弟。兄弟。兄弟。ABCDEFHGMA A A A是是是是B B B B、C C C C的双亲的双亲的双亲的双亲B B B B、C C C C是是是是A A A A的孩子的孩子的孩子的孩子B B B B、C C C C是兄弟关系是兄弟关系是兄弟关系是兄弟关系E E E E、F

12、F F F是堂兄弟关系是堂兄弟关系是堂兄弟关系是堂兄弟关系1919n n路路路路径径径径：若若若若树树树树中中中中存存存存在在在在一一一一个个个个序序序序列列列列k k k k1 1 1 1，k k k k2 2 2 2kkkkn n n n，使使使使得得得得k k k ki i i i是是是是k k k ki+1i+1i+1i+1的的的的双亲双亲双亲双亲，则称该结点序列为，则称该结点序列为，则称该结点序列为，则称该结点序列为k k k k1 1 1 1到到到到k k k kn n n n的一条的一条的一条的一条路径路径路径路径。n n路径长度：路径长度：路径长度：路径长度：这些节点经过的边的

13、条数这些节点经过的边的条数这些节点经过的边的条数这些节点经过的边的条数ABCDEFHGM序列：序列：序列：序列：A B D M EA B D M EA B D M EA B D M E序列：序列：序列：序列：A B D MA B D MA B D MA B D M序列：序列：序列：序列：A C FA C FA C FA C F是路径是路径是路径是路径非路径非路径非路径非路径是路径是路径是路径是路径2020n n子子子子孙孙孙孙，祖祖祖祖先先先先：以以以以某某某某结结结结点点点点为为为为根根根根的的的的子子子子树树树树中中中中的的的的所所所所有有有有结结结结点点点点都都都都被被被被称称称称为为为

14、为是是是是该该该该结结结结点点点点的的的的子子子子孙孙孙孙。从从从从根根根根结结结结点点点点到到到到该该该该结结结结点点点点路路路路径径径径上上上上的所有结点称为该结点的祖先。的所有结点称为该结点的祖先。的所有结点称为该结点的祖先。的所有结点称为该结点的祖先。ABCDEFHGM2121n n森林：森林：森林：森林：多棵互不相交的树的集合构成森林多棵互不相交的树的集合构成森林多棵互不相交的树的集合构成森林多棵互不相交的树的集合构成森林ABCDEFHGM三棵树构成的森林三棵树构成的森林三棵树构成的森林三棵树构成的森林2222n n结点结点结点结点n n结点的度结点的度结点的度结点的度(Degree

15、)(Degree)(Degree)(Degree)n n叶子（叶子（叶子（叶子（Leaf)Leaf)Leaf)Leaf)或终端结点或终端结点或终端结点或终端结点n n分支结点或非终端结点分支结点或非终端结点分支结点或非终端结点分支结点或非终端结点n n树的度树的度树的度树的度n n层次层次层次层次(Level)(Level)(Level)(Level)n n树的深度树的深度树的深度树的深度(Depth)(Depth)(Depth)(Depth)n n孩子（孩子（孩子（孩子（child)child)child)child)n n双亲（双亲（双亲（双亲（Parent)Parent)Parent)P

16、arent)n n兄弟兄弟兄弟兄弟(Sibling)(Sibling)(Sibling)(Sibling)n n祖先祖先祖先祖先n n子孙子孙子孙子孙n n路径路径路径路径ABCDEFHGM2323知识点知识点3 3：二叉树的概念二叉树的概念n n二叉树二叉树二叉树二叉树(Binary Tree)(Binary Tree)(Binary Tree)(Binary Tree)：n n或者是一棵空树，或者是一棵空树，或者是一棵空树，或者是一棵空树，n n或者是一棵由一个根结点和两棵互不相交的左子或者是一棵由一个根结点和两棵互不相交的左子或者是一棵由一个根结点和两棵互不相交的左子或者是一棵由一个根结

17、点和两棵互不相交的左子树和右子树所组成的非空树，树和右子树所组成的非空树，树和右子树所组成的非空树，树和右子树所组成的非空树，n n左子树和右子树同样也都是二叉树左子树和右子树同样也都是二叉树左子树和右子树同样也都是二叉树左子树和右子树同样也都是二叉树 ABCDEFHM2424n n特征：特征：特征：特征：每个结点最多只有两棵子树每个结点最多只有两棵子树每个结点最多只有两棵子树每个结点最多只有两棵子树 子树有左右之分，次序不能任意颠倒，只有一子树有左右之分，次序不能任意颠倒，只有一子树有左右之分，次序不能任意颠倒，只有一子树有左右之分，次序不能任意颠倒，只有一棵子树时也棵子树时也棵子树时也棵子

18、树时也必须分清是左子树还是右子树必须分清是左子树还是右子树必须分清是左子树还是右子树必须分清是左子树还是右子树ABCACB2525网络信息传输：网络信息传输：网络信息传输：网络信息传输：文字文字文字文字数字编码数字编码数字编码数字编码电电电电信信信信号号号号电文电文电文电文编码编码编码编码发送者发送者发送者发送者数字编码数字编码数字编码数字编码文字文字文字文字电文电文电文电文编码编码编码编码接收者接收者接收者接收者你好你好你好你好0101010101010101010101010101010101010101你好你好你好你好核心问题：电文如何编码称为核心问题：电文如何编码称为核心问题：电文如何

19、编码称为核心问题：电文如何编码称为01010101串？串？串？串？2626项目实现的进一步分析：项目实现的进一步分析：项目核心问题：项目核心问题：如何将电报文字转换成如何将电报文字转换成0101编码编码 扩展问题：扩展问题：电文传送时的高效性电文传送时的高效性2727扩展问题：扩展问题：电文传送时的高效性电文传送时的高效性在计算机及通信中，在计算机及通信中，常用二进制编码来表示字符，常用二进制编码来表示字符，假设某电文通信中只使用假设某电文通信中只使用A B C DA B C D四个字符四个字符每个字母用两位二进制数表示，例如每个字母用两位二进制数表示，例如传输传输100100个字母需要用个字

20、母需要用200200个二进制位个二进制位此种编码方式为等长编码，此种编码方式为等长编码，此时电文长度由电文字符数决定此时电文长度由电文字符数决定对于电文：对于电文：DABCDABC可翻译为编码：可翻译为编码：对于编码：对于编码：01 00 11 1001 00 11 10可准确翻译为：可准确翻译为：0000表示表示A A0101表示表示B B1010表示表示C C1111表示表示D DB A D CB A D C11 00 01 1011 00 01 102828实际情况：实际情况：字符在实际使用中出现频率不一样！字符在实际使用中出现频率不一样！新问题新问题1：如何让电文编码缩短如何让电文编码

21、缩短为提高电文传送效率，应让电文编码尽量短为提高电文传送效率，应让电文编码尽量短考虑问题：考虑问题：出现频率高的字符编码位数少出现频率高的字符编码位数少 出现频率低的字符编码位数多出现频率低的字符编码位数多 以此降低电文总长度以此降低电文总长度 常用汉字常用汉字63356335个，最常用字个，最常用字560560个，常个，常用字用字807807个，次常用字个，次常用字10331033个，共个，共24002400个。这些字占了书刊物汉字出现次数的个。这些字占了书刊物汉字出现次数的99%99%A 8.19 B 1.47 C 3.83 D 3.91A 8.19 B 1.47 C 3.83 D 3.9

22、1E 12.25 F 2.26 G 1.71 H 4.57 E 12.25 F 2.26 G 1.71 H 4.57 I 7.10 J 0.14 K 0.41 L 3.77 I 7.10 J 0.14 K 0.41 L 3.77 前面十位是：前面十位是：E T A O I N R S D CE T A O I N R S D C2929假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成且出现频率分别为：且出现频率分别为：000 01 1 001 000 000 01 1 001 000 考虑问题：考虑问题：出现频率高的字符编码位数少出现频率高的字符编码位数少

23、出现频率低的字符编码位数多出现频率低的字符编码位数多 以此降低电文总长度以此降低电文总长度 000000表示表示A A001001表示表示B B 01 01表示表示C C 1 1表示表示D DA 5%A 5%B 10%B 10%C 15%C 15%D 70%D 70%假定：假定：问题：问题：传输传输100100个字母所用的二个字母所用的二进制位为进制位为电文：电文：ACDBAACDBA翻译成编码：翻译成编码：编码：编码：000 01 1 001000 01 1 001翻译成电文翻译成电文:3 35 5+3 31010+2 215151 17070+=145145A C D BA C D B30

24、30此种编码方式为不等长编码，此种编码方式为不等长编码，采用不等长编码可缩短电文编码长度，采用不等长编码可缩短电文编码长度，从而提高电文传送效率从而提高电文传送效率假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成且出现频率分别为：且出现频率分别为：考虑问题：考虑问题：出现频率高的字符编码位数少出现频率高的字符编码位数少 出现频率低的字符编码位数多出现频率低的字符编码位数多 以此降低电文总长度以此降低电文总长度 000000表示表示A A001001表示表示B B 01 01表示表示C C 1 1表示表示D DA 5%A 5%B 10%B 10%C 15%C

25、15%D 70%D 70%假定：假定：3131假定：假定：翻译：翻译：C B D BC B D B翻译：翻译：C B D C DC B D C D新问题新问题2 2：随意的不等长编码可能导致编码翻译时出现歧义随意的不等长编码可能导致编码翻译时出现歧义编码：编码：000011001000011001问题：编码是任意给定的吗？问题：编码是任意给定的吗？000000表示表示A A 001001表示表示B B 00 00表示表示C C 1 1表示表示D D假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成且出现频率分别为：且出现频率分别为：A 5%A 5%B 10%B

26、 10%C 15%C 15%D 70%D 70%000 01 1 00 1000 01 1 00 100 001 1 00100 001 1 00100 001 1 00 100 001 1 00 1错误！错误！错误！错误！3232新知识：新知识：设计不等长编码时，必须做到：任何一个字符的编码设计不等长编码时，必须做到：任何一个字符的编码不能是另一个字符编码的前缀，这种编码为不能是另一个字符编码的前缀，这种编码为前缀码前缀码新问题新问题2 2：随意的不等长编码可能导致编码翻译时出现歧义随意的不等长编码可能导致编码翻译时出现歧义000000表示表示A A001001表示表示B B 01 01表示

27、表示C C 1 1表示表示D D我们设计的第一种编码我们设计的第一种编码是前缀码是前缀码新问题新问题3 3：如何设计前缀码：如何设计前缀码3333知识点知识点4：哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码树的路径长度：树的路径长度：树的路径长度：树的路径长度：n n树的根结点到树中每一个结点的路径长度之和。树的根结点到树中每一个结点的路径长度之和。树的根结点到树中每一个结点的路径长度之和。树的根结点到树中每一个结点的路径长度之和。结点的带权的路径长度：结点的带权的路径长度：结点的带权的路径长度：结点的带权的路径长度：n n该结点到根结点之间的路程长度与该结点上权的乘积该结点到根结点之间的路程长度

28、与该结点上权的乘积该结点到根结点之间的路程长度与该结点上权的乘积该结点到根结点之间的路程长度与该结点上权的乘积n n路路路路径径径径：若若若若树树树树中中中中存存存存在在在在一一一一个个个个序序序序列列列列k k k k1 1 1 1，k k k k2 2 2 2kkkkn n n n，使使使使得得得得k k k ki i i i是是是是k k k ki+1i+1i+1i+1的双亲，则称该结点序列为的双亲，则称该结点序列为的双亲，则称该结点序列为的双亲，则称该结点序列为k k k k1 1 1 1到到到到k k k kn n n n的一条路径。的一条路径。的一条路径。的一条路径。n n路径长度

29、：路径长度：路径长度：路径长度：这些节点经过的边的条数这些节点经过的边的条数这些节点经过的边的条数这些节点经过的边的条数3434知识点知识点4：哈夫曼树与哈夫曼编码哈夫曼树与哈夫曼编码树的路径长度：树的路径长度：树的路径长度：树的路径长度：n n树的根结点到树中每一个结点的路径长度之和。树的根结点到树中每一个结点的路径长度之和。树的根结点到树中每一个结点的路径长度之和。树的根结点到树中每一个结点的路径长度之和。结点的带权的路径长度：结点的带权的路径长度：结点的带权的路径长度：结点的带权的路径长度：n n该结点到根结点之间的路程长度与该结点上权的乘积该结点到根结点之间的路程长度与该结点上权的乘积

30、该结点到根结点之间的路程长度与该结点上权的乘积该结点到根结点之间的路程长度与该结点上权的乘积树的路径长度：树的路径长度：树的路径长度：树的路径长度：1+1+2+2+3+31+1+2+2+3+31+1+2+2+3+31+1+2+2+3+3结点结点结点结点a a a a的带权路径长度：的带权路径长度：的带权路径长度：的带权路径长度：7*37*37*37*3dcab24753535树的带权路径长度：树的带权路径长度：树的带权路径长度：树的带权路径长度：n n树中所有叶子结点的带权的路径长度的和。树中所有叶子结点的带权的路径长度的和。树中所有叶子结点的带权的路径长度的和。树中所有叶子结点的带权的路径长

31、度的和。n n通常记为：通常记为：通常记为：通常记为：WPL(Weighted Path Length)WPL(Weighted Path Length)WPL(Weighted Path Length)WPL(Weighted Path Length)。树的带权路径长度：树的带权路径长度：树的带权路径长度：树的带权路径长度：4*2+7*3+5*3+2*14*2+7*3+5*3+2*14*2+7*3+5*3+2*14*2+7*3+5*3+2*1dcab24753636树的带权路径长度：树的带权路径长度：树的带权路径长度：树的带权路径长度：n n树中所有叶子结点的带权的路径长度的和。树中所有叶子

32、结点的带权的路径长度的和。树中所有叶子结点的带权的路径长度的和。树中所有叶子结点的带权的路径长度的和。n n通常记为：通常记为：通常记为：通常记为：WPL(Weighted Path Length)WPL(Weighted Path Length)WPL(Weighted Path Length)WPL(Weighted Path Length)。n n由由由由n n n n个带权值的叶子结点构成的二叉树中，个带权值的叶子结点构成的二叉树中，个带权值的叶子结点构成的二叉树中，个带权值的叶子结点构成的二叉树中，WPLWPLWPLWPL最小的最小的最小的最小的二叉树称为二叉树称为二叉树称为二叉树称

33、为最优二叉树最优二叉树最优二叉树最优二叉树，或，或，或，或哈夫曼（哈夫曼（哈夫曼（哈夫曼（Huffman Huffman Huffman Huffman）树）树）树）树。WPL=4*2+7*3+5*3+2*1=46dcab24753737abcd7524WPL=7*2+5*2+2*2+4*2=36abcd7524WPL=7*1+5*2+2*3+4*3=35WPL=7*1+4*3+2*3+5*2=35abdc742538381 1 1 1、根据给定的、根据给定的、根据给定的、根据给定的n n n n个权值个权值个权值个权值 w w w w1 1 1 1,w,w,w,w2 2 2 2,w,w,w,

34、wn n n n ，构造构造构造构造n n n n棵只有棵只有棵只有棵只有根结点的二叉树，令其权值为根结点的二叉树，令其权值为根结点的二叉树，令其权值为根结点的二叉树，令其权值为w w w wj j j j;2 2 2 2、在森林中选取两棵根结点权值最小的树作左右子在森林中选取两棵根结点权值最小的树作左右子在森林中选取两棵根结点权值最小的树作左右子在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权树，构造一棵新的二叉树，置新二叉树根结点权树，构造一棵新的二叉树，置新二叉树根结点权树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和值为其左右子

35、树根结点权值之和值为其左右子树根结点权值之和值为其左右子树根结点权值之和;3 3 3 3、从、从、从、从森林中删除这两棵树，同时将新得到的二叉树森林中删除这两棵树，同时将新得到的二叉树森林中删除这两棵树，同时将新得到的二叉树森林中删除这两棵树，同时将新得到的二叉树加入森林中加入森林中加入森林中加入森林中;4 4 4 4、重复上述两步，直到重复上述两步，直到重复上述两步，直到重复上述两步，直到森林中森林中森林中森林中只含一棵树为止，这只含一棵树为止，这只含一棵树为止，这只含一棵树为止，这棵树即哈夫曼树棵树即哈夫曼树棵树即哈夫曼树棵树即哈夫曼树 。哈夫曼树的构造方法哈夫曼树的构造方法哈夫曼树的构造

36、方法哈夫曼树的构造方法39399例如例如:已知权值已知权值 W=5,6,2,9,7 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树5627第一步：把每个权值看作只有一个结点的树第一步：把每个权值看作只有一个结点的树40409例如例如:已知权值已知权值 W=5,6,2,9,7 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树5267第二步：取权值最小的两棵树，合并成，第二步：取权值最小的两棵树，合并成，新树的权值为两棵子树权值之和新树的权值为两棵子树权值之和741419例如例如:已知权值已知权值 W=5,6,2,9,7 W=5,6,2,9

37、,7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树5267第三步：从森林中去掉被合并的结点，并将新第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树二步，直到森林合并成为一棵树742429例如例如:已知权值已知权值 W=5,6,2,9,7 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树5267713第三步：从森林中去掉被合并的结点，并将新第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树二步，直

38、到森林合并成为一棵树43439例如例如:已知权值已知权值 W=5,6,2,9,7 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树526771316第三步：从森林中去掉被合并的结点，并将新第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树二步，直到森林合并成为一棵树44449例如例如:已知权值已知权值 W=5,6,2,9,7 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树526771316第三步：从森林中去掉被合并的结点，并将新第三步：从森林中去掉被合并的

39、结点，并将新合并的树加入到森林中，继续执行第合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树二步，直到森林合并成为一棵树45459例如例如:已知权值已知权值 W=5,6,2,9,7 W=5,6,2,9,7 构造以权值为叶子的哈夫曼树构造以权值为叶子的哈夫曼树52677131629第三步：从森林中去掉被合并的结点，并将新第三步：从森林中去掉被合并的结点，并将新合并的树加入到森林中，继续执行第合并的树加入到森林中，继续执行第二步，直到森林合并成为一棵树二步，直到森林合并成为一棵树构造完成构造完成4646设计电文编码时，设计电文编码时，随意的不等长编码可能导致编码翻译时出现歧义随意的不等

40、长编码可能导致编码翻译时出现歧义使用前缀码，可解决不等长编码出现的歧义使用前缀码，可解决不等长编码出现的歧义利用哈夫曼树可构造前缀码利用哈夫曼树可构造前缀码构造方法：构造方法：1 1，将字符集中的每个字符作为节点，将字符集中的每个字符作为节点2 2，每个字符的出现频率作为节点的权值，每个字符的出现频率作为节点的权值3 3，构造哈夫曼树，构造哈夫曼树4 4，令哈夫曼树中的左分支为，令哈夫曼树中的左分支为0 0，右分支为，右分支为1 1 从根到叶子节点的从根到叶子节点的0101序列即为叶子节点的编码序列即为叶子节点的编码4747假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构

41、成四个字符构成且出现频率分别为：且出现频率分别为：A 5%B 10%C 15%D 70%A 5%B 10%C 15%D 70%0.050.10.150.74848假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成且出现频率分别为：且出现频率分别为：A 5%B 10%C 15%D 70%A 5%B 10%C 15%D 70%0.050.10.150.70.154949假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成且出现频率分别为：且出现频率分别为：A 5%B 10%C 15%D 70%A 5%B 10%C 15%D 70%0

42、.050.10.150.70.150.35050假定：假定：某电文通信中只由某电文通信中只由ABCDABCD四个字符构成四个字符构成且出现频率分别为：且出现频率分别为：A 5%B 10%C 15%D 70%A 5%B 10%C 15%D 70%0.050.10.150.70.150.31A AB BC CD D0 01 10 01 10 01 1A A的编码：的编码：000000B B的编码：的编码：001001C C的编码：的编码：01 01D D的编码：的编码：1 1电文：电文：D A B C D A B C编码：编码：1 000 001 01 1 000 001 01每个字符的编码都不是

43、每个字符的编码都不是另一字符编码的前缀另一字符编码的前缀5151项目完成，总结：项目完成，总结：项目完成，总结：项目完成，总结：1 1 1 1，树的概念，树的概念，树的概念，树的概念2 2 2 2，专业术语的定义，专业术语的定义，专业术语的定义，专业术语的定义3 3 3 3，二叉树的概念，二叉树的概念，二叉树的概念，二叉树的概念4 4 4 4，哈夫曼树和哈夫曼编码，哈夫曼树和哈夫曼编码，哈夫曼树和哈夫曼编码，哈夫曼树和哈夫曼编码下节内容：下节内容：下节内容：下节内容：1 1 1 1，二叉树的性质，二叉树的性质，二叉树的性质，二叉树的性质2 2 2 2，二叉树基本操作，二叉树基本操作，二叉树基本

44、操作，二叉树基本操作3 3 3 3，二叉树的应用，二叉树的应用，二叉树的应用，二叉树的应用作业：作业：作业：作业：P99 6.21P99 6.21P99 6.21P99 6.215252n(n0)n(n0)个结点的树的高度个结点的树的高度:最低是多少？最高是多少？最低是多少？最高是多少？答案：答案：1 1，n n练习练习练习练习ABD5353答案：答案：一棵树应满足下列条件：一棵树应满足下列条件：（1 1）有有且且仅仅有有一一个个结结点点没没有有前前驱驱（双双亲亲）,称称该该结结点为树根点为树根;（2 2）除除根根结结点点以以外外,其其余余每每个个结结点点有有且且仅仅有有一一个个直直接前驱接前

45、驱;（3 3）树中每个结点可以有多个直接后继）树中每个结点可以有多个直接后继(孩子结点孩子结点)。判断判断判断判断54541 1、哈夫曼树只有度为哈夫曼树只有度为哈夫曼树只有度为哈夫曼树只有度为0 0 0 0和和和和2 2 2 2的结点，无度为的结点，无度为的结点，无度为的结点，无度为1 1 1 1的结点；的结点；的结点；的结点；2 2 2 2、n n n n个叶子的哈夫曼树的形态一般不唯一，但个叶子的哈夫曼树的形态一般不唯一，但个叶子的哈夫曼树的形态一般不唯一，但个叶子的哈夫曼树的形态一般不唯一，但WPLWPLWPLWPL是相是相是相是相同的；同的；同的；同的；3 3 3 3、n n n n

46、个叶子的哈夫曼树共有个叶子的哈夫曼树共有个叶子的哈夫曼树共有个叶子的哈夫曼树共有2n-12n-12n-12n-1个结点。个结点。个结点。个结点。判断判断判断判断答案：正确答案：正确答案：正确答案：正确55550.10.20.301练习：练习：假设有字符集假设有字符集AA，B B，C C，DD其在电文中的使用频率分别为其在电文中的使用频率分别为0.10.1，0.40.4，0.30.3，0.20.2请给出该字符集中每个字符的哈夫曼编码请给出该字符集中每个字符的哈夫曼编码并将并将AABCDDAABCDD电文翻译为哈夫曼编码电文翻译为哈夫曼编码0.30.6010.4101ADCB编码：编码：A 100

47、B 0C 11D 101AABBCDD翻译：翻译：1000011101101565620092009年年1010月考题：月考题：2727、由字符集、由字符集ss，t t，a a，e e，II及其在电文中出现的及其在电文中出现的频度构建的哈夫曼树如图所示。已知某段电文的哈夫频度构建的哈夫曼树如图所示。已知某段电文的哈夫曼编码为曼编码为111000010100111000010100，请根据该哈夫曼树进行译码，请根据该哈夫曼树进行译码，写出原来的电文。写出原来的电文。57574.2 4.2 4.2 4.2 二叉树二叉树二叉树二叉树n n二叉树二叉树二叉树二叉树(Binary Tree)(Binar

48、y Tree)(Binary Tree)(Binary Tree)：n n或者是一棵空树，或者是一棵空树，或者是一棵空树，或者是一棵空树，n n或者是一棵由一个根结点和两棵互不相交的左子或者是一棵由一个根结点和两棵互不相交的左子或者是一棵由一个根结点和两棵互不相交的左子或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，树和右子树所组成的非空树，树和右子树所组成的非空树，树和右子树所组成的非空树，n n左子树和右子树同样也都是二叉树左子树和右子树同样也都是二叉树左子树和右子树同样也都是二叉树左子树和右子树同样也都是二叉树 123456789 10 11 12 13 14 155

49、858n n特征：特征：特征：特征：每个结点最多只有两棵子树每个结点最多只有两棵子树每个结点最多只有两棵子树每个结点最多只有两棵子树 子树有左右之分，其次序不能任意颠倒，只有子树有左右之分，其次序不能任意颠倒，只有子树有左右之分，其次序不能任意颠倒，只有子树有左右之分，其次序不能任意颠倒，只有一棵子树时也必须分清是左、右子树。一棵子树时也必须分清是左、右子树。一棵子树时也必须分清是左、右子树。一棵子树时也必须分清是左、右子树。ACBABC5959二叉树的五种形态(a)(a)(b)(b)(c)(c)(d)(d)(e)(e)6060（1 1 1 1）初始化）初始化）初始化）初始化 INITIATE

50、(BT)INITIATE(BT)INITIATE(BT)INITIATE(BT)（2 2 2 2）求根）求根）求根）求根 ROOT(BT)ROOT(BT)ROOT(BT)ROOT(BT)（3 3 3 3）求双亲）求双亲）求双亲）求双亲 PARENT(BT,x)PARENT(BT,x)PARENT(BT,x)PARENT(BT,x)（4 4 4 4）求左孩子、右孩子）求左孩子、右孩子）求左孩子、右孩子）求左孩子、右孩子Child(BT,x),RChild(BT,x)Child(BT,x),RChild(BT,x)Child(BT,x),RChild(BT,x)Child(BT,x),RChild