所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有节点，使得每个节点仅被访问一次。

（1）前序遍历

前序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先访问根节点，然后遍历左子树，最后遍历右子树；并且，在遍历左右子树时，仍然先访问根节点，然后遍历左子树，最后遍历右子树。图1-10中的二叉树，前序遍历序列：ABCDEF。

（2）中序遍历

中序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后访问根节点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根节点，最后遍历右子树。图1-10中的二叉树，中序遍历序列：CBDAEF。

（3）后序遍历

后序遍历是指在访问根节点、遍历左子树与遍历右子树这三者中，首先遍历左子树，然后遍历右子树，最后访问根节点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根节点。图1-10中的二叉树，后序遍历序列：CDBFEA。

例，已知二叉树的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则前序遍历序列是什么？

解题过程如下：

1）从后序中，可以先得到根节点是E，然后再看中序的序列：ABCDEFG，可以发现ABCD位于根节点的左边，而FG位于根节点的右边，于是得到图1-11所示的图形。

2）先来看ABCD这部分，然后看后序序列，在后序序列中有BDCA这一部分，可以确定A是这部分的根，再看中序序列中的ABCD，发现BCD都在A的后面。因此，可以画出如图1-12所示的图形。

3）再看BCD这部分，从后序中看到的顺序是BDC，所以C是这部分的根节点，中序序列是BCD，可以断定B在C的左边，D在C的右边。这样，得到如图1-13所示的图形。
 
4）再看看右边的FG这部分，从后序序列FG和中序FG中，可以推出，G是这部分的根节点，而F位于G的左边。得到如图1-14所示的图形。

5）根据以上步骤合成一个二叉树，如图1-15所示。
 
6）写出前序遍历序列：EACBDGF。