2011-2012初赛知识点讲解数据结构（八）树.ppt

树（三） 2012初赛知识点梳理 给出一棵二叉树的 中序遍历：DBGEACHFI 后序遍历：DGEBHIFCA 画出此二叉树。 给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA，画出此二叉树。 【问题分析】 　　后序遍历中最后访问的是根结点，所以后序遍历DGEBHIFCA序列中A是根结点；根据中序遍历的算法，先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树，所以中序遍历DBGEACHFI序列中，根结点A的两侧分别是左子树和右子树：DBGE、CHFI。 由中根序列和后根序列来确定二叉树的结构，从而判断先根遍历序列及其它。 例1：(NOIP 2001提高组试题) 已知一棵二叉树的结点名为大写英文字母，其中序与后序遍历的顺序分别为：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的右子树中序序列为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，即根结点为E D的左子树后序序列为H F，即根结点为F D的右子树后序序列为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 则其后序遍历序列为( )。 A．4 2 5 7 6 3 1 B．4 2 7 5 6 3 1 C．4 2 7 5 3 6 1  D．4 7 2 3 5 6 1 E．4 5 2 6 3 7 l 由前序序列和中序序列来确定一棵二叉树，从而判断后序序列及其它 例2：(NOIP 2004提高组试题)二叉树T，已知其前序遍历序列为1 2 4 3 5 7 6，中序遍历序列为4 2 1 5 7 3 6，则其后序遍历序列为( )。 A．4 2 5 7 6 3 1 B．4 2 7 5 6 3 1 C．4 2 7 5 3 6 1  D．4 7 2 3 5 6 1 E．4 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的左子树根结点为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 由先根序列和后根序列来推断二叉树的结构，从而判断中根遍历序列以及其他 例3：(NOIP 2007提高组第14题)已知7个结点的二叉树的先根遍历是1 2 4 5 6 3 7 f数字为结点的编号，以下同)，后根遍历是4 6 5 27 3 1，则该二叉树的可能的中根遍历是( )。 A．4 2 6 5 1 7 3 B．4 2 5 6 1 3 7 C．4 2 3 1 5 4 7 D．4 2 5 6 1 7 3 由先根序列和后根序列来推断二叉树的结构，从而判断中根遍历序列以及其他 例3：(NOIP 2007提高组第14题)已知7个结点的二叉树的先根遍历是1 2 4 5 6 3 7 f数字为结点的编号，以下同)，后根遍历是4 6 5 27 3 1，则该二叉树的可能的中根遍历是( )。 A．4 2 6 5 1 7 3 B．4 2 5 6 1 3 7 C．4 2 3 1 5 4 7 D．4 2 5 6 1 7 3 解析：先根遍历序列