52、二叉树遍历：前序、中序、后序、层序

二叉树遍历，说白了就是「怎么把树里的每个节点都走一遍」。

我刚开始学数据结构时，总觉得这玩意儿很玄乎。后来在嵌入式项目里写一个菜单系统，树形结构一上，遍历就成了家常便饭。嗯，今天咱们就把这四种遍历方式彻底捋清楚。

一、先搞清楚「序」是什么

二叉树的遍历，核心就一句话：根节点什么时候被访问。

• 前序（Pre-order）：根 → 左 → 右
• 中序（In-order）：左 → 根 → 右
• 后序（Post-order）：左 → 右 → 根
• 层序（Level-order）：从上到下，从左到右

你想想看，前中后其实指的是「根」的位置。根在前就是前序，根在中间就是中序，根在最后就是后序。层序则是按层来，跟根的位置没关系。

二、递归实现——最直观的方式

递归实现遍历，代码极其简洁。我个人习惯先写递归版本，因为逻辑清晰，不容易出错。

// 二叉树节点定义
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 前序遍历
void preOrder(TreeNode *root) {
    if (root == NULL) return;
    printf("%d ", root->data);  // 访问根
    preOrder(root->left);       // 遍历左子树
    preOrder(root->right);      // 遍历右子树
}

// 中序遍历
void inOrder(TreeNode *root) {
    if (root == NULL) return;
    inOrder(root->left);        // 遍历左子树
    printf("%d ", root->data);  // 访问根
    inOrder(root->right);       // 遍历右子树
}

// 后序遍历
void postOrder(TreeNode *root) {
    if (root == NULL) return;
    postOrder(root->left);      // 遍历左子树
    postOrder(root->right);     // 遍历右子树
    printf("%d ", root->data);  // 访问根
}

你看，三种递归遍历的区别仅仅是 printf 的位置不同。我曾经在面试时被问到「能不能用一行代码区分三种遍历」，其实就是这个道理。

三、非递归实现——面试常考

非递归遍历需要手动维护一个栈。我建议你理解递归的本质，再写非递归版本会轻松很多。

前序非递归

void preOrderIterative(TreeNode *root) {
    if (root == NULL) return;
    TreeNode *stack[100];
    int top = -1;
    stack[++top] = root;
    
    while (top >= 0) {
        TreeNode *node = stack[top--];
        printf("%d ", node->data);
        // 先压右，再压左（因为栈是后进先出）
        if (node->right) stack[++top] = node->right;
        if (node->left)  stack[++top] = node->left;
    }
}

中序非递归

void inOrderIterative(TreeNode *root) {
    TreeNode *stack[100];
    int top = -1;
    TreeNode *curr = root;
    
    while (curr != NULL || top >= 0) {
        // 一路向左，压入栈
        while (curr != NULL) {
            stack[++top] = curr;
            curr = curr->left;
        }
        // 弹出并访问
        curr = stack[top--];
        printf("%d ", curr->data);
        // 转向右子树
        curr = curr->right;
    }
}

后序非递归（双栈法）

void postOrderIterative(TreeNode *root) {
    if (root == NULL) return;
    TreeNode *s1[100], *s2[100];
    int top1 = -1, top2 = -1;
    s1[++top1] = root;
    
    while (top1 >= 0) {
        TreeNode *node = s1[top1--];
        s2[++top2] = node;
        if (node->left)  s1[++top1] = node->left;
        if (node->right) s1[++top1] = node->right;
    }
    
    while (top2 >= 0) {
        printf("%d ", s2[top2--]->data);
    }
}

四、层序遍历——队列登场

层序遍历用队列实现，一层一层往下走。这在嵌入式里很实用，比如按层打印菜单。

void levelOrder(TreeNode *root) {
    if (root == NULL) return;
    TreeNode *queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    while (front < rear) {
        TreeNode *node = queue[front++];
        printf("%d ", node->data);
        if (node->left)  queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;
    }
}

层序的难点在于「按层输出」。如果你想每层单独打印一行，需要记录当前层的节点数。

void levelOrderByLevel(TreeNode *root) {
    if (root == NULL) return;
    TreeNode *queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    while (front < rear) {
        int levelSize = rear - front;  // 当前层节点数
        for (int i = 0; i < levelSize; i++) {
            TreeNode *node = queue[front++];
            printf("%d ", node->data);
            if (node->left)  queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
        printf("\n");  // 换行
    }
}

五、四种遍历对比

遍历方式	访问顺序	数据结构	典型应用
前序	根 → 左 → 右	栈	复制树、序列化
中序	左 → 根 → 右	栈	二叉搜索树排序输出
后序	左 → 右 → 根	栈（双栈）	删除树、计算表达式
层序	从上到下，从左到右	队列	广度优先搜索、按层处理

六、知识结构图

七、避坑指南

我曾经在调试一个树形菜单时，发现层序遍历总是漏掉最后一层。查了半天，原来是队列的 rear 指针越界了。嵌入式环境里数组大小有限，队列长度一定要做边界检查。

• 递归深度：树深度超过栈空间时，改用非递归
• 空指针检查：每次访问 left 和 right 前都要判空
• 队列/栈溢出：静态数组要预留足够空间，或者用动态分配
• 后序非递归：双栈法最稳妥，单栈法容易搞混