深度为4有7个结点的一般二叉树嘚顺序存储 深度为4，只有4个右孩子的二叉树的顺序存储 顺序存储结构适用于满二叉树和完全二叉树的存储 先序遍历 中序遍历 投影 后序遍曆 表达式a+b*(c-d)-e/f 用二叉树表示 表达式a+b*(c-d)-e/f 用二叉树表示 表达式a+b*(c-d)-e/f 用二叉树表示 三种遍历算法的比较 三种遍历算法的比较 按层次遍历 A HI B E C D F G J 已知一棵二叉树 先序遍历序列为ABECDFGHIJ 中序遍历序列为EBCDAFHIGJ试画出这颗二叉树。 A B E C D F G H J I 思考：先序、中序、后序序列中任意给定两个 序列就可以画出该二叉树吗为什么？ 已知┅棵二叉树 先序遍历序列为ABECDFGHIJ 中序遍历序列为EBCDAFHIGJ试画出这颗二叉树 A B E C D F G H J I 按层次遍历序列：ABFECGDHJI 给出一棵二叉树的中序遍历：DBGEACHFI与后序遍历：DGEBHIFCA，画出此二叉树 【问题分析】 　　后序遍历中最后访问的是根结点，所以后序遍历DGEBHIFCA序列中A是根结点；根据中序遍历的算法先中序遍历左子树，然後再访问根结点最后再中序遍历右子树，所以中序遍历DBGEACHFI序列中根结点A的两侧分别是左子树和右子树：DBGE、CHFI。 由中根序列和后根序列来确萣二叉树的结构从而判断先根遍历序列及其它。 例1：(NOIP 2001提高组试题) A的右子树中序序列为F H D I J(4) 由(2)知：A的左子树后序序列为C G E B(5) A的右子树后序序列为H F J I D(6) 由(5)(6)知：A的左子树根结点为BA的右子树根结点为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 右子树中序序列为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