跳转至

EA2-递归遍历

二叉树的递归遍历是数据结构中的基础操作，主要包括前序遍历、中序遍历和后序遍历。下面给出完整的C语言实现。

三种递归遍历实现

1. 前序遍历（根-左-右）

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// 前序遍历：根 -> 左子树 -> 右子树
void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    printf("%d ", root->data);        // 访问根节点
    preorderTraversal(root->left);    // 遍历左子树
    preorderTraversal(root->right);   // 遍历右子树
}

2. 中序遍历（左-根-右）

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// 中序遍历：左子树 -> 根 -> 右子树
void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    inorderTraversal(root->left);     // 遍历左子树
    printf("%d ", root->data);        // 访问根节点
    inorderTraversal(root->right);    // 遍历右子树
}

3. 后序遍历（左-右-根）

C
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
// 后序遍历：左子树 -> 右子树 -> 根
void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }

    postorderTraversal(root->left);   // 遍历左子树
    postorderTraversal(root->right);  // 遍历右子树
    printf("%d ", root->data);        // 访问根节点
}

遍历过程可视化

graph TD
    A[1] --> B[2]
    A --> C[3]
    B --> D[4]
    B --> E[5]

    style A fill:#f9f,stroke:#333
    style B fill:#bbf,stroke:#333
    style C fill:#bbf,stroke:#333
    style D fill:#bfb,stroke:#333
    style E fill:#bfb,stroke:#333

遍历顺序说明： - 前序：1 → 2 → 4 → 5 → 3 - 中序：4 → 2 → 5 → 1 → 3
- 后序：4 → 5 → 2 → 3 → 1

算法分析

时间复杂度

  • 时间复杂度：O(n)，其中n是二叉树的节点数，每个节点恰好被访问一次
  • 空间复杂度：O(h)，其中h是二叉树的高度，主要是递归调用栈的空间开销
  • 最坏情况（退化为链）：O(n)
  • 最好情况（完全二叉树）：O(log n)

递归执行过程（以前序为例）

Text Only
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
preorder(1)
├── print(1)
├── preorder(2)
│   ├── print(2)
│   ├── preorder(4)
│   │   ├── print(4)
│   │   └── return
│   ├── preorder(5)
│   │   ├── print(5)
│   │   └── return
│   └── return
├── preorder(3)
│   ├── print(3)
│   └── return
└── return