二叉树的先序、中序、后序遍历

二叉树的三种遍历方式

先序遍历：根左右

A B D H E I C F J K G

中序遍历：左根右

D H B E I A J F K C G

后序遍历：左右根

H D I E B J K F G C A

一个结论

只给定二叉树的一种遍历序列，是无法唯一确定相应的二叉树。

但是，如果知道了二叉树的中序遍历序列和任意的另一种序列，就可以唯一的确定这棵二叉树。

例子

例子1 已知 中序遍历、先序遍历（可以确定）

中序遍历：D H B E I A J F K C G

先序遍历：A B D H E I C F J K G

1. 先序遍历的根节点在第一个，所以可知 A 为根节点
2. 所以根据中序遍历（D H B E I ）A（ J F K C G），得到了左子树和右子树
3. 先序遍历的第二个节点是 B ，所以左子树的根是 B，(D H) B (E I)
4. 依次类推，就可以画出这棵唯一的树

例子2 已知 中序遍历、后序遍历（可以确定）

中序遍历：D H B E I A J F K C G

后序遍历：H D I E B J K F G C A

1. 后序遍历的根节点在最后一个，所以可知 A 为根节点
2. 所以根据中序遍历（D H B E I ）A（ J F K C G），得到了左子树和右子树
3. 后序遍历的倒数第二个节点是 C ，所以右子树的根是 C，（J F K） C （G）
4. 依次类推，就可以画出这棵唯一的树

例子2 已知 先序遍历、后序遍历（无法确定）

这种情况无法确定这棵树长什么样，因为你只能确定根是什么，但是无法确定左子树和右子树

参考

二叉树的先序、中序、后序遍历序列