第5章树与二叉树(java版)

1、第五章第五章 树与二叉树树与二叉树第五章第五章 树树 与与 二二 叉叉 树树5.2 二叉树的基本概念二叉树的基本概念5.1 树的基本概念树的基本概念5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.3 二叉树的遍历二叉树的遍历5.5 树与森林树与森林第五章第五章 树树 与与 二二 叉叉 树树重点：重点：u二叉树的性质；二叉树的性质；u二叉树的存储方法二叉树的存储方法u二叉树的遍历及其应用二叉树的遍历及其应用u哈夫曼编码哈夫曼编码难点：难点：u二叉树遍历算法的应用二叉树遍历算法的应用第五章第五章 树树 与与 二二 叉叉 树树 你见过家族谱系图吗？试以图形表示你见过家族谱系图吗？试以图形表示从你

2、的祖父起的家族成员关系。从你的祖父起的家族成员关系。祖父祖父伯父伯父父亲父亲叔父叔父堂兄堂兄堂姐堂姐你你侄儿侄儿堂弟堂弟5.1 树的基本概念树的基本概念5.1.2 5.1.2 树的常用术语树的常用术语5.1 5.1 树的基本概念树的基本概念5.1 树的基本概念树的基本概念 树树是由是由n n（n0n0）个结点所构成的）个结点所构成的有限集合，当有限集合，当n=0n=0时，称为时，称为空树空树；当；当n0n0时，时，n n个结点满足以下条件：个结点满足以下条件： 有且仅有一个称为有且仅有一个称为根根的结点。的结点。 其余结点可分为其余结点可分为m m（m0m0）个）个互不相交的有限集合，且每一个

3、集合互不相交的有限集合，且每一个集合又构成一棵树，这棵树称为是又构成一棵树，这棵树称为是根结点根结点的子树的子树。5.1 树的基本概念树的基本概念ABCDEFGHIJMKL例如例如: :rootT1T2T35.1 树的基本概念树的基本概念树形表示法树形表示法文氏图表示法文氏图表示法凹入图表示法凹入图表示法广义表广义表( (括号括号) )表示法表示法ABCDEFGHIJMKL树形表示法树形表示法5.1 树的基本概念树的基本概念ABCDEFGHIJMKL树形表示法树形表示法EKFBDCJLGMIH文氏图表示法文氏图表示法A5.1 树的基本概念树的基本概念ABCDEFGHIJMKL树形表示法树形表示

4、法凹入图表示法凹入图表示法ABCDEFKLGIHJM5.1 树的基本概念树的基本概念ABCDEFGHIJMKL树形表示法树形表示法广义表广义表(括号括号)表示法表示法:（A,B(E,F(K,L),C(G),D(H,I,J(M)5.1 树的基本概念树的基本概念线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 ( (无前驱无前驱) ) 存在一个根结点存在一个根结点 ( (无前驱无前驱) )最后一个数据元素最后一个数据元素 (无后继无后继)存在多个叶子结点存在多个叶子结点 ( (无后继无后继) )其它数据元素其它数据元素( (一个前驱、一个前驱、 一个后继一个后继) )其它结点其它结点(

5、 (一个前驱一个前驱( (双亲双亲) )、 多个后继多个后继( (孩子孩子)元素之间存在元素之间存在“一一对一对一”的关系的关系元素之间存在元素之间存在“一对一对多多”的关系的关系5.1 树的基本概念树的基本概念5.1.2 5.1.2 树的常用术语树的常用术语5.1 5.1 树的基本概念树的基本概念5.1 树的基本概念树的基本概念结点结点: :结点的度结点的度: :树的度树的度: :叶子结点叶子结点: :分支结点分支结点: :数据元素数据元素+ +所有关联子树根的分支所有关联子树根的分支结点所拥有子树的数目结点所拥有子树的数目树中所有结点的度的最大值树中所有结点的度的最大值度为零的结点度为零的

6、结点度大于零的结点度大于零的结点DHIJM分支分支: :根和子树根之间的连线根和子树根之间的连线( (边边) )结点的路径结点的路径: :由从根到该结点所经分支和结点构成由从根到该结点所经分支和结点构成5.1 树的基本概念树的基本概念孩子孩子结点、双亲双亲结点兄弟兄弟结点、堂兄弟堂兄弟祖先祖先结点、子孙子孙结点结点的层次结点的层次: :树的深度：树的深度：树中所有结点层次数的最大值加树中所有结点层次数的最大值加1 1。ABCDEFGHIJMKL 假设根结点的层次为假设根结点的层次为0 0，则其它结点，则其它结点的层次是其双亲结点的层次数加的层次是其双亲结点的层次数加1 1。有序树：有序树： 树

7、中各结点的所有子树之间从左到右树中各结点的所有子树之间从左到右有严格的次序关系。有严格的次序关系。5.1 树的基本概念树的基本概念无序树无序树: :森林：森林： 由由m m（m m0 0）棵互不相交的树所构）棵互不相交的树所构成的集合。成的集合。 与有序树相反，无序树是指树中各与有序树相反，无序树是指树中各结点的所有子树之间没有严格的次序关结点的所有子树之间没有严格的次序关系。系。BCDEFGHIJMKL5.2 二叉树的基本概念二叉树的基本概念5.2.2 5.2.2 二叉树的性质二叉树的性质5.2.3 5.2.3 二叉树的存储结构二叉树的存储结构5.2 5.2 二叉树的基本概念二叉树的基本概念

8、5.2 二叉树的基本概念二叉树的基本概念 二叉树或为空树空树，或是由一个根结点根结点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二二叉树叉树组成。ABCDEFGHK根结点根结点左子树左子树右子树右子树5.2 二叉树的基本概念二叉树的基本概念N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子树均左右子树均不为空树不为空树5.2 二叉树的基本概念二叉树的基本概念 具有具有3 3个结点的树与二叉树的个结点的树与二叉树的形态各有多少种形态各有多少种? ?问问 二叉树就是度小于等于二叉树就是度小于等于2 2的树，这个结论是否正确？的树，这个

9、结论是否正确？5.2 二叉树的基本概念二叉树的基本概念 如果在一棵二叉树中，它的所有结点如果在一棵二叉树中，它的所有结点或或者是叶结点者是叶结点，或者是左、右子树都非空或者是左、右子树都非空，并且，并且所有叶结点都在同一层上所有叶结点都在同一层上，则称这棵二叉树为，则称这棵二叉树为满二叉树满二叉树 。012345678910 11 12 13 145.2 二叉树的基本概念二叉树的基本概念 如果在一棵具有如果在一棵具有n n个结点的二叉树中，它的个结点的二叉树中，它的逻辑结构与满二叉树的前逻辑结构与满二叉树的前n n个结点的逻辑结构相个结点的逻辑结构相同同，则称这样的二叉树为完全二叉树，则称这样

10、的二叉树为完全二叉树 01234567 890123456789完全二叉树完全二叉树非非完全二叉树完全二叉树5.2 二叉树的基本概念二叉树的基本概念左支树左支树右支树右支树所有所有结点都结点都没没有有右右孩子的二叉树。孩子的二叉树。 所有所有结点都结点都没没有有左左孩子的二叉树。孩子的二叉树。ABCDABCD5.2 二叉树的基本概念二叉树的基本概念5.2.2 5.2.2 二叉树的性质二叉树的性质5.2.3 5.2.3 二叉树的存储结构二叉树的存储结构5.2 5.2 二叉树的基本概念二叉树的基本概念5.2 二叉树的基本概念二叉树的基本概念在二叉树的第在二叉树的第 i i 层上至多有层上至多有2

11、2i i 个结个结点。点。(i0)(i0)用归纳法证明：用归纳法证明： 归纳基：归纳基： 归纳假设：归纳假设： 归纳证明：归纳证明：i = 0 层时，只有一个根结点：层时，只有一个根结点：20 = 1；假设对所有的假设对所有的 j(0ji)层层，命，命题成立；题成立；则第则第 i层的结点数层的结点数 2i-1 2 = 2i。5.2 二叉树的基本概念二叉树的基本概念 深度为深度为 h h （h1h1）的二叉树上至）的二叉树上至多含多含 个结点。个结点。 基于上一条性质，深度为基于上一条性质，深度为 h h 的二叉的二叉树上的结点数至多为树上的结点数至多为: : 2 20 0+2+21 1+ +

12、+2 +2h-1h-1 = 2 = 2h h-1-1 。5.2 二叉树的基本概念二叉树的基本概念 对于任何一棵二叉树，若其叶结点对于任何一棵二叉树，若其叶结点的个数为的个数为n n0 0 ，度为，度为2 2的结点个数为的结点个数为n n2 2，则有则有 。则则 二叉树上结点总数 n = 二叉树上分支总数 e = n0 + n1 + n2而而 e与与 n的关系如何？的关系如何？n1+2n2由此得，由此得， n0 = n2 + 1 。设度为1的结点数为n1 e= n-15.2 二叉树的基本概念二叉树的基本概念 度为度为m m的树中，叶子结点数与其的树中，叶子结点数与其它结点数之间的关系如何？它结点

13、数之间的关系如何？思考思考5.2 二叉树的基本概念二叉树的基本概念具有具有 n n 个结点的完全二叉树的个结点的完全二叉树的深度深度为为 或或 loglog2 2(n(n+ +1)1) 。 设设完全二叉树的深度为 h , 则根据第二条性质得 2h-1-1 n 2h -1即2h-1 n 2h ,h-1 log2 n rDepth ? lDepth : rDepth);3. 求二叉树的深度求二叉树的深度5.3 二叉树的遍历二叉树的遍历5.3.2 5.3.2 二叉树的遍历应用举例二叉树的遍历应用举例1. 在二叉树上的查找某个结点在二叉树上的查找某个结点2. 计算二叉树中结点的个数计算二叉树中结点的个

14、数3. 求二叉树的深度求二叉树的深度4.4.判断两棵二叉树是否相等判断两棵二叉树是否相等5.3 二叉树的遍历二叉树的遍历要求：要求：实现方法实现方法: : 判断根结点为判断根结点为T1T1、T2T2的两棵二叉树是否相的两棵二叉树是否相等，若相等，则返回等，若相等，则返回truetrue；否则，返回；否则，返回falsefalse。 因为一棵二叉树由根、左子树和右子树三因为一棵二叉树由根、左子树和右子树三个部分组成，所以只有当两棵二叉树的三个组个部分组成，所以只有当两棵二叉树的三个组成部分都对应相等时，这两棵树才相等。而左、成部分都对应相等时，这两棵树才相等。而左、右子树的相等判断可以用对二叉树

15、相等判断的右子树的相等判断可以用对二叉树相等判断的同样方法来实现，即可用递归调用来实现。同样方法来实现，即可用递归调用来实现。4.4.判断两棵二叉树是否相等判断两棵二叉树是否相等 所以，可利用所以，可利用先先根、根、中中根、和根、和后后根遍历中根遍历中的的任何一种任何一种算法思想来实现。算法思想来实现。5.3 二叉树的遍历二叉树的遍历实现步骤实现步骤:(:(以中根遍历为例以中根遍历为例) ) 1) 1)若两棵二叉树若两棵二叉树都为空都为空，则两棵二叉树相，则两棵二叉树相等，返回等，返回true;true; 2)2)若两棵二叉树若两棵二叉树都非空都非空，则：，则：3)3)其它任何情况都返回其它任

16、何情况都返回falsefalse。若左子树相等，则继续判断它们的若左子树相等，则继续判断它们的根根结点结点是否相等是否相等，即转，即转 ；若根结点的值相等，则继续判断它们若根结点的值相等，则继续判断它们的右子树是否相等，即转的右子树是否相等，即转 ；若右子树也相等，则两棵二叉树若右子树也相等，则两棵二叉树相等，返回相等，返回true;true;4.4.判断两棵二叉树是否相等判断两棵二叉树是否相等5.3 二叉树的遍历二叉树的遍历实现算法实现算法( (书书P168P168算法算法5.12)5.12)：public boolean (BiTreeNode T1, BiTreeNode T2) if

17、(T1=null&T2=null) return true;if (T1!=null&T2!=null) if (isEqual(T1.getLchild(),T2.getLchild()if (T1.getData().equals(T2.getData()4.4.判断两棵二叉树是否相等判断两棵二叉树是否相等if (isEqual(T1.getRchild(),T2.getRchild() return true; return false;5.3 二叉树的遍历二叉树的遍历5.3.1 5.3.1 二叉树的遍历方法及其实现二叉树的遍历方法及其实现5.3.2 5.3.2 二叉树遍历算法的应用举例

18、二叉树遍历算法的应用举例5.3.3 5.3.3 建立二叉树建立二叉树5.3 5.3 二叉树的遍历二叉树的遍历5.3 二叉树的遍历二叉树的遍历5.3.3 5.3.3 建立二叉树建立二叉树 ( (二叉链式二叉链式存储结构存储结构) )3. 3. 由标明空子树的先根遍历序列建由标明空子树的先根遍历序列建 二叉树二叉树1. 1. 由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树2. 2. 由后根和中根遍历序列建二叉树由后根和中根遍历序列建二叉树4. 4. 由完全二叉树的顺序存储结构建由完全二叉树的顺序存储结构建 立二叉链式存储结构立二叉链式存储结构5.3 二叉树的遍历二叉树的遍历1. 由先根和

19、中根遍历序列建二叉树由先根和中根遍历序列建二叉树 仅知二叉树的先序序列仅知二叉树的先序序列“abcdefg” 不不能唯一确定一棵二叉树，能唯一确定一棵二叉树， 如果同时已知二叉树的中序序列如果同时已知二叉树的中序序列“cbdaegf”，则会如何？，则会如何？ 二叉树的先序序列二叉树的先序序列二叉树的中序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根5.3 二叉树的遍历二叉树的遍历1. 由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树a b c d e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列先序序

20、列中序序列中序序列5.3 二叉树的遍历二叉树的遍历1. 由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树-算法算法建立一棵二叉树的过程如下：建立一棵二叉树的过程如下： 5.3 二叉树的遍历二叉树的遍历其中：其中：preOrder是整棵树的先根遍历序列；是整棵树的先根遍历序列；inOrder是整棵树的中根遍历序列；是整棵树的中根遍历序列；reIndex是先根遍历序列在是先根遍历序列在preOrder中的开始位置中的开始位置;inIndex是中根遍历序列在是中根遍历序列在inOrder中的开始位置中的开始位置;count表示树中结点的个数。表示树中结点的个数。 1. 由先根和中根遍历序列建

21、二叉树由先根和中根遍历序列建二叉树- 算法算法实现方法：实现方法：引入引入5 5个参数：个参数：preOrder、inOrder、preIndex、inIndex和和count。5.3 二叉树的遍历二叉树的遍历1. 由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树-算法算法public BiTree(String preOrder, String inOrder, int preIndex, int inIndex,int count) if (count 0) char r = preOrder.charAt(preIndex); for (int i=0; i count; i+)

22、 if (r = inOrder.charAt( i + inIndex ) break;root = new BiTreeNode(r); root.setLchild( new BiTree (preOrder, inOrder, preIndex + 1, inIndex,i) .root ); root.setRchild( new BiTree (preOrder, inOrder, preIndex + i + 1, inIndex + i + 1, count - i - 1) .root ); P170/算法算法5.135.3 二叉树的遍历二叉树的遍历5.3.3 5.3.3 建

23、立二叉树建立二叉树 ( (二叉链式二叉链式存储结构存储结构) )3. 3. 由标明空子树的先根遍历序列建由标明空子树的先根遍历序列建 二叉树二叉树1. 1. 由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树2. 2. 由后根和中根遍历序列建二叉树由后根和中根遍历序列建二叉树4. 4. 由完全二叉树的顺序存储结构建由完全二叉树的顺序存储结构建 立二叉链式存储结构立二叉链式存储结构5.3 二叉树的遍历二叉树的遍历2. 由后根和中根遍历序列建二叉树由后根和中根遍历序列建二叉树二叉树的后序序列二叉树的后序序列二叉树的中序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根

24、根根问：问：由二叉树的前序和后序序列是否由二叉树的前序和后序序列是否也可以唯一确定一棵树？也可以唯一确定一棵树？5.3 二叉树的遍历二叉树的遍历2. 由后根和中根遍历序列建二叉树由后根和中根遍历序列建二叉树 由二叉树的前序和后序序列由二叉树的前序和后序序列不可以不可以唯一确定一棵树唯一确定一棵树 如下二棵树：如下二棵树：ABAB 其其前序前序遍历序列都为：遍历序列都为：A B 其其后序后序遍历序列都为：遍历序列都为：B A5.3 二叉树的遍历二叉树的遍历2. 由后根和中根遍历序列建二叉树由后根和中根遍历序列建二叉树-算法算法学生可依照算法学生可依照算法5.135.13自行完成！自行完成！略略5

25、.3 二叉树的遍历二叉树的遍历5.3.3 5.3.3 建立二叉树建立二叉树 ( (二叉链式二叉链式存储结构存储结构) )3. 3. 由标明空子树的先根遍历序列建由标明空子树的先根遍历序列建 二叉树二叉树1. 1. 由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树2. 2. 由后根和中根遍历序列建二叉树由后根和中根遍历序列建二叉树4. 4. 由完全二叉树的顺序存储结构建由完全二叉树的顺序存储结构建 立二叉链式存储结构立二叉链式存储结构5.3 二叉树的遍历二叉树的遍历3.由标明空子树的先根遍历序列建由标明空子树的先根遍历序列建 二叉树二叉树以字符以字符“# #”表示表示ABCDAB # #

26、 C # # # # D # # #A以下列字符串表示以下列字符串表示 标明空子树的先根遍历序列就是在标明空子树的先根遍历序列就是在先根遍历序列中先根遍历序列中加入空树加入空树信息。信息。以字符串以字符串“A#”表示表示5.3 二叉树的遍历二叉树的遍历3.由标明空子树的先根遍历序列建由标明空子树的先根遍历序列建 二叉树二叉树 在完整先根遍历数据输入正确的在完整先根遍历数据输入正确的前提下，由此建立二叉链表的算法为：前提下，由此建立二叉链表的算法为：若若读入的字符是读入的字符是# #，则，则建立空树建立空树；否则否则建立根结点；建立根结点；递归建立左子树的二叉链表；递归建立左子树的二叉链表；递归

27、建立右子树的二叉链表。递归建立右子树的二叉链表。5.3 二叉树的遍历二叉树的遍历3.由标明空子树的先根遍历序列建由标明空子树的先根遍历序列建 二叉树二叉树public BiTree(String preStr) / 算法5.14结束P172/算法算法5.14private int index=0; /用于记从用于记从preStr中取字符的位置中取字符的位置char c=preStr.charAt( index+ );if (c != #) else root = new BiTreeNode(c); /建立树的根结点建立树的根结点root.setLchild(new BiTree(preStr

28、).root); / / 建立树的左子树建立树的左子树root.setRchild(new BiTree(preStr).root); / / 建立树的右子树建立树的右子树 root = null; 5.3 二叉树的遍历二叉树的遍历5.3.3 5.3.3 建立二叉树建立二叉树 ( (二叉链式二叉链式存储结构存储结构) )3. 3. 由标明空子树的先根遍历序列建由标明空子树的先根遍历序列建 二叉树二叉树1. 1. 由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树2. 2. 由后根和中根遍历序列建二叉树由后根和中根遍历序列建二叉树4. 4. 由完全二叉树的顺序存储结构建由完全二叉树的顺序存

29、储结构建 立二叉链式存储结构立二叉链式存储结构5.3 二叉树的遍历二叉树的遍历4. 4.由完全二叉树的顺序存储结构建立二叉链式存储结构由完全二叉树的顺序存储结构建立二叉链式存储结构完全二叉树：完全二叉树：其对应的顺序存储结构：其对应的顺序存储结构：右孩子的编号为右孩子的编号为 由二叉树的性质由二叉树的性质5 5可可知，知，结点编号规则：结点编号规则：根结点的编号为根结点的编号为？0编号为编号为 i i的结点其左的结点其左孩子的编号为孩子的编号为 ？2i+1？2i+25.3 二叉树的遍历二叉树的遍历4. 4.由完全二叉树的顺序存储结构建立二叉链式存储结构由完全二叉树的顺序存储结构建立二叉链式存储

30、结构public BiTreeNode createBiTree(String sqBiTree,int index) P173/Exam5_7中中BiTreeNode root=null;if (indexsqBitree .length() root = new BiTreeNode(sqBiTree.charAt(index); root.setLchild(creatBiTree(sqBiTree,2*i+1); / / 建立树的左子树建立树的左子树root.setRchild(creatBiTree(sqBiTree,2*i+2); / / 建立树的右子树建立树的右子树 return

31、 root; 算法：算法：5.3 二叉树的遍历二叉树的遍历作业作业1 1：习题五中的习题五中的 三、三、1，2 附加题如下：5.3 二叉树的遍历二叉树的遍历1. 1. 已知一棵度为已知一棵度为m m的树中有的树中有n n1 1个度为个度为1 1 的结点，的结点，n n2 2个度为个度为2 2的结点，的结点，n nm m个度为个度为m m的结点，问该的结点，问该树中有多少片叶子？树中有多少片叶子？2.2.试采用顺序存储方法和二叉链式存储方法分试采用顺序存储方法和二叉链式存储方法分别画出下图所示的二叉树的存储结构。别画出下图所示的二叉树的存储结构。BDGFHAEC附加题：附加题：5.3 二叉树的遍

32、历二叉树的遍历附加题：附加题：3. 3. 分别写出题分别写出题2 2中二叉树的先根、中根和后序中二叉树的先根、中根和后序根遍历序列。根遍历序列。4. 4. 已知一棵树二叉树的后根遍历和中根遍历的已知一棵树二叉树的后根遍历和中根遍历的序列分别为：序列分别为：A C D B G I H F EA C D B G I H F E和和A B C D E A B C D E F G H IF G H I，请画出该二叉树，并写出它的先根遍，请画出该二叉树，并写出它的先根遍历的序列。历的序列。5. 5. 已知一棵树二叉树的先根遍历和中根遍历的已知一棵树二叉树的先根遍历和中根遍历的序列分别为：序列分别为：A

33、B D G H C E F IA B D G H C E F I和和G D H B A G D H B A E C I FE C I F，请画出此二叉树，并写出它的后根遍，请画出此二叉树，并写出它的后根遍的序列。的序列。5.3 二叉树的遍历二叉树的遍历1.1.已知一棵度为已知一棵度为m m的树中有的树中有n n1 1个度为个度为1 1的结点，的结点，n n2 2个度结点，个度结点，n nm m个度为个度为m m的结点，问该树中有的结点，问该树中有多少片叶子？多少片叶子？解：设树的总结点个数为解：设树的总结点个数为n, n, 叶子结点的个数为叶子结点的个数为n n0 0，则则 n= n n= n

34、0 0 + n + n1 1 + n + n2 2 + n + nm m (1)(1) 又因为树的总分支数为又因为树的总分支数为 n-1,n-1,且且 n-1= nn-1= n1 1 + n + n2 2 * *2+ n2+ n3 3 * *3+ n3+ nm m* *m (2)m (2) (1)-(2) (1)-(2)得得 1= n1= n0 0n n1 1 -2 n -2 n2 2 - - - -（m-1) nm-1) nm m 则：则： n n0 0 = 1 + n = 1 + n2 2+2 n+2 n3 3+(m-1) n+(m-1) nm m附加题解答：附加题解答：5.3 二叉树的遍

35、历二叉树的遍历2.2.试采用顺序存储方法和二叉链式存储方法分试采用顺序存储方法和二叉链式存储方法分别画出下图所示的二叉树的存储结构。别画出下图所示的二叉树的存储结构。 D C B H G F E AT A B C D E F G H 0 1 2 3 4 5 6 7 8 9 10 11 12 13二叉链式存储结构：二叉链式存储结构：顺序存储结构：顺序存储结构：附加题解答：附加题解答：5.3 二叉树的遍历二叉树的遍历3.3.分别写出题分别写出题2 2中二叉树的先根、中根和后序根中二叉树的先根、中根和后序根遍历序列。遍历序列。BDGFHAEC前根序列：前根序列：ABDEGCFHABDEGCFH中根序

36、列：中根序列：DBGEACHFDBGEACHF后根序列：后根序列：DGEBHFCADGEBHFCA附加题解答：附加题解答：5.3 二叉树的遍历二叉树的遍历4. 4. 已知一棵树二叉树的后根遍历和中根遍历的已知一棵树二叉树的后根遍历和中根遍历的序列分别为：序列分别为：A C D B G I H F EA C D B G I H F E和和A B C D E A B C D E F G H IF G H I，请画出该二叉树，并写出它的先根遍，请画出该二叉树，并写出它的先根遍历的序列。历的序列。先根遍历序列：先根遍历序列：EBADCFHGIEBADCFHGIIB BA AC CH HG GE ED

37、DF F构造的二叉树如下：构造的二叉树如下：附加题解答：附加题解答：5.3 二叉树的遍历二叉树的遍历5. 5. 已知一棵树二叉树的先根遍历和中根遍历的已知一棵树二叉树的先根遍历和中根遍历的序列分别为：序列分别为：A B D G H C E F IA B D G H C E F I和和G D H B A G D H B A E C I FE C I F，请画出此二叉树，并写出它的后根遍，请画出此二叉树，并写出它的后根遍的序列。的序列。BDGFIAHCE后根遍历序列：后根遍历序列：GHDBEIFCA构造的二叉树如下：构造的二叉树如下：附加题解答：附加题解答：5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈

38、夫曼编码5.4.1 5.4.1 哈夫曼树的基本概念哈夫曼树的基本概念5.4.2 5.4.2 哈夫曼树和哈夫曼编哈夫曼树和哈夫曼编 码的构造方法码的构造方法5.4.3 5.4.3 构造哈夫曼树和哈夫构造哈夫曼树和哈夫 曼编码类的描述曼编码类的描述5.4 5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.1 5.4.1 哈夫曼树的基本概念哈夫曼树的基本概念 结点的路径长度结点的路径长度： 结点间的路径结点间的路径： 从一个结点到另一个结点所经历的结点从一个结点到另一个结点所经历的结点和分支序列。和分支序列。 从根结点到该结点的路径上分支的数目。

39、从根结点到该结点的路径上分支的数目。 结点的权结点的权： 在实际应用中，人们往住会给树中的每在实际应用中，人们往住会给树中的每一个结点赋予一个具有某种实际意义的数值，一个结点赋予一个具有某种实际意义的数值，这个数值被称为该结点的权值。这个数值被称为该结点的权值。 5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.1 5.4.1 哈夫曼树的基本概念哈夫曼树的基本概念 树的带权路径长度树的带权路径长度： 结点的带权路径长度结点的带权路径长度：结点的路径长度与该结点的权值的乘积。结点的路径长度与该结点的权值的乘积。 树中所有叶结点的带权路径长度之和树中所有叶结点的带权路径长度之和 。 假设树上

40、有假设树上有 n n 个叶结点，通常记作个叶结点，通常记作: : 其中其中L Li i为带权为带权 w wi i的叶子结点的的叶子结点的带权路径长度带权路径长度。iniiLWWPL1iL5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.1 5.4.1 哈夫曼树的基本概念哈夫曼树的基本概念 最优二叉树最优二叉树： 给定给定n n个权值并作为个权值并作为n n个叶结点按一定规个叶结点按一定规则构造一棵二叉树，使其则构造一棵二叉树，使其带权路径长度达到带权路径长度达到最小值最小值，则这棵二叉树被称为，则这棵二叉树被称为最优二叉树。最优二叉树。也称也称哈夫曼树。哈夫曼树。iL 在所有含 n 个叶

41、子结点、并带相同权值的 二叉树中，必存在一棵其带权路径带权路径长度取最小值长度取最小值的树，这树就是“最优树最优树”。5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码27549WPL(T)= 72+52+23+43+92 =60WPL(T)= 74+94+53+42+21 =89 7 9 254对应权值对应权值5.4.1 5.4.1 哈夫曼树的基本概念哈夫曼树的基本概念5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码如何构造最优树（哈夫曼树）呢？如何构造最优树（哈夫曼树）呢？5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.1 5.4.1 哈夫曼树的基本概念哈夫曼树的基本概念5.4.2

42、5.4.2 哈夫曼树和哈夫曼编哈夫曼树和哈夫曼编 码的构造方法码的构造方法5.4.3 5.4.3 构造哈夫曼树和哈夫构造哈夫曼树和哈夫 曼编码类的描述曼编码类的描述5.4 5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.2 5.4.2 哈夫曼树及哈夫曼编码的构造方法哈夫曼树及哈夫曼编码的构造方法 (1) 根据给定的根据给定的 n 个权值个权值 w1, w2, , wn， 构造构造 一个由一个由n 棵二叉树所构成棵二叉树所构成的集合的集合 F = T1, T2, , Tn， 其中每棵二叉树中均只含一个带权其中每棵二叉树中均只含一个带权值为值

43、为 wi 的根结点，其左、右子树为空的根结点，其左、右子树为空树；树； 赫夫曼算法的主要步骤（赫夫曼算法的主要步骤（P175）5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.2 5.4.2 哈夫曼树及哈夫曼编码的构造哈夫曼树及哈夫曼编码的构造 赫夫曼算法的主要步骤（赫夫曼算法的主要步骤（P175） (2) (2)在二叉树森林在二叉树森林F F中选取根结点的中选取根结点的权值最小和次小的两棵二叉树，分别权值最小和次小的两棵二叉树，分别把它们作为左子树和右子树去构造一把它们作为左子树和右子树去构造一棵新二叉树，新二叉树的根结点权值棵新二叉树，新二叉树的根结点权值为其左、右子树根结点的权值之

44、和。为其左、右子树根结点的权值之和。 5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.2 5.4.2 哈夫曼树及哈夫曼编码的构造方法哈夫曼树及哈夫曼编码的构造方法 赫夫曼算法的主要步骤（赫夫曼算法的主要步骤（P175） (3) 作为新二叉树的左、右子树的这两作为新二叉树的左、右子树的这两棵二叉树从森林棵二叉树从森林F中中删除删除，同时，同时加入加入刚生刚生成的新二叉树；成的新二叉树； (4) 重复重复 (2) 和和 (3) 两步，直至两步，直至 F 中只中只 含一棵二叉树为止，则这种棵二叉树就含一棵二叉树为止，则这种棵二叉树就是所构成的哈夫曼树。是所构成的哈夫曼树。5.4 哈夫曼树及哈

45、夫曼编码哈夫曼树及哈夫曼编码5.4.2 5.4.2 哈夫曼树及哈夫曼编码的构造方法哈夫曼树及哈夫曼编码的构造方法9例如例如: : 已知权值已知权值 W= 5, 6, 2, 9, 7 5627527697671395275.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.2 5.4.2 哈夫曼树及哈夫曼编码的构造方法哈夫曼树及哈夫曼编码的构造方法67139527952716671329000011110001101101119527165.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.2 5.4.2 哈夫曼树及哈夫曼编码的构造方法哈夫曼树及哈夫曼编码的构造方法再例如再例如: : 书书P

46、177P177的的 例例5.8 5.8 ( (由学生完成）由学生完成） 已知在一个信息通信联络中使用了已知在一个信息通信联络中使用了8 8个字符：个字符：a a、b b、c c、d d、e e、f f、g g和和h h，每个，每个字符的使用频度分别为：字符的使用频度分别为：6 6、3030、8 8、9 9、1515、2424、4 4和和1212，试设计各个字符的哈夫，试设计各个字符的哈夫曼编码。曼编码。 问：问：一棵有一棵有 n个叶子结点的哈夫曼树共有多个叶子结点的哈夫曼树共有多 少个结点？少个结点？2*n+1 个个5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.2 5.4.2 哈夫曼

47、树及哈夫曼编码的构造方法哈夫曼树及哈夫曼编码的构造方法 指的是，任何一个字符的编码都不是同一指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。字符集中另一个字符的编码的前缀。前缀编码：前缀编码： 哈夫曼编码是一种前缀码。哈夫曼编码是一种前缀码。 从哈夫曼树的根开始，从左到右把二进制从哈夫曼树的根开始，从左到右把二进制编码的每一位进行判别，若遇到编码的每一位进行判别，若遇到0 0，则选择左，则选择左分支走向下一个结点；若遇到分支走向下一个结点；若遇到1 1，则选择右分，则选择右分支走向下一个结点，直至到达一个树叶结点，支走向下一个结点，直至到达一个树叶结点，便求得相应字符。便求

48、得相应字符。 译码过程是编码过程的逆过程：译码过程是编码过程的逆过程：5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.1 5.4.1 哈夫曼树的基本概念哈夫曼树的基本概念5.4.2 5.4.2 哈夫曼树和哈夫曼编哈夫曼树和哈夫曼编 码的构造方法码的构造方法5.4.3 5.4.3 构造哈夫曼树和哈夫构造哈夫曼树和哈夫 曼编码类的描述曼编码类的描述5.4 5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.3 5.4.3 哈夫曼树及哈夫曼编码类的描述哈夫曼树及哈夫曼编码类的描述哈夫曼树的结点存储结构示意图：哈夫曼树的结点存储结构示意图：其

49、中其中: : weight域存放结点的权值；域存放结点的权值； flag域存放结点是否加入哈夫曼树的标志域存放结点是否加入哈夫曼树的标志 值，等于值，等于1 1时表示已加入，否则没加入；时表示已加入，否则没加入； parent、rchild、lchild域分别存放父结域分别存放父结 点，左、右孩子结点的地址。点，左、右孩子结点的地址。5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.3 5.4.3 哈夫曼树及哈夫曼编码类的描述哈夫曼树及哈夫曼编码类的描述哈夫曼树的结点类描述：（书中哈夫曼树的结点类描述：（书中P178）public class HuffmanNode public Huf

50、fmanNode () / 构造一个空结点构造一个空结点 this(null); / / 构造一个左、右孩子域为空的结点构造一个左、右孩子域为空的结点public HuffmanNode (int weight ) this.weight=weight; flag=0; parent=lchild=rchild=null; private int weight; / 结点的数据域结点的数据域private int flag; /结点是否加入哈夫曼树的标志结点是否加入哈夫曼树的标志 private HuffmanNode parent, lchild, rchild; /父结点，父结点， 左、右

51、孩子结点域左、右孩子结点域5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.3 5.4.3 哈夫曼树及哈夫曼编码类的描述哈夫曼树及哈夫曼编码类的描述构造哈夫曼树和哈夫曼编码的类描述：构造哈夫曼树和哈夫曼编码的类描述：public class HuffmanTree （略）（略）书中书中P179P179public int huffmanCoding (int W) int n = W.length; / 字符个数int m = 2 * n - 1; / 哈夫曼树的结点数5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.3 5.4.3 哈夫曼树及哈夫曼编码类的描述哈夫曼树及哈夫曼编码

52、类的描述 例如：例如：对于书对于书P177P177例例5.85.8，按，按HuffmanTree类中的类中的HuffmanCoding方法可构造如下图的方法可构造如下图的一棵二棵树：一棵二棵树：5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码weight flag parent lchild rchild 0 1 2 3 4 5 6 7 8 9101112131460000300000800009000015000024000040000120000 其存储结构其存储结构HNHN的的初始初始和和终结终结状态分别如下图所示状态分别如下图所示 ： weight flag parent lchild

53、 rchild 0 1 2 3 4 5 6 7 8 91011121314618003011300819009190015111002411200418001211000100106017011232201287320134946014105620141111080012135.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.4.3 5.4.3 哈夫曼树及哈夫曼编码类的描述哈夫曼树及哈夫曼编码类的描述所得的哈夫曼编码如下图所示所得的哈夫曼编码如下图所示 ： 5.5 树与森林树与森林5.5.1 5.5.1 树、森林与二叉树之间的转换树、森林与二叉树之间的转换5.5.2 5.5.2 树的存储结构树

54、的存储结构5.5.3 5.5.3 树与森林的遍历树与森林的遍历5.5 5.5 树与森林树与森林5.5 树与森林树与森林5.5.1 5.5.1 树、森林与二叉树之间的转换树、森林与二叉树之间的转换1. 1. 树转换成二叉树的规则：树转换成二叉树的规则：GABCDEF树树 AB C E D F G 二叉树二叉树左孩子右兄弟左孩子右兄弟5.5 树与森林树与森林5.5.1 5.5.1 树、森林与二叉树之间的转换树、森林与二叉树之间的转换树转换成二叉树可形象描述为以下树转换成二叉树可形象描述为以下3 3个步骤：个步骤：(1) (1) 加线加线GABCDEF AB C E D F G (2) (2) 删线

55、删线(3) (3) 旋转旋转树树二叉树二叉树5.5 树与森林树与森林5.5.1 5.5.1 树、森林与二叉树之间的转换树、森林与二叉树之间的转换2. 2. 二叉树转换成树的规则：二叉树转换成树的规则：是树转换成二叉树的逆过程：是树转换成二叉树的逆过程：(1) (1) 加线加线GABCDEF AB C E D F G (2) (2) 删线删线(3) (3) 旋转旋转二叉树二叉树树树5.5 树与森林树与森林5.5.1 5.5.1 树、森林与二叉树之间的转换树、森林与二叉树之间的转换3. 3. 森林转换成二叉树的规则：森林转换成二叉树的规则：若 F = ，则 B = ；否则， 由 ROOT( T1

56、) 对应得到 Node(root)； 由 (t11, t12, , t1m ) 对应得到 LBT； 由 (T2, T3, Tn ) 对应得到 RBT。5.5 树与森林树与森林ABCDEFGH I J K树与二叉树的对应树与二叉树的对应ABCDEFG例如：如下森林转化成二叉树的过程为：例如：如下森林转化成二叉树的过程为：H I J K5.5.1 5.5.1 树、森林与二叉树之间的转换树、森林与二叉树之间的转换5.5 树与森林树与森林树根相连树根相连（将森林中后一棵树视为前一棵树的右子树）（将森林中后一棵树视为前一棵树的右子树）ABCDEFGH I J K5.5.1 5.5.1 树、森林与二叉树之

57、间的转换树、森林与二叉树之间的转换5.5 树与森林树与森林4. 二叉树转换为森林的规则为：二叉树转换为森林的规则为：若 B = ， 则 F = ；否则，由 Node(root) 对应得到 ROOT( T1 )；由LBT 对应得到 ( t11, t12, ，t1m)；由RBT 对应得到 (T2, T3, , Tn)。（转换过程是森林转换成二叉树的逆过程）（转换过程是森林转换成二叉树的逆过程）动画播放动画播放（6-6-2）5.5.1 5.5.1 树、森林与二叉树之间的转换树、森林与二叉树之间的转换5.5 树与森林树与森林5.5.1 5.5.1 树、森林与二叉树之间的转换树、森林与二叉树之间的转换5

58、.5.2 5.5.2 树的存储结构树的存储结构5.5.3 5.5.3 树与森林的遍历树与森林的遍历5.5 5.5 树与森林树与森林5.5 树与森林树与森林5.5.2 5.5.2 树的存储结构树的存储结构1.1.双亲链表存储结构双亲链表存储结构2.2.孩子链表存储结构孩子链表存储结构4.4.孩子兄弟链表存储结构孩子兄弟链表存储结构( (重点掌握）重点掌握）树的四种存储结构树的四种存储结构3.3.双亲孩子链表存储结构双亲孩子链表存储结构5.5 树与森林树与森林5.5.2 5.5.2 树的存储结构树的存储结构1.1.双亲链表存储结构双亲链表存储结构5.5 树与森林树与森林5.5.2 5.5.2 树的

59、存储结构树的存储结构2.2.孩子链表存储结构孩子链表存储结构5.5 树与森林树与森林5.5.2 5.5.2 树的存储结构树的存储结构3.3.双亲孩子链表存储结构双亲孩子链表存储结构5.5 树与森林树与森林5.5.2 5.5.2 树的存储结构树的存储结构4.4. 孩子兄弟链表存储结构孩子兄弟链表存储结构（* *）5.5 树与森林树与森林5.5.2 5.5.2 树的存储结构树的存储结构4.4. 孩子兄弟链表存储结构孩子兄弟链表存储结构孩子兄弟链表中结点类的描述：孩子兄弟链表中结点类的描述：public class CSTreeNodeprivate Object data; / 结点的数据域结点的

60、数据域private CSTreeNode firstchild, nextsiblingchild; / 左孩子、右兄弟域左孩子、右兄弟域(书书P186)5.5 树与森林树与森林5.5.1 5.5.1 树、森林与二叉树之间的转换树、森林与二叉树之间的转换5.5.2 5.5.2 树的存储结构树的存储结构5.5.3 5.5.3 树与森林的遍历树与森林的遍历5.5 5.5 树与森林树与森林5.5 树与森林树与森林5.5.3 5.5.3 树和森林的遍历树和森林的遍历一、树的遍历一、树的遍历5.5 树与森林树与森林5.5.3 5.5.3 树和森林的遍历树和森林的遍历-树的遍历树的遍历树的遍历可有三条搜