[快速树的遍历]前序中序后序课件.ppt

1、树（二）树（二）2012初赛知识点梳理初赛知识点梳理4、设有一棵k叉树，其中只有度为0和k两种结点，设n 0，n k，分别表示度为0和度为k的结点个数，试求出n 0 和n k之间的关系（n 0=数学表达式，数学表达式仅含n k、k和数字）。答：答：n0和和nk之间的关系为：之间的关系为：n0=(k-1)nk+1。k=2n0=n2+1k=3n0=2n3+1k=4n0=3n4+1一个包含一个包含n个分支结点（非叶结点）的非空满个分支结点（非叶结点）的非空满k叉树，叉树，k=1，它的，它的叶结点数目为：叶结点数目为：A）nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1【分析分析】选

2、择选择 D考多叉树的性质，考多叉树的性质，N0=(K-1)N+1，考试的时带入，考试的时带入K=2时候，验证二叉树时候，验证二叉树能得到结果。能得到结果。概念：概念：1.满二叉数、完全二叉树、均衡二叉树、平衡二叉树满二叉数、完全二叉树、均衡二叉树、平衡二叉树2.已知节点数计算二叉树的不同形态的个数已知节点数计算二叉树的不同形态的个数3.二叉树度为二叉树度为0的节点个数与度为的节点个数与度为2的节点个数的关系的节点个数的关系4.每层节点最多是多少每层节点最多是多少5.树的深度为树的深度为h，与树的节点数的关系。与树的节点数的关系。高度为高度为n的均衡的二叉树是的均衡的二叉树是指：如果去掉叶结点及

3、相应的树枝，它应该是高度为n-1的满二叉树对于对于N2的平衡二叉树，的平衡二叉树，其前其前N-2层必然是完全二叉树，层必然是完全二叉树，又称又称AVL树树二叉树的存储结构二叉树的存储结构结点的位置与结点编号的关系：如果i=1，则i为根，无父结点；如果i1，则父结点为i/2。如果2*i=N，则i的左儿子的编号为2*i。如果2*i+1BDCD L R先序遍历序列：先序遍历序列：A B D CA B D C先序遍历先序遍历ABCDGEFH先序遍历：先序遍历：A A B B D D G G C C E E F F H H顺时针路径中，第一次（左边）遇到某个节点记录下来顺时针路径中，第一次（左边）遇到某

4、个节点记录下来中序遍历ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A CB D A C投影投影D GBAECH中序遍历：中序遍历：ABCDGEFHF后序遍历后序遍历ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列：D B C AD B C ABABCDGEFH顺时针路径中，遇到某个节点右边时，记录下来顺时针路径中，遇到某个节点右边时，记录下来后序遍历：后序遍历：C CG GF FD DH HB B E EA A表达式a+b*(c-d)-e/f 用二叉树表示-+/a*b-efcd先序遍历：先序遍历：-+a a*b

5、b-c c d d/e e f f波兰式波兰式表达式a+b*(c-d)-e/f 用二叉树表示-+/a*b-efcd中序遍历：中序遍历：-+a a*b b-c cd d/e ef f中缀表示中缀表示表达式a+b*(c-d)-e/f 用二叉树表示-+/a*b-efcd后序遍历：后序遍历：-+a a*b b-c c d d/e e f f逆逆波兰式波兰式三种遍历算法的比较相同点：相同点：如果把访问根结点这个如果把访问根结点这个不涉及递归的语句抛开，则不涉及递归的语句抛开，则三个递归算法走过的路线是三个递归算法走过的路线是一样的一样的。三种遍历算法的比较不同点：不同点：v 前序遍历是每进入一层递前序遍

6、历是每进入一层递 归调用时归调用时先访问根结点先访问根结点，然后再依次向它的左、右然后再依次向它的左、右 子树执行递归调用；子树执行递归调用；v 中序遍历是在执行完中序遍历是在执行完左子左子 树递归调用后再访问根结树递归调用后再访问根结 点点，然后向它的右子树递，然后向它的右子树递 归调用；归调用；v 后序遍历则是在从后序遍历则是在从右子树右子树 递归调用退出后访问根结递归调用退出后访问根结 点点。AEBCDFHIGJ 已知一棵二叉树已知一棵二叉树 先序遍历序列为先序遍历序列为A ABECDFGHIJBECDFGHIJ 中序遍历序列为中序遍历序列为EBCDEBCDA AFHIGJFHIGJ试画

7、出这颗二叉树。试画出这颗二叉树。AFHIGJBECD 已知一棵二叉树已知一棵二叉树 先序遍历序列为先序遍历序列为A AB BECDFGHIJECDFGHIJ 中序遍历序列为中序遍历序列为E EB BCDCDA AFHIGJFHIGJ试画出这颗二叉树。试画出这颗二叉树。AFHIGJBECD 已知一棵二叉树已知一棵二叉树 先序遍历序列为先序遍历序列为A AB BECDFGHIJECDFGHIJ 中序遍历序列为中序遍历序列为E EB BCDCDA AFHIGJFHIGJ试画出这颗二叉树。试画出这颗二叉树。AFHIGJBDEC 已知一棵二叉树已知一棵二叉树 先序遍历序列为先序遍历序列为A AB BE

8、ECDFGHIJCDFGHIJ 中序遍历序列为中序遍历序列为E EB BCDCDA AFHIGJFHIGJ试画出这颗二叉树。试画出这颗二叉树。AFHIGJBECD 已知一棵二叉树已知一棵二叉树 先序遍历序列为先序遍历序列为A AB BECDFGHIJECDFGHIJ 中序遍历序列为中序遍历序列为E EB BCDCDA AFHIGJFHIGJ试画出这颗二叉树。试画出这颗二叉树。AHIGJBECDF 已知一棵二叉树已知一棵二叉树 先序遍历序列为先序遍历序列为A AB BECDFGHIJECDFGHIJ 中序遍历序列为中序遍历序列为E EB BCDCDA AFHIGJFHIGJ试画出这颗二叉树。试画

9、出这颗二叉树。AHIBECDFGJ 已知一棵二叉树已知一棵二叉树 先序遍历序列为先序遍历序列为A AB BECDFGHIJECDFGHIJ 中序遍历序列为中序遍历序列为E EB BCDCDA AFHIGJFHIGJ试画出这颗二叉树。试画出这颗二叉树。ABECDFGHJI思考思考：先序、中序、后序序列中任意给定两个：先序、中序、后序序列中任意给定两个 序列就可以画出该二叉树吗？为什么？序列就可以画出该二叉树吗？为什么？已知一棵二叉树已知一棵二叉树 先序遍历序列为先序遍历序列为A AB BECDFGHIJECDFGHIJ 中序遍历序列为中序遍历序列为E EB BCDCDA AFHIGJFHIGJ试

10、画出这颗二叉树。试画出这颗二叉树。按层次遍历ABECDFGHJI按层次遍历序列：ABFECGDHJI 给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA，画出此二叉树。【问题分析】后序遍历中最后访问的是根结点，所以后序遍历DGEBHIFCA序列中A是根结点；根据中序遍历的算法，先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树，所以中序遍历DBGEACHFI序列中，根结点A的两侧分别是左子树和右子树：DBGE、CHFI。由中根序列和后根序列来确定二叉树的结构，从而判断先根遍历序列及其它。由中根序列和后根序列来确定二叉树的结构，从而判断先根遍历序列及其它。n例例1：

11、(NOIP 2001提高组试题提高组试题)n已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：C B G E A F H D I J与与C G E B H F JI D A则该二叉树的先序遍历的顺序为则该二叉树的先序遍历的顺序为解析：已知中序序列为解析：已知中序序列为C B G E A F H D I(1)后序序列为后序序列为C G EBH F JI D A。(2)由由(2)知：根结点为知：根结点为A 由由(1)知：知：A的左子树中序序列为的左子树中序序列为C B G E (3)A的右子树中序序列为的右子树中

12、序序列为F H D I J(4)由由(2)知：知：A的左子树后序序列为的左子树后序序列为C G E B(5)A的右子树后序序列为的右子树后序序列为H F J I D(6)由由(5)(6)知：知：A的左子树根结点为的左子树根结点为B，A的右子树根结点为的右子树根结点为D由由(3)(4)知：知：B的左子树为的左子树为C，右子树中序序列为，右子树中序序列为G E D的左子树中序序列为的左子树中序序列为F H，右子树中序序列为，右子树中序序列为I J由由(5)(6)知：知：B的右子树后序序列为的右子树后序序列为G E，即根结点为，即根结点为ED的左子树后序序列为的左子树后序序列为H F，即根结点为，即

13、根结点为FD的右子树后序序列为的右子树后序序列为JI，即根结点为，即根结点为I综上可推出二叉树的结构如图所示综上可推出二叉树的结构如图所示故该二叉树的先序遍历序列为：故该二叉树的先序遍历序列为：A B C E G D F H I J 由前序序列和中序序列来确定一棵二叉树，从而判断后序序列及其它由前序序列和中序序列来确定一棵二叉树，从而判断后序序列及其它例例2：(NOIP 2004提高组试题提高组试题)二叉树二叉树T，已知其前序遍历序列为，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍，中序遍历序列为历序列为4 2 1 5 7 3 6，则其后序遍历序列为，则其后序遍历序列为()。A4 2

14、 5 7 6 3 1 B4 2 7 5 6 3 1 C4 2 7 5 3 6 1 D4 7 2 3 5 6 1 E4 5 2 6 3 7 l 解析：已知前序遍历序列为解析：已知前序遍历序列为1 2 4 3 5 7 6 (1)中序遍历序列为中序遍历序列为4 2 l 5 7 3 6 (2)由由(1)知：根结点为知：根结点为1由由(2)知：知：1的左子树中序序列为的左子树中序序列为4 2 (3)右子树中序序列为右子树中序序列为5 7 3 6 (4)由由(1)知知1的左子树先序序列为的左子树先序序列为2 4 (5)1的右子树先序序列为的右子树先序序列为3 5 7 6 (6)由由(3)(5)知：知：1的

15、左子树根结点为的左子树根结点为2，2的左子树为的左子树为4由由(4)(6)知：知：1的右子树根结点为的右子树根结点为3由由(4)知：知：3的左子树中序序列为的左子树中序序列为5 7 (7)3的右子树为的右子树为6 由由(6)(7)知：知：3的左子树根结点为的左子树根结点为5，且，且5的右子树为的右子树为7 综上对应的一棵二叉树的结构如图所示：综上对应的一棵二叉树的结构如图所示：故其后序遍历序列为：故其后序遍历序列为：4 2 7 5 6 3 1 从而答案选从而答案选B 由先根序列和后根序列来推断二叉树的结构，从而判断中根遍历序列以及其他由先根序列和后根序列来推断二叉树的结构，从而判断中根遍历序列

16、以及其他例例3：(NOIP 2007提高组第提高组第14题题)已知已知7个结点的二叉树的先根遍历是个结点的二叉树的先根遍历是1 2 4 5 6 3 7 f数字为结点的编号，以下同数字为结点的编号，以下同)，后根遍历是，后根遍历是4 6 5 27 3 1，则该二叉树的可能的中根遍，则该二叉树的可能的中根遍历是历是()。A4 2 6 5 1 7 3 B4 2 5 6 1 3 7 C4 2 3 1 5 4 7 D4 2 5 6 1 7 3解析：先根遍历序列是解析：先根遍历序列是1 2 4 5 6 3 7 (1)后根遍历序列是后根遍历序列是4 6 5 2 7 3 1(2)由由(1)和和(2)知：根结点

17、为知：根结点为l，1的左子树根结点是的左子树根结点是2，右子树根结点是，右子树根结点是3，结点，结点4是结点是结点2的左子树，可以判断结点的左子树，可以判断结点5是结点是结点2的右子树的根结点，但结点的右子树的根结点，但结点6可能是结点可能是结点5的左子的左子树，也可能是它的右子树，同样结点树，也可能是它的右子树，同样结点7可能是结点可能是结点3的左子树，也可能是它的右子树。的左子树，也可能是它的右子树。对应的二叉树的结构可能是如下四种：对应的二叉树的结构可能是如下四种：图的中序遍历序列是：图的中序遍历序列是：4 2 6 5 1 7 3 图的中序遍历序列是：图的中序遍历序列是：4 2 5 6

18、1 7 3 图图的中序遍历序列是：的中序遍历序列是：4 2 6 5 1 3 7 图的中序遍历序列是：图的中序遍历序列是：4 2 5 6 1 3 7 故此故此题的答案应选题的答案应选A B D 通过二叉树的宽度优先遍历和树中结点的最大深度及结点之间的关系来判断通过二叉树的宽度优先遍历和树中结点的最大深度及结点之间的关系来判断树的结构，从而解决有关问题。树的结构，从而解决有关问题。例例5：(NOIP 2005提高组试题提高组试题)二叉树二叉树T的宽度优先遍历序列为的宽度优先遍历序列为A B C D E F G H I，已知已知A是是C的父结点，的父结点，D是是G的父结点，的父结点，F是是I的父结点

19、，树中所有结点的最大深度为的父结点，树中所有结点的最大深度为3(根结点深度设为根结点深度设为0)，可知，可知E的父结点可能是的父结点可能是()。A B B C C D D E F 解析：二叉树的宽度优先遍历就是按层遍历，从根结点自上而下，自左向右访问树解析：二叉树的宽度优先遍历就是按层遍历，从根结点自上而下，自左向右访问树中的每一个结点。由题目可知中的每一个结点。由题目可知A是根结点，又知是根结点，又知A是是C的父结点，可以推知的父结点，可以推知B是是A的左的左子树的根结点，子树的根结点，C是是A的右子树的根结点。又知的右子树的根结点。又知D是是G的父结点，的父结点，F是是I的父结点，树中的父结点，树中所有结点的最大深度为所有结点的最大深度为3，故，故E结点可能是结点可能是B结点的右子树，也可能是结点的右子树，也可能是G结点的左子树。结点的左子树。二叉树的部分结构图为下图所示：二叉树的部分结构图为下图所示：故故E的父结点可能是的父结点可能是B，也可能是，也可能是C。A B C B C C BC B