C++中二叉树的前序（后序、中序）遍历分别是什么意思？相应的树图怎么看？

Question

例如：已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是什么？为什么？

Answer 1

二叉树的遍历是指按照一定次序访问树中所有结点，并且每个节点仅被访问一次的过程。

1、先序遍历（前序）

（1）访问根节点；

（2）先序遍历左子树；

（3）先序遍历右子树。

2、中序遍历

（1）中序遍历左子树；

（2）访问根节点；

（3）中序遍历右子树。

3、后序遍历

（1）后序遍历左子树；

（2）后序遍历右子树‘

（3）访问根节点。

记住访问根结点的时机就可以区分三种遍历方法了。

同时知道一棵二叉树的先序序列和中序序列，或者同时知道中序序列和后序序列，就能确定这棵二叉树的结构。构造算法相信你已经学习过，在任一本介绍数据结构的书上应该也有描述的。由于涉及到算法细节，这里就不细说了。

下面根据你例子中给出的序列来介绍确定二叉树结构的步骤：

（1）后序序列中最后一个为树的根节点，即c为二叉树的根结点；

（2）中序遍历中根节点把序列分为左右子树的中序遍历序列两个部分，在你的例子在右子树没有中序遍历序列（中序遍历序列中c右边没有序列），故可知二叉树的左子树的后序遍历序列为dabe，中序遍历序列为deba；

（3）应用（1）的方法，确定c的左子树的根结点为e，并把以e为根结点的子树的中序遍历序列划分为d（以e为根结点的左子树的中序遍历序列）和ba（以e为根结点的右子树的中序遍历序列）两个部分，后序遍历序列为dab；

（4）应用（1）的方法，可确定e的左结点为b；

（5）应用（1）的方法，可确定e的右结点为a；

（6）最后，可确定a无左结点，右结点为d。

构造的二叉树如图中所示。

那么可获得前序遍历序列为cedba

Answer 2

前序：根、左、右
后序：左、右、根
中序：左、根、右