二叉树遍历详解：前序、中序、后序与层序

二、二叉树前序遍历

1. 前序遍历的操作

A. 若此棵树为空树，即根节点为 NULL，不进行任何操作。 B. 若此棵树不为空，即根节点不为 NULL，进行如下操作：

1. 访问根节点
2. 先序遍历左子树
3. 先序遍历右节点

所以前序遍历可简记为：根 左 右 的顺序进行遍历。具体逻辑可通过递归函数形式实现。

前序遍历的结果如下图所示：

如果不省略空节点的打印即为：1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL 如果省略空节点的打印即为：1 2 3 4 5 6

2. 前序遍历代码实现

// 前序遍历
void PrevOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    printf("%d ", root->data);
    PrevOrder(root->left);
    PrevOrder(root->right);
}

3. 递归调用图

三、二叉树中序遍历

1. 中序遍历的操作

A. 若此棵树为空树，即根节点为 NULL，不进行任何操作。 B. 若此棵树不为空，即根节点不为 NULL，进行如下操作：

1. 中序访问左子树
2. 访问根节点
3. 中序遍历右节点

所以中序遍历可简记为：左 根 右 的顺序进行遍历。

中序遍历的结果如下图所示：

如果不省略空节点的打印即为：NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL 如果省略空节点的打印即为：3 2 1 5 4 6

2. 中序遍历代码实现

// 中序遍历
void InOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}

四、二叉树后序遍历

1. 后序遍历的操作

A. 若此棵树为空树，即根节点为 NULL，不进行任何操作。 B. 若此棵树不为空，即根节点不为 NULL，进行如下操作：

1. 后序访问左子树
2. 访问根节点
3. 后序遍历右节点

所以后序遍历可简记为：左 右 根 的顺序进行遍历。

后序遍历的结果如下图所示：

如果不省略空节点的打印即为：NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1 如果省略空节点的打印即为：3 2 5 6 4 1

2. 后序的遍历代码实现

// 后序遍历
void PostOrder(BTNode* root) {
    if (root == NULL) {
        printf("NULL ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->data);
}

五、二叉树层序遍历

1. 层次遍历的操作

进行层次遍历时需要借助一个队列，层次遍历的核心思想为：上一层的节点出队，带入下一层的节点入队。

1. 将二叉树的根结点入队；
2. 若队列非空，则队头结点出队并访问该结点，若它有左孩子，则将其左孩子入队；若它有右孩子，则将其右孩子入队；

下图为二叉树的层次遍历，即按照箭头所指的方向，按照自上而下，自左向右的顺序对二叉树的各个结点进行逐层访问。

可以得到下图二叉树的层次遍历序列为：1 2 3 4 5 6

2. 层序遍历代码实现

// 层序遍历
// 上一层节点出队，带入下一层节点入队
void TreeLevelOrder(BTNode* root) {
    Queue q;
    QueueInit(&q);
    if (root) QueuePush(&q, root);
    while (!QueueEmpty(&q)) {
        BTNode* front = QueueFront(&q);
        QueuePop(&q);
        printf("%d ", front->data);
        if (front->left) QueuePush(&q, front->left);
        if (front->right) QueuePush(&q, front->right);
    }
    QueueDestroy(&q);
}

六、小试牛刀

1. 练习一

二叉树的前序（先序）遍历为：EFHIGJK，二叉树的中序遍历：HFIEJKG，则二叉树为？

核心思路：由前序遍历确定根，中序遍历确定左右子树。 前序遍历的特点：根 左子树 右子树 中序遍历的特点：左子树 根 右子树 所以对于前序遍历而言，从左往右进行的过程就是相当于对根的遍历，而通过根的确定，对中序序列进行分割左右子树。

2. 练习二

二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树的形状为？

核心思路：由后序遍历确定根，中序遍历确定左右子树。 后序遍历的特点：左子树 右子树 根 中序遍历的特点：左子树 根 右子树 对于后序序列从右往左的过程，就相当于对根进行确定，而通过根的确定，对中序序列进行分割左右子树。

3. 练习三

二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF，则按层次输出（同一层从左到右）的序列。

核心思路：由后序遍历确定根，中序遍历确定左右子树。 后序遍历的特点：左子树 右子树 根 中序遍历的特点：左子树 根 右子树 对于后序序列从右往左的过程，就相当于对根进行确定，而通过根的确定，对中序序列进行分割左右子树。

故而：层序遍历的结果为：FEDCBA

4. 练习四

完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH，则该完全二叉树的前序序列为？

由层序遍历的特性：自上而下，自左到右。

故而前序遍历的结果为：ABDHECFG