C / C++ / 系统课时

前中后序遍历有什么区别

前中后序遍历有什么区别

前序、中序和后序遍历访问的是同一棵二叉树,区别只在于“当前节点”相对左右子树何时被访问。掌握这个顺序后,就能用几乎相同的递归框架实现三种遍历,并根据输出结果判断程序采用了哪一种规则。

学习目标

  • 区分前序、中序、后序遍历访问根节点的时机
  • 用递归函数实现三种深度优先遍历
  • 根据树结构推导三种遍历产生的节点序列

三种遍历只差根节点的位置

对任意一个非空节点,都可以把要处理的内容看成三部分:当前节点、左子树、右子树。三种遍历都先完整处理一侧子树再处理另一侧,真正变化的是当前节点位于三个动作中的哪个位置。

  • 前序:当前节点 → 左子树 → 右子树
  • 中序:左子树 → 当前节点 → 右子树
  • 后序:左子树 → 右子树 → 当前节点

同一二叉树的前中后序遍历对比

把“访问当前节点”的代码分别放在递归调用之前、两次递归之间或两次递归之后,就得到了三种遍历。这也是记忆它们最稳定的方法,而不是单独背诵一组节点序列。

用递归实现三种遍历

下面构造一棵包含六个节点的二叉树,并分别执行三种遍历。每个递归函数遇到 NULL 就直接返回,因此叶子节点不存在的孩子不会继续访问。

c
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode *create_node(int data) {
    TreeNode *node = malloc(sizeof(TreeNode));
    if (node == NULL) {
        exit(EXIT_FAILURE);
    }
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void preorder(const TreeNode *root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

void inorder(const TreeNode *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

void postorder(const TreeNode *root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

void free_tree(TreeNode *root) {
    if (root == NULL) return;
    free_tree(root->left);
    free_tree(root->right);
    free(root);
}

int main(void) {
    TreeNode *root = create_node(1);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(4);
    root->left->right = create_node(5);
    root->right->right = create_node(6);

    printf("前序: ");
    preorder(root);
    printf("\n中序: ");
    inorder(root);
    printf("\n后序: ");
    postorder(root);
    printf("\n");

    free_tree(root);
    return 0;
}

预期输出

text
前序: 1 2 4 5 3 6
中序: 4 2 5 1 3 6
后序: 4 5 2 6 3 1

怎样手工推导访问顺序

以前序为例,从根节点 1 开始,先访问当前节点,然后完整进入左子树。左子树的根是 2,因此先得到 1 2,接着访问 4 和 5;左子树结束后才进入右子树 3,最后访问它的右孩子 6。

中序遍历则会尽可能先向左走,所以最左侧的 4 最先输出。处理完 4 后回到 2,再访问 5,直到根节点 1 的整个左子树处理完成后才输出 1。

后序把当前节点放在最后,因此父节点一定晚于自己的左右子树输出。根节点 1 要等整棵左子树和整棵右子树都处理完,才成为最后一个结果。

三种顺序适合什么场景

前序会先看到父节点,适合需要先处理节点再处理子结构的任务,例如复制一棵树时先创建当前节点。中序在二叉搜索树中尤其重要,因为按“左、根、右”访问可以得到按键值排序的序列。后序则先处理孩子再处理父节点,释放整棵动态二叉树就是典型用途。

判断遍历类型时,不要只看某几个相邻节点,而要检查根节点相对整个左、右子树的位置:根最先出现是前序,夹在左右子树之间是中序,最后出现则是后序。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

前中后序遍历有什么区别

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通