二叉树有三种遍历方式:先序遍历,中序遍历,后续遍历
1.先序遍历
(1)访问根结点；
(2)先序遍历左子树；
(3)先序遍历右子树。
2.中序遍历
(1)中序遍历左子树；
(2)访问根结点；
(3)中序遍历右子树。
3.后序遍历
(1)后序遍历左子树；
(2)后序遍历右子树；
(3)访问根结点。
我们只要知道 先序中序或 后序中序 就能确定一棵二叉树 如果我们只知道 先序 后续 是无法确定一棵二叉树的
以 2009年上半年程序员上午试题38题为例
某二叉树的先序遍历序列为ABFCDE、中序遍历序列为BFADCE，则该二叉树根的左孩子和右孩子结点分别是（38）。
(38)A.B 和 F B.F 和 B C.B 和 C D.C 和 B
首先 题中给我们了 这棵二叉树 的先序序列和中序序列
通过先序序列 我们能够知道第一个字母是根节点 也就是 节点A 为 整个二叉树的根节点(因为先序序列首先访问的就是根节点)
通过中序序列 我们能够通过根节点A 判断二叉树的左子节点有BF 右子节点有DCE (因为根节点将整棵二叉树分为左右两边,可以通过中序序列来确定左右子树都有哪些节点)
这个时候我们可以先画出根节点及左右子树都有哪些节点
接下来我们看 先序序列 ABFCDE 把根节点去除 BFCDE 这个时候先序遍历是先访问根节点然后再访问左子树最后右子树.那么BFCDE 这个序列中的B 为 左子树的根节点.序列中去掉左子树的节点和根节点 还剩 CDE 这三个节点 那么C节点则为右子树的根节点(因为先序遍历是先访问根节点的,而C在序列的开头则C为右子树根节点)
现在我们知道了这棵二叉树的根节点和左子树,右子树的根节点,接下来就要确定左子树剩下的F节点是在左子树的左边还是右边
首先我们假设F节点在B节点的左侧
用先序序列ABFCDE验证:先访问根节点(A),先序遍历左子树(BF),左子树先访问根节点(B),再遍历左子树左节点(F).先序遍历看起来没问题,那么我们用中序序列BFADCE去验证下:首先访问左子树(BF),左子树中先访问左节点(F),再访问左子树根节点(B) 貌似不对 因为这样 中序遍历应该是以 FB开头 而不是 BF开头,那么将F节点放到B节点右侧
这回左子树就对了 先序遍历:先访问根节点A,再访问左子树,左子树先访问根节点B,然后要访问左节点,但是左节点没有,所以继续访问,访问右节点F. 中序遍历:先访问左子树,然后是左子树的左节点,依然为空,则继续访问左子树根节点B,然后访问左子树右节点F
用同样的方法可以确定右子树,右子树的根节点为C 中序遍历右子树为DCE 则 先访问右子树左节点D 然后访问右子树根节点C 最后访问右子树右节点E. 整个二叉树如图:
这道题正确答案为 C