二叉树遍历算法详解 – 进阶篇

欢迎来到今天的数据结构教程！二叉树遍历是算法面试的必考题，也是实际开发中的基础技能。

一、二叉树基础

1.1 树的定义

二叉树是每个节点最多有两个子节点的树结构：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

1.2 创建节点

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

二、前序遍历（Preorder）

2.1 遍历顺序

根节点 → 左子树 → 右子树

2.2 递归实现

void preorderRecursive(struct TreeNode* root) {
    if (root == NULL) return;
    
    printf("%d ", root->val);           // 访问根节点
    preorderRecursive(root->left);      // 遍历左子树
    preorderRecursive(root->right);     // 遍历右子树
}

// 示例：
//       1
//      / \
//     2   3
//    / \
//   4   5
// 输出：1 2 4 5 3

2.3 迭代实现（使用栈）

#include <stdlib.h>

void preorderIterative(struct TreeNode* root) {
    if (root == NULL) return;
    
    struct TreeNode* stack[100];
    int top = -1;
    
    stack[++top] = root;
    
    while (top >= 0) {
        struct TreeNode* node = stack[top--];
        printf("%d ", node->val);
        
        // 先压右子树。后压左子树（栈是 LIFO）
        if (node->right) stack[++top] = node->right;
        if (node->left) stack[++top] = node->left;
    }
}

三、中序遍历（Inorder）

3.1 遍历顺序

左子树 → 根节点 → 右子树

3.2 递归实现

void inorderRecursive(struct TreeNode* root) {
    if (root == NULL) return;
    
    inorderRecursive(root->left);       // 遍历左子树
    printf("%d ", root->val);           // 访问根节点
    inorderRecursive(root->right);      // 遍历右子树
}

// 示例（同上树）：4 2 5 1 3
// 重要：二叉搜索树的中序遍历是有序序列！

3.3 迭代实现

void inorderIterative(struct TreeNode* root) {
    struct TreeNode* stack[100];
    int top = -1;
    struct TreeNode* current = root;
    
    while (current != NULL || top >= 0) {
        // 一直向左
        while (current != NULL) {
            stack[++top] = current;
            current = current->left;
        }
        
        current = stack[top--];
        printf("%d ", current->val);
        current = current->right;
    }
}

四、后序遍历（Postorder）

4.1 遍历顺序

左子树 → 右子树 → 根节点

4.2 递归实现

void postorderRecursive(struct TreeNode* root) {
    if (root == NULL) return;
    
    postorderRecursive(root->left);     // 遍历左子树
    postorderRecursive(root->right);    // 遍历右子树
    printf("%d ", root->val);           // 访问根节点
}

// 示例（同上树）：4 5 2 3 1
// 应用：计算树的高度、释放树的内存

4.3 迭代实现（双栈法）

void postorderIterative(struct TreeNode* root) {
    if (root == NULL) return;
    
    struct TreeNode* stack1[100];
    struct TreeNode* stack2[100];
    int top1 = -1, top2 = -1;
    
    stack1[++top1] = root;
    
    // 第一个栈：根→右→左
    while (top1 >= 0) {
        struct TreeNode* node = stack1[top1--];
        stack2[++top2] = node;
        
        if (node->left) stack1[++top1] = node->left;
        if (node->right) stack1[++top1] = node->right;
    }
    
    // 第二个栈：左→右→根
    while (top2 >= 0) {
        printf("%d ", stack2[top2--]->val);
    }
}

五、层序遍历（Level Order）

5.1 遍历顺序

从上到下。从左到右（使用队列）

5.2 实现代码

void levelOrder(struct TreeNode* root) {
    if (root == NULL) return;
    
    struct 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++) {
            struct TreeNode* node = queue[front++];
            printf("%d ", node->val);
            
            if (node->left) queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
        printf("\n");  // 每层换行
    }
}

// 示例（同上树）：
// 第 1 层：1
// 第 2 层：2 3
// 第 3 层：4 5

六、遍历应用

6.1 计算树的高度

int maxDepth(struct TreeNode* root) {
    if (root == NULL) return 0;
    
    int leftHeight = maxDepth(root->left);
    int rightHeight = maxDepth(root->right);
    
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

6.2 查找节点

struct TreeNode* search(struct TreeNode* root, int val) {
    if (root == NULL) return NULL;
    if (root->val == val) return root;
    
    struct TreeNode* leftResult = search(root->left, val);
    if (leftResult != NULL) return leftResult;
    
    return search(root->right, val);
}

6.3 释放树的内存

void freeTree(struct TreeNode* root) {
    if (root == NULL) return;
    
    freeTree(root->left);
    freeTree(root->right);
    free(root);  // 后序遍历释放
}

七、复杂度分析

遍历方式    时间复杂度    空间复杂度
前序        O(n)         O(h)
中序        O(n)         O(h)
后序        O(n)         O(h)
层序        O(n)         O(w)

n = 节点数。h = 树高。w = 最大宽度

八、总结

二叉树遍历是数据结构的基础：

1. 前序：复制树、序列化
2. 中序：二叉搜索树排序
3. 后序：释放内存、计算高度
4. 层序：BFS、层次处理

关注我们获取更多数据结构教程！