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 要等整棵左子树和整棵右子树都处理完,才成为最后一个结果。
三种顺序适合什么场景
前序会先看到父节点,适合需要先处理节点再处理子结构的任务,例如复制一棵树时先创建当前节点。中序在二叉搜索树中尤其重要,因为按“左、根、右”访问可以得到按键值排序的序列。后序则先处理孩子再处理父节点,释放整棵动态二叉树就是典型用途。
判断遍历类型时,不要只看某几个相邻节点,而要检查根节点相对整个左、右子树的位置:根最先出现是前序,夹在左右子树之间是中序,最后出现则是后序。
按自己的节奏,确认真正理解。