图1

1.前序遍历

前序遍历（Preorder traversal），是二叉树遍历的一种，也叫做先根遍历、先序遍历、前序周游，可记做根左右（VLR，注：V = visit that node, L = Left child, R = right child）。前序遍历首先访问根结点，然后遍历左子树，最后遍历右子树。

以上图为例，递归的过程如下（如图2所示，实线访问时输出结果）：

  1. 输出根结点A，接着遍历左子树。
  2. 输出左子树的根结点B，继续遍历B的左子树。
  3. 输出D。
  4. 输出J。J的左、右子树都为空，J这棵子树遍历完毕。
  5. 返回遍历D的右子树，D的右孩子为空，D这棵子树遍历完毕。
  6. 返回接着遍历B的右子树，输出 E、G、H。
  7. B这棵树子树遍历完毕。
  8. 返回继续遍历A的右子树，输出C、F。

最终遍历的输出结果为：A B D J E G H C F 图2

用递归实现的代码示例如下（另一种方式是用堆栈实现）：

#include <iostream>
using namespace std;

struct Node {
    char data;
    struct Node *left;
    struct Node *right;
};

void preorder(struct Node* node)
{
    if (node == NULL)
        return;

    cout << node->data << " "; //first print data of node

    preorder(node->left); //then recur on left sutree

    preorder(node->right); //now recur on right subtree
}

int main()
{
    Node j = {'J', NULL, NULL};
    Node d = {'D', &j, NULL};

    Node g = {'G', NULL, NULL};
    Node h = {'H', NULL, NULL};
    Node e = {'E', &g, &h};

    Node b = {'B', &d, &e};

    Node f = {'F', NULL, NULL};
    Node c = {'C', NULL, &f};
    
    Node a = {'A', &b, &c};

    preorder(&a);
    return 0;
}

2.中序遍历

对于当前结点，先输出它的左孩子，然后输出该结点，最后输出它的右孩子。

图1的中序遍历结果是：J D B G E H A C F

用递归实现的代码示例：

void inorder(struct Node* node)
{
    if (node == NULL)
        return;

    inorder(node->left); //first recur on left sutree
    
    cout << node->data << " "; //then print data of node

    inorder(node->right); //now recur on right subtree
}

3.后序遍历

对于当前结点，先输出它的左孩子，然后输出它的右孩子，最后输出该结点。

图1的后序遍历结果为：J D G H E B F C A

用递归实现的代码示例：

void postorder(struct Node* node)
{
    if (node == NULL)
        return;

    postorder(node->left); //first recur on left sutree

    postorder(node->right); //then recur on right subtree
    
    cout << node->data << " "; //now print data of node
}

4. 根据前序遍历和中序遍历的结果推导树的结构

问题：已知前序遍历: GDAFEMHZ，中序遍历: ADEFGHMZ，求后序遍历。

解题思路（注：一棵子树，不论用前序遍历，中序遍历，还是后序遍历，其所有的元素都是在一块的）

  1. 前序遍历的第一个元素肯定是根结点（例中为G）
  2. 在中序遍历中找到这个元素（例中为G），左边为G的左子树的中序遍历结果（例中为ADEF），右边G的为右子树的中序遍历结果（例中为HMZ）。
  3. 在前序遍历中找到中序左子树（例中为ADEF）对应的前序排列（例中为DAFE），和中序右子树（例中为HMZ）对应的前序（例中为MHZ）。
  4. 对于左子树和右子树重复步骤1~3，即可以得到完整的树。

5. 根据中序遍历和后序遍历的结果推导树的结构

中序遍历：ADEFGHMZ
后序遍历：AEFDHZMG

思路和前一节类似。

6. 作业

1、

【CSP 2019 入门组第一轮 q14】假设一棵二叉树的后序遍历序列为DGJHEBIFCA,中序遍历序列为DBGEHJACIF,则其前序遍历序列为（）。
A. ABCDEFGHIJ   B. ABDEGHJCFI  
C. ABDEGJHCFI   D. ABDEGHJFIC  

2、

【NOIP 2015 普及组初赛 q16】前序遍历序列与中序遍历序列相同的二叉树为( )。
A. 根结点无左子树  
B. 根结点无右子树  
C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树  
D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树  

3、

【NOIP 2013 普及组初赛 q11】二叉树的（ ）第一个访问的节点是根节点。
A. 先序遍历   B. 中序遍历   C. 后序遍历   D. 以上都是  

4、

【NOIP 2012 普及组初赛 q06】如果一棵二叉树的中序遍历是BAC，那么它的先序遍历不可能是（ ）。
A. ABC   B. CBA   C. ACB   D. BAC  

5、

【NOIP 2010 普及组初赛 q17】一棵二叉树的前序遍历序列是ABCDEFG，后序遍历序列是CBFEGDA，则根结点的左子树的结点个数可能是（ ）。
A. 2   B. 3   C. 4   D. 5  

6、

【NOIP 2008 普及组初赛 q13】二叉树T，已知其先根遍历是1 2 4 3 5 7 6（数字为结点的编号，以下同），中根遍历是2 4 1 5 7 3 6，则该二叉树的后根遍历是（ ）。
A. 4 2 5 7 6 3 1   B. 4 2 7 5 6 3 1  
C. 7 4 2 5 6 3 1   D. 4 2 7 6 5 3 1  

7、

【NOIP 2007 普及组初赛 q20】已知7个节点的二叉树的先根遍历是1 2 4 5 6 3 7（数字为节点的编号，以下同），中根遍历是4 2 6 5 1 7 3，则该二叉树的后根遍历是（  ）。
A. 4 6 5 2 7 3 1   B. 4 6 5 2 1 3 7  
C. 4 2 3 1 5 4 7   D. 4 6 5 3 1 7 2