第5章+树与二叉树ppt课件.ppt

《第5章+树与二叉树ppt课件.ppt》由会员分享，可在线阅读，更多相关《第5章+树与二叉树ppt课件.ppt（171页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数数 据据 结结 构构(Java(Java语言描述语言描述)篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统第五章第五章 树与二叉树树与二叉树数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）第五章第五章 树树 与与 二二 叉叉 树树章节目录章节目录章节目录章节目录章节目录章节目录作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统教学内容教学内

2、容5.2 二叉树的基本概念二叉树的基本概念5.1 树的基本概念树的基本概念5.4 哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码5.3 二叉树的遍历二叉树的遍历5.5 树与森林树与森林数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）第五章第五章 树树 与与 二二 叉叉 树树章节目录章节目录章节目录章节目录章节目录章节目录作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统教学重点与难点教学重点与难点重点：重点

3、：u二叉树的性质；二叉树的性质；u二叉树的存储方法二叉树的存储方法u二叉树的遍历及其应用二叉树的遍历及其应用u哈夫曼编码哈夫曼编码难点：难点：u二叉树遍历算法的应用二叉树遍历算法的应用数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）第五章第五章 树树 与与 二二 叉叉 树树章节目录章节目录章节目录章节目录章节目录章节目录作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统课课 前前 思思 考考 你你见过

4、家族家族谱系系图吗？试以以图形表示形表示从你的祖父起的家族成从你的祖父起的家族成员关系。关系。祖父祖父伯父伯父父亲父亲叔父叔父堂兄堂兄堂姐堂姐你你侄儿侄儿堂弟堂弟 这类图形正这类图形正是本章要讨是本章要讨论的论的“树树”结构。结构。数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.1 树的基本概念树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型

5、的系统5.1.1 5.1.1 树的定义树的定义5.1.2 5.1.2 树的常用术语树的常用术语5.1 5.1 树的基本概念树的基本概念数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.1 树的基本概念树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.1.1 5.1.1 树的定义树的定义 树树是由是由n n（n0n0）个结点所构成的）个结

6、点所构成的有限集合，当有限集合，当n=0n=0时，称为时，称为空树空树；当；当n0n0时，时，n n个结点满足以下条件：个结点满足以下条件：有且仅有一个称为有且仅有一个称为根根的结点。的结点。其余结点可分为其余结点可分为m m（m0m0）个）个互不相交的有限集合，且每一个集合互不相交的有限集合，且每一个集合又构成一棵树，这棵树称为是又构成一棵树，这棵树称为是根结点根结点的子树的子树。数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.1 树的基本概念树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束

7、放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.1.1 5.1.1 树的定义树的定义ABCDEFGHIJMKL例如例如:rootT1T2T3数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.1 树的基本概念树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计

8、时计分系统是一种得分类型的系统5.1.1 5.1.1 树的定义树的定义树的表示方法：树的表示方法：树形表示法树形表示法文氏图表示法文氏图表示法凹入图表示法凹入图表示法广义表广义表(括号括号)表示法表示法ABCDEFGHIJMKL树形表示法树形表示法数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.1 树的基本概念树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系

9、统是一种得分类型的系统5.1.1 5.1.1 树的定义树的定义ABCDEFGHIJMKL树形表示法树形表示法EKFBDCJLGMIH文氏图表示法文氏图表示法A数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.1 树的基本概念树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.1.1 5.1.1 树的定义树的定义ABCDEFGHIJMKL树

10、形表示法树形表示法凹入图表示法凹入图表示法ABCDEFKLGIHJM数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.1 树的基本概念树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.1.1 5.1.1 树的定义树的定义ABCDEFGHIJMKL树形表示法树形表示法广义表广义表(括号括号)表示法表示法:（A,B(E,F(K,L),C(G

11、),D(H,I,J(M)数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.1 树的基本概念树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统线性结构线性结构树型结构树型结构第一个数据元素第一个数据元素 (无前驱无前驱)存在一个根结点存在一个根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)存在多个叶子结点存在多个叶子

12、结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它结点其它结点(一个前驱一个前驱(双亲双亲)、多个后继多个后继(孩子孩子)元素之间存在元素之间存在“一一对一对一”的关系的关系元素之间存在元素之间存在“一对一对多多”的关系的关系数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.1 树的基本概念树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮

13、球比赛的计时计分系统是一种得分类型的系统5.1.1 5.1.1 树的定义树的定义5.1.2 5.1.2 树的常用术语树的常用术语5.1 5.1 树的基本概念树的基本概念数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.1 树的基本概念树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.1.2 5.1.2 树的常用术语树的常用术语结点结点:

14、结点的度结点的度:树的度树的度:叶子结点叶子结点:分支结点分支结点:数据元素数据元素+所有关联子树根的分支所有关联子树根的分支结点所拥有子树的数目结点所拥有子树的数目树中所有结点的度的最大值树中所有结点的度的最大值度为零的结点度为零的结点度大于零的结点度大于零的结点DHIJM分支分支:根和子树根之间的连线根和子树根之间的连线(边边)结点的路径结点的路径:由从根到该结点所经分支和结点构成由从根到该结点所经分支和结点构成数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.1 树的基本概念树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结

15、束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统孩子孩子结点、双亲双亲结点兄弟兄弟结点、堂兄弟堂兄弟祖先祖先结点、子孙子孙结点结点的层次结点的层次:树的深度：树的深度：树中所有结点层次数的最大值加树中所有结点层次数的最大值加1 1。ABCDEFGHIJMKL 假设根结点的层次为假设根结点的层次为0 0，则其它结点，则其它结点的层次是其双亲结点的层次数加的层次是其双亲结点的层次数加1 1。有序树：有序树：树中各结点的所有子树之间从左到右树中各结点的所有

16、子树之间从左到右有严格的次序关系。有严格的次序关系。数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.1 树的基本概念树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统无序树无序树:森林：森林：由由m m（m m0 0）棵互不相交的树所构）棵互不相交的树所构成的集合。成的集合。与有序树相反，无序树是指树中各与有序树相反，无序树是指树中各结点

17、的所有子树之间没有严格的次序关结点的所有子树之间没有严格的次序关系。系。BCDEFGHIJMKL数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.2.1 5.2.1 二叉树的定义二叉树的定义5.2.2 5.2.2 二叉树的性质二叉树的性质5.2.3 5.2.3 二

18、叉树的存储结构二叉树的存储结构5.2 5.2 二叉树的基本概念二叉树的基本概念数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.2.1 5.2.1 二叉树的定义二叉树的定义 二叉树或为空树空树，或是由一个根结点根结点加上两棵两棵分别称为左子树左子树和右子树的、互不

19、交的互不交的二二叉树叉树组成。ABCDEFGHK根结点根结点左子树左子树右子树右子树数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.2.1 5.2.1 二叉树的定义二叉树的定义二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR

20、右子树为空树右子树为空树L左子树为空树左子树为空树左右子树均左右子树均不为空树不为空树数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.2.1 5.2.1 二叉树的定义二叉树的定义 具有具有3 3个结点的树与二叉树的个结点的树与二叉树的形态各有多少种形态各有多少种

21、?树有树有2 2种而二叉树有种而二叉树有5 5种。种。问问 二叉树就是度小于等于二叉树就是度小于等于2 2的树，这个结论是否正确的树，这个结论是否正确？数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统满二叉树的定义满二叉树的定义 如果在一棵二叉树中，它的所有结点如果

22、在一棵二叉树中，它的所有结点或或者是叶结点者是叶结点，或者是左、右子树都非空或者是左、右子树都非空，并且，并且所有叶结点都在同一层上所有叶结点都在同一层上，则称这棵二叉树为，则称这棵二叉树为满二叉树满二叉树 。012345678910 11 12 13 14数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮

23、球比赛的计时计分系统是一种得分类型的系统完全二叉树的定义完全二叉树的定义 如果在一棵具有如果在一棵具有n n个结点的二叉树中，它的个结点的二叉树中，它的逻辑结构与满二叉树的前逻辑结构与满二叉树的前n n个结点的逻辑结构相个结点的逻辑结构相同同，则称这样的二叉树为完全二叉树，则称这样的二叉树为完全二叉树 01234567 890123456789完全二叉树完全二叉树非非完全二叉树完全二叉树数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映

24、结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统单分支树的定义单分支树的定义左支树：左支树：左支树左支树右支树右支树右支树：右支树：所有所有结点都结点都没没有有右右孩子的二叉树。孩子的二叉树。所有所有结点都结点都没没有有左左孩子的二叉树。孩子的二叉树。ABCDABCD数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放

25、映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.2.1 5.2.1 二叉树的定义二叉树的定义5.2.2 5.2.2 二叉树的性质二叉树的性质5.2.3 5.2.3 二叉树的存储结构二叉树的存储结构5.2 5.2 二叉树的基本概念二叉树的基本概念数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映

26、章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.2.2 5.2.2 二叉树的性质二叉树的性质在在二二叉叉树树的的第第 i i 层层上上至至多多有有2 2i i 个个结结点。点。(i0)(i0)用归纳法证明：用归纳法证明：归纳基：归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=0 层时，只有一个根结点：层时，只有一个根结点：20=1；假设对所有的假设对所有的 j(0ji)层层，命，命题成立；题成立；则第则第 i层的结点数层的结点数 2i-1 2=2i。性质性质1 1：数据结构（数据

27、结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.2.2 5.2.2 二叉树的性质二叉树的性质 深深度度为为 h h（h1h1）的的二二叉叉树树上上至至多含多含 2 2h h-1-1 个结点。个结点。性质性质2 2：证明：证明：基于上一条性质，深度为基于上一条性质，深度为 h

28、h 的二叉的二叉树上的结点数至多为树上的结点数至多为:2 20 0+2+21 1+2+2h-1h-1=2=2h h-1-1 。数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.2.2 5.2.2 二叉树的性质二叉树的性质 对对于于任任何何一一棵棵二二叉叉树树，若若

29、其其叶叶结结点点的的个个数数为为n n0 0 ，度度为为2 2的的结结点点个个数数为为n n2 2，则有则有n n0 0=n=n2 2+1+1 。性质性质3 3：则则 二叉树上结点总数 n =？二叉树上分支总数 e =？n0+n1+n2而而 e与与 n的关系如何？的关系如何？证明：证明：n1+2n2由此得，由此得，n0=n2+1。设度为1的结点数为n1 e=n-1数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录

30、章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.2.2 5.2.2 二叉树的性质二叉树的性质 度为度为m m的树中，叶子结点数与其的树中，叶子结点数与其它结点数之间的关系如何？它结点数之间的关系如何？思考思考数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.2 二叉树的基本概念二叉树的基本概念作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据

31、运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.2.2 5.2.2 二叉树的性质二叉树的性质具具有有 n n 个个结结点点的的完完全全二二叉叉树树的的深深度度为为 loglog2 2n n +1+1 或或 loglog2 2(n(n+1)1)。性质性质4 4：证明：证明：设设完全二叉树的深度为 h,则根据第二条性质得 2h-1-1 n 2h -1即2h-1 n 2h,h-1 log2 n rDepth?lDepth:rDepth);3.求二叉树的深度求二叉树的深度数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语

32、言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.3.2 5.3.2 二叉树的遍历应用举例二叉树的遍历应用举例1.在二叉树上的查找某个结点在二叉树上的查找某个结点2.计算二叉树中结点的个数计算二叉树中结点的个数3.求二叉树的深度求二叉树的深度4.4.判断两棵二叉树是否相等判断两棵二叉树是否相等数据结构（数据结构（数据结构（数据结构（JavaJava语言

33、描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统要求：要求：实现方法实现方法:判断根结点为判断根结点为T1T1、T2T2的两棵二叉树是否相的两棵二叉树是否相等，若相等，则返回等，若相等，则返回truetrue；否则，返回；否则，返回falsefalse。因为一棵二叉树由根、左子树和右子树三个因为一棵二叉树由根、左子树和右子树三个部分

34、组成，所以只有当两棵二叉树的三个组成部部分组成，所以只有当两棵二叉树的三个组成部分都对应相等时，这两棵树才相等。而左、右子分都对应相等时，这两棵树才相等。而左、右子树的相等判断可以用对二叉树相等判断的同样方树的相等判断可以用对二叉树相等判断的同样方法来实现，即可用递归调用来实现。法来实现，即可用递归调用来实现。4.4.判断两棵二叉树是否相等判断两棵二叉树是否相等 所以，可利用所以，可利用先先根、根、中中根、和根、和后后根遍历中根遍历中的的任何一种任何一种算法思想来实现。算法思想来实现。数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历

35、二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统实现步骤实现步骤:(:(以中根遍历为例以中根遍历为例)1)1)若两棵二叉树若两棵二叉树都为空都为空，则两棵二叉树相等，则两棵二叉树相等，返回返回true;true;2)2)若两棵二叉树若两棵二叉树都非空都非空，则：，则：3)3)其它任何情况都返回其它任何情况都返回falsefalse。若左子树相等，则继续判断它们的若左子树相等，则继续

36、判断它们的根根结点结点是否相等是否相等，即转，即转；若根结点的值相等，则继续判断它们若根结点的值相等，则继续判断它们的右子树是否相等，即转的右子树是否相等，即转；若右子树也相等，则两棵二叉树若右子树也相等，则两棵二叉树相等，返回相等，返回true;true;4.4.判断两棵二叉树是否相等判断两棵二叉树是否相等数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规

37、定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统实现算法实现算法(书书P168P168算法算法5.12)5.12)：public boolean isEqualisEqual(BiTreeNode T1,BiTreeNode T2)if(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

38、.getRchild(),T2.getRchild()return true;return false;数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.3.1 5.3.1 二叉树的遍历方法及其实现二叉树的遍历方法及其实现5.3.2 5.3.2 二叉树遍历算法的应用举例二

39、叉树遍历算法的应用举例5.3.3 5.3.3 建立二叉树建立二叉树5.3 5.3 二叉树的遍历二叉树的遍历数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.3.3 5.3.3 建立二叉树建立二叉树 (二叉链式二叉链式存储结构存储结构)3.3.由标明空子树的先根遍历序列建由

40、标明空子树的先根遍历序列建 二叉树二叉树1.1.由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树2.2.由后根和中根遍历序列建二叉树由后根和中根遍历序列建二叉树4.4.由完全二叉树的顺序存储结构建由完全二叉树的顺序存储结构建 立二叉链式存储结构立二叉链式存储结构数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此

41、，篮球比赛的计时计分系统是一种得分类型的系统1.由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树 仅知二叉树的先序序列仅知二叉树的先序序列“abcdefg”不能唯一确定一棵二叉树，不能唯一确定一棵二叉树，如果同时已知二叉树的中序序列如果同时已知二叉树的中序序列“cbdaegf”，则会如何？，则会如何？二叉树的先序序列二叉树的先序序列二叉树的中序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布

42、置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1.由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树a b c d e f gc b d a e g f例如例如:aab bccddeeffggabcdefg先序序列先序序列中序序列中序序列数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结

43、束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1.由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树-算法算法建立一棵二叉树的过程如下：建立一棵二叉树的过程如下：数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时

44、间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统其中：其中：preOrder是整棵树的先根遍历序列；是整棵树的先根遍历序列；inOrder是整棵树的中根遍历序列；是整棵树的中根遍历序列；reIndex是先根遍历序列在是先根遍历序列在preOrder中的开始位置中的开始位置;inIndex是中根遍历序列在是中根遍历序列在inOrder中的开始位置中的开始位置;count表示树中结点的个数。表示树中结点的个数。1.由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树-算法算法实现方法：实现方法：引入引入5 5个参数：个参数：preOrder、inOrder、preIn

45、dex、inIndex和和count。数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统1.由先根和中根遍历序列建二叉树由先根和中根遍历序列建二叉树-算法算法public BiTree(String preOrder,String inOrder,int preIndex,i

46、nt inIndex,int count)if(count 0)char r=preOrder.charAt(preIndex);for(int i=0;i count;i+)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).roo

47、t);P170/算法算法5.13数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统5.3.3 5.3.3 建立二叉树建立二叉树 (二叉链式二叉链式存储结构存储结构)3.3.由标明空子树的先根遍历序列建由标明空子树的先根遍历序列建 二叉树二叉树1.1.由先根和中根遍历序列建二叉

48、树由先根和中根遍历序列建二叉树2.2.由后根和中根遍历序列建二叉树由后根和中根遍历序列建二叉树4.4.由完全二叉树的顺序存储结构建由完全二叉树的顺序存储结构建 立二叉链式存储结构立二叉链式存储结构数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛的计时计分系统是一种得分类型的系统2.由后根和中根遍历序列建二叉

49、树由后根和中根遍历序列建二叉树二叉树的后序序列二叉树的后序序列二叉树的中序序列二叉树的中序序列左子树左子树左子树左子树 右子树右子树右子树右子树根根根根问：问：由二叉树的前序和后序序列是否由二叉树的前序和后序序列是否也可以唯一确定一棵树？也可以唯一确定一棵树？数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队在规定的比赛时间里得分多少来决定胜负的，因此，篮球比赛

50、的计时计分系统是一种得分类型的系统2.由后根和中根遍历序列建二叉树由后根和中根遍历序列建二叉树 由二叉树的前序和后序序列由二叉树的前序和后序序列不可以不可以唯唯一确定一棵树一确定一棵树 如下二棵树：如下二棵树：ABAB 其其前序前序遍历序列都为：遍历序列都为：A B 其其后序后序遍历序列都为：遍历序列都为：B A数据结构（数据结构（数据结构（数据结构（JavaJava语言描述语言描述语言描述语言描述）5.3 二叉树的遍历二叉树的遍历作业布置作业布置作业布置作业布置作业布置作业布置结束放映结束放映结束放映结束放映结束放映结束放映章节目录章节目录章节目录章节目录章节目录章节目录篮球比赛是根据运动队