bitworld 的博客
【CSP-J初赛】二叉树的遍历
bitworld 最强壮的男人 SU @ 2025-7-28 16:10:44

二叉树的遍历

1. 什么是二叉树？

在讨论遍历之前，我们必须先精确定义我们操作的对象：二叉树。

想象一下家族族谱，但有一个限制：每个人最多只能有两个孩子。这就是二叉树的核心思想。它是一种由节点 (Node) 和连接节点的边 (Edge) 组成的层次结构。

节点 (Node)：存储数据的基本单元。
根节点 (Root)：位于树顶端的唯一节点，它没有父节点。
父节点 (Parent) & 子节点 (Child)：如果一个节点 $A$ 直接连接到另一个节点 $B$ ，且 $A$ 在 $B$ 的上一层，那么 $A$ 是 $B$ 的父节点， $B$ 是 $A$ 的子节点。
子树 (Subtree)：每个节点都可以看作是其下方连接的所有节点构成的更小的树的根，这个更小的树称为该节点的子树。
二叉树 (Binary Tree)：一个特殊的树，其中每个节点最多有两个子节点，分别称为左子节点 (Left Child) 和右子节点 (Right Child)。相应地，它们构成了左子树 (Left Subtree) 和右子树 (Right Subtree)。
叶节点 (Leaf Node)：没有任何子节点的节点。

为了在程序中表示一个二叉树节点，我们通常使用结构体或类：

struct Node {
    int val;      // 节点存储的值
    Node *l, *r;  // 指向左、右子节点的指针

    // 构造函数，方便创建新节点
    Node(int v) : val(v), l(nullptr), r(nullptr) {}
};

一个值为 $v$ 的节点可以这样创建：Node* n = new Node(v);。如果一个节点的左子节点指针为 nullptr，意味着它没有左孩子。

例如，考虑下面这棵二叉树：

      (1)
     /   \
    (2)   (3)
   / \   /
  (4)(5)(6)

节点 $1$ 是根节点。
节点 $2$ 是节点 $1$ 的左子节点，节点 $3$ 是右子节点。
节点 $4, 5, 6$ 是叶节点。
以节点 $2$ 为根，包含节点 $4$ 和 $5$ 的结构是节点 $1$ 的左子树。

2. 树的“遍历”：为何与如何？

遍历 (Traversal) 是指按照某种特定的顺序，系统性地访问树中的每一个节点，且每个节点仅被访问一次。

为什么要遍历？因为我们需要一种标准化的方法来“线性化”树这种非线性结构，以便进行查找、打印、计算、修改等操作。例如，打印出树中所有节点的值，或者计算所有节点值的总和。

核心问题在于：当你位于任意一个节点 $N$ 时，有三件事情可以做：

处理节点 $N$ 本身 (记为 $V$ , Visit)。
遍历 $N$ 的左子树 (记为 $L$ , Left)。
遍历 $N$ 的右子树 (记为 $R$ , Right)。

这三件事的执行顺序，就定义了不同的深度优先遍历。

3. 深度优先遍历 (Depth-First Search, DFS)

深度优先遍历的策略是“一路走到黑再回头”。它会沿着一条路径尽可能深地探索，直到到达一个叶节点，然后才回溯（返回到父节点）去探索另一条路径。根据访问节点本身 ( $V$ )、左子树 ( $L$ )、右子树 ( $R$ ) 的相对顺序，DFS分为三种主要类型：前序、中序和后序。

3.1 前序遍历 (Pre-order Traversal)

规则： $V \rightarrow L \rightarrow R$ (访问根节点 $\rightarrow$ 遍历左子树 $\rightarrow$ 遍历右子树)

过程：

访问当前节点。
递归地对当前节点的左子树进行前序遍历。
递归地对当前节点的右子树进行前序遍历。

示例：对我们之前的树进行前序遍历。

      (1)
     /   \
    (2)   (3)
   / \   /
  (4)(5)(6)

从根节点 1 开始。访问 1。序列：1。
去左子树（根为 2）。访问 2。序列：1, 2。
去 2 的左子树（根为 4）。访问 4。序列：1, 2, 4。
4 没有子节点，返回到 2。
去 2 的右子树（根为 5）。访问 5。序列：1, 2, 4, 5。
5 没有子节点，返回到 2。2 的左右子树都遍历完了，返回到 1。
去 1 的右子树（根为 3）。访问 3。序列：1, 2, 4, 5, 3。
去 3 的左子树（根为 6）。访问 6。序列：1, 2, 4, 5, 3, 6。
6 没有子节点，返回到 3。
3 没有右子树，遍历完成。

最终前序遍历序列：$1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 3 \rightarrow 6$

递归实现：

void pre(Node* u) {
    if (!u) return; // 如果节点为空，直接返回
    cout << u->val << " "; // V: 访问根节点
    pre(u->l);             // L: 遍历左子树
    pre(u->r);             // R: 遍历右子树
}

递归的实现简洁地体现了 $V \rightarrow L \rightarrow R$ 的定义。

迭代实现 (使用栈)：递归的本质是利用了系统的函数调用栈。我们可以手动模拟这个过程。

#include<bits/stdc++.h>
using namespace std;

// 节点定义
struct Node {
    int val;
    Node *l, *r;
    Node(int v) : val(v), l(nullptr), r(nullptr) {}
};

// 迭代前序遍历
void preIter(Node* rt) {
    if (!rt) return;
    stack<Node*> stk;
    stk.push(rt);
    while (!stk.empty()) {
        Node* cur = stk.top();
        stk.pop();
        cout << cur->val << " ";
        // 注意：先推右孩子，再推左孩子
        // 因为栈是后进先出(LIFO)，所以后推的左孩子会先被访问
        if (cur->r) stk.push(cur->r);
        if (cur->l) stk.push(cur->l);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    // 构建示例树
    Node* root = new Node(1);
    root->l = new Node(2);
    root->r = new Node(3);
    root->l->l = new Node(4);
    root->l->r = new Node(5);
    root->r->l = new Node(6);

    preIter(root); // 输出: 1 2 4 5 3 6 
    cout << endl;

    return 0;
}

复杂度：时间 $O(N)$ ，因为每个节点入栈、出栈各一次。空间 $O(H)$ ，其中 $H$ 是树的高度。最坏情况下（树退化成链表）， $H=N$ ，空间复杂度为 $O(N)$ 。

3.2 中序遍历 (In-order Traversal)

规则： $L \rightarrow V \rightarrow R$ (遍历左子树 $\rightarrow$ 访问根节点 $\rightarrow$ 遍历右子树)

过程：

递归地对当前节点的左子树进行中序遍历。
访问当前节点。
递归地对当前节点的右子树进行中序遍历。

示例：

      (1)
     /   \
    (2)   (3)
   / \   /
  (4)(5)(6)

从根节点 1 开始。先去左子树（根为 2）。
在 2 这里，还是先去它的左子树（根为 4）。
在 4 这里，它没有左子树。访问 4。序列：4。4 也没有右子树，返回到 2。
2 的左子树遍历完了。访问 2。序列：4, 2。
去 2 的右子树（根为 5）。
在 5 这里，它没有左子树。访问 5。序列：4, 2, 5。5 也没有右子树，返回到 2。
2 的左右子树都遍历完了，返回到 1。
1 的左子树遍历完了。访问 1。序列：4, 2, 5, 1。
去 1 的右子树（根为 3）。
在 3 这里，先去它的左子树（根为 6）。
在 6 这里，它没有左子树。访问 6。序列：4, 2, 5, 1, 6。返回到 3。
3 的左子树遍历完了。访问 3。序列：4, 2, 5, 1, 6, 3。
3 没有右子树，遍历完成。

最终中序遍历序列：$4 \rightarrow 2 \rightarrow 5 \rightarrow 1 \rightarrow 6 \rightarrow 3$

重要特性：对于二叉搜索树 (Binary Search Tree, BST)，若按无重复键或固定的重复处理规则（例如，小于等于放左子树，大于放右子树），则其中序遍历会得到一个单调不减或严格递增的序列。

递归实现：

void in(Node* u) {
    if (!u) return;
    in(u->l);             // L: 遍历左子树
    cout << u->val << " "; // V: 访问根节点
    in(u->r);             // R: 遍历右子树
}

迭代实现 (使用栈)：中序的迭代实现比前序稍复杂，因为它需要先深入左子树的尽头。

void inIter(Node* rt) {
    if (!rt) return;
    stack<Node*> stk;
    Node* cur = rt;
    while (cur || !stk.empty()) {
        // 一直向左走，将路径上的节点全部入栈
        while (cur) {
            stk.push(cur);
            cur = cur->l;
        }
        // 当左边走不通了，从栈中弹出一个节点并访问它
        cur = stk.top();
        stk.pop();
        cout << cur->val << " ";
        // 转向右子树，并对右子树重复这个过程
        cur = cur->r;
    }
}

复杂度：时间 $O(N)$ ，空间 $O(H)$ 。

3.3 后序遍历 (Post-order Traversal)

规则： $L \rightarrow R \rightarrow V$ (遍历左子树 $\rightarrow$ 遍历右子树 $\rightarrow$ 访问根节点)

过程：

递归地对当前节点的左子树进行后序遍历。
递归地对当前节点的右子树进行后序遍历。
访问当前节点。

应用场景：后序遍历的一个典型应用是计算器中的后缀表达式求值。另一个是释放树的内存，因为必须先释放子节点的内存，才能安全地释放父节点的内存。

示例：

      (1)
     /   \
    (2)   (3)
   / \   /
  (4)(5)(6)

从根 1 开始，去左子树（根为 2）。
在 2 这里，去左子树（根为 4）。
4 没有子节点，可以认为它的左右子树都遍历完了。访问 4。序列：4。返回到 2。
在 2 这里，左子树已遍历，去右子树（根为 5）。
5 没有子节点，访问 5。序列：4, 5。返回到 2。
在 2 这里，左右子树都已遍历。访问 2。序列：4, 5, 2。返回到 1。
在 1 这里，左子树已遍历，去右子树（根为 3）。
在 3 这里，去左子树（根为 6）。
6 没有子节点，访问 6。序列：4, 5, 2, 6。返回到 3。
在 3 这里，左子树已遍历，它没有右子树。访问 3。序列：4, 5, 2, 6, 3。返回到 1。
在 1 这里，左右子树都已遍历。访问 1。序列：4, 5, 2, 6, 3, 1。

最终后序遍历序列：$4 \rightarrow 5 \rightarrow 2 \rightarrow 6 \rightarrow 3 \rightarrow 1$

递归实现：

void post(Node* u) {
    if (!u) return;
    post(u->l);            // L: 遍历左子树
    post(u->r);            // R: 遍历右子树
    cout << u->val << " "; // V: 访问根节点
}

迭代实现 (使用双栈或单栈+反转)：后序的迭代实现是最不直观的。一个巧妙的方法是利用前序遍历。标准前序遍历是 $V \rightarrow L \rightarrow R$ 。如果我们修改它为 $V \rightarrow R \rightarrow L$ ，得到的序列再反转一下，就是 $L \rightarrow R \rightarrow V$ ，即后序遍历。

void postIter(Node* rt) {
    if (!rt) return;
    stack<Node*> s1, s2;
    s1.push(rt);
    while (!s1.empty()) {
        Node* cur = s1.top();
        s1.pop();
        s2.push(cur); // 将 V->R->L 的访问顺序存入s2
        if (cur->l) s1.push(cur->l);
        if (cur->r) s1.push(cur->r);
    }
    // s2中的顺序是 V->R->L，依次弹出即为 L->R->V
    while (!s2.empty()) {
        cout << s2.top()->val << " ";
        s2.pop();
    }
}

复杂度：时间 $O(N)$ ，空间 $O(N)$ （因为用了两个栈，最坏情况下都可能存 $N$ 个元素）。

4. 广度优先遍历 (Breadth-First Search, BFS)

与DFS深入探索的策略不同，BFS采用“逐层扫描”的方式。它会先访问完第一层的所有节点，然后是第二层，以此类推。

4.1 层序遍历 (Level-order Traversal)

这是广度优先搜索（BFS）在树上最经典和常见的应用。 严格来说，只要遵循“按层优先”的原则，同一层内部的访问顺序可以是多样的（如从右到左、之字形等），但本文仅讨论从上到下、从左到右的标准层序遍历。

规则：从上到下，从左到右，逐层访问节点。

过程：使用一个队列 (Queue) 来实现，队列的特性是先进先出 (First-In, First-Out)。

将根节点入队。
当队列不为空时，循环执行以下操作： a. 从队头取出一个节点。 b. 访问该节点。 c. 如果该节点有左孩子，将左孩子入队。 d. 如果该节点有右孩子，将右孩子入队。

示例：

      (1)
     /   \
    (2)   (3)
   / \   /
  (4)(5)(6)

队列 Q：[]。将根节点 1 入队。Q：[1]。
Q 不空。出队 1，访问。序列：1。将 1 的孩子 2 和 3 入队。Q：[2, 3]。
Q 不空。出队 2，访问。序列：1, 2。将 2 的孩子 4 和 5 入队。Q：[3, 4, 5]。
Q 不空。出队 3，访问。序列：1, 2, 3。将 3 的孩子 6 入队。Q：[4, 5, 6]。
Q 不空。出队 4，访问。序列：1, 2, 3, 4。4 无孩子。Q：[5, 6]。
Q 不空。出队 5，访问。序列：1, 2, 3, 4, 5。5 无孩子。Q：[6]。
Q 不空。出队 6，访问。序列：1, 2, 3, 4, 5, 6。6 无孩子。Q：[]。
Q 为空，遍历结束。

最终层序遍历序列：$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 6$

实现：

void levelOrder(Node* rt) {
    if (!rt) return;
    queue<Node*> q;
    q.push(rt);
    while (!q.empty()) {
        Node* cur = q.front();
        q.pop();
        cout << cur->val << " ";
        if (cur->l) q.push(cur->l);
        if (cur->r) q.push(cur->r);
    }
}

复杂度：时间 $O(N)$ ，每个节点入队出队一次。空间复杂度为 $O(W)$ ，其中 $W$ 是树的最大宽度。在最坏情况下，即一个底层节点密集的完全二叉树，其宽度 $W$ 可以达到 $\Theta(N)$ （例如，满二叉树的最后一层约有 $N/2$ 个节点），因此空间复杂度的上界是 $O(N)$ 。而在最好的情况下，即树退化为一条链，宽度恒为 1，空间复杂度仅为 $O(1)$ 。

5. 遍历的应用：从遍历序列重建二叉树

一个非常经典的考点是：给你一个或多个遍历序列，要求你重建出唯一的原始二叉树。

核心结论：

只给前序、后序、层序中的任意一种，无法唯一确定一棵树。
只给中序，也无法唯一确定一棵树。
（前序 + 中序） 或 （后序 + 中序） 可以唯一确定一棵二叉树。
（前序 + 后序）一般不行，除非是每个节点度为0或2的满二叉树。

为什么必须有中序遍历？因为中序遍历的序列中，根节点的左边是其所有左子树的节点，右边是其所有右子树的节点。这为我们提供了划分左右子树的依据。

5.1 根据前序和中序遍历重建

思路：

确定根：前序遍历的第一个元素永远是当前 (子)树的根节点。
划分左右子树：在中序遍历中找到这个根节点。它左边的所有元素构成左子树的中序遍历，右边的所有元素构成右子树的中序遍历。
确定子树的前序遍历：根据左子树的节点数量（可以从中序划分中得知），在前序遍历中（根节点之后）划分出相应数量的元素，作为左子树的前序遍历。剩下的部分就是右子树的前序遍历。
递归构建：对左、右子树递归地执行以上步骤。

题意概括：给定前序遍历数组 pre 和中序遍历数组 in，构建二叉树。

#include<bits/stdc++.h>
using namespace std;

// 节点定义
struct Node {
    int val;
    Node *l, *r;
    Node(int v) : val(v), l(nullptr), r(nullptr) {}
};

// 辅助哈希表，用于O(1)查找中序遍历中元素的位置
// 为了效率，此表应在调用build函数前预处理好
unordered_map<int, int> pos;

Node* build(const vector<int>& pre, const vector<int>& in, int preL, int preR, int inL, int inR) {
    if (preL > preR) return nullptr;

    // 1. 前序第一个是根
    int rootVal = pre[preL];
    Node* root = new Node(rootVal);
    
    // 2. 在中序中找到根，划分左右
    int k = pos[rootVal];
    int leftSize = k - inL;

    // 3. 递归构建
    root->l = build(pre, in, preL + 1, preL + leftSize, inL, k - 1);
    root->r = build(pre, in, preL + leftSize + 1, preR, k + 1, inR);
    
    return root;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    vector<int> pre_order = {1, 2, 4, 5, 3, 6};
    vector<int> in_order = {4, 2, 5, 1, 6, 3};
    
    for (int i = 0; i < in_order.size(); ++i) {
        pos[in_order[i]] = i;
    }

    Node* root = build(pre_order, in_order, 0, pre_order.size() - 1, 0, in_order.size() - 1);
    
    // 验证，例如用后序遍历打印
    // 期望输出: 4 5 2 6 3 1
    function<void(Node*)> post_print = 
        [&](Node* u) {
        if (!u) return;
        post_print(u->l);
        post_print(u->r);
        cout << u->val << " ";
    };
    post_print(root);
    cout << endl;

    return 0;
}

复杂度：时间 $O(N)$ ，因为哈希表查找是 $O(1)$ ，每个节点只访问一次。空间 $O(N)$ 用于存储哈希表和递归栈。

5.2 根据后序和中序遍历重建

思路与上面几乎完全一样，唯一的区别在于：

确定根：后序遍历的最后一个元素是当前 (子)树的根节点。

题意概括：给定后序遍历数组 post 和中序遍历数组 in，构建二叉树。

// ... Node定义保持不变 ...
// 注意：此函数同样依赖于在调用点预先填充好的哈希表 pos
extern unordered_map<int, int> pos;

Node* build(const vector<int>& post, const vector<int>& in, int postL, int postR, int inL, int inR) {
    if (postL > postR) return nullptr;

    // 1. 后序最后一个是根
    int rootVal = post[postR];
    Node* root = new Node(rootVal);

    // 2. 在中序中找到根，划分左右
    int k = pos[rootVal];
    int leftSize = k - inL;

    // 3. 递归构建
    // 注意后序数组的索引计算
    root->l = build(post, in, postL, postL + leftSize - 1, inL, k - 1);
    root->r = build(post, in, postL + leftSize, postR - 1, k + 1, inR);
    
    return root;
}

复杂度：同样是时间 $O(N)$ ，空间 $O(N)$ 。

6. 例题

6.1 判断题

一棵非空二叉树，其前序遍历和后序遍历序列一定不同。
- 答案：错误。这是一个反例驱动的判断。如果一棵二叉树仅包含一个根节点，那么它的前序遍历和后序遍历序列都是该节点本身，两者是相同的。因此，“一定不同”的论断是错误的。
已知一棵二叉树的前序遍历和中序遍历序列，可以唯一确定这棵二叉树。
- 答案：正确。前序遍历提供了根节点的顺序，而中序遍历通过根节点的位置划分了左、右子树。这两个信息结合，足以递归地、无歧义地重建整棵树的结构。
对于任意二叉树，其中序遍历序列中，任意一个节点的右子树中的所有节点都在它的右边。
- 答案：正确。这源于中序遍历的定义 ( $L \rightarrow V \rightarrow R$ )。在访问一个节点 $V$ 之前，其整个左子树 $L$ 已经被访问完毕；在访问完 $V$ 之后，才会去访问其整个右子树 $R$ 。因此，在最终的线性序列中， $V$ 必然出现在其所有左子树节点之后，并出现在其所有右子树节点之前。

6.2 选择题

一棵二叉树的前序遍历是 GDAFEMHZ，中序遍历是 ADEFGHMZ，则其后序遍历是？ A. AEFDMHGZ B. AEDFHMZG C. ADEFHMZG D. AEDFMHGZ
- 解题思路：这是一个通过遍历序列重建树并求解另一遍历序列的典型问题。我们将严格按照步骤进行推导。
  1. 确定根节点：前序遍历的第一个元素是树的根。前序序列为 GDAFEMHZ，因此根节点是 G。
  2. 划分左、右子树：在中序遍历序列 ADEFGHMZ 中找到根节点 G。
    - G 左侧的 ADEF 是其左子树的中序遍历。
    - G 右侧的 HMZ 是其右子树的中序遍历。
  3. 确定子树的前序遍历：左子树有4个节点 (A,D,E,F)。在前序序列中，根节点 G 之后紧邻的4个节点 DAFE 构成了左子树的前序遍历。剩下的 MHZ 则是右子树的前序遍历。
  4. 递归构建左子树：
    - 前序: DAFE，中序: ADEF。
    - 根是 D。在中序 ADEF 中，D 的左边是 A (左子树)，右边是 EF (右子树)。
    - 对于 D 的左子树：前序 A，中序 A。这是一个单节点 A。
    - 对于 D 的右子树：前序 FE，中序 EF。根是 F。在中序 EF 中，F 的左边是 E，右边为空。所以 F 的左孩子是 E。
    - 左子树结构为：D 的左孩子是 A，右孩子是 F，F 的左孩子是 E。
  5. 递归构建右子树：
    - 前序: MHZ，中序: HMZ。
    - 根是 M。在中序 HMZ 中，M 的左边是 H，右边是 Z。
    - 因此，M 的左孩子是 H，右孩子是 Z。
  6. 整合并求后序遍历：我们得到的完整树结构如下：
```
      G
     / \
    D   M
   / \ / \
  A  F H  Z
     /
    E
```
    现在，我们根据 $L \rightarrow R \rightarrow V$ 的规则求后序遍历：
    - 首先遍历 G 的左子树（根为 D），得到后序序列 A E F D。
    - 然后遍历 G 的右子树（根为 M），得到后序序列 H Z M。
    - 最后访问根节点 G。
    - 将各部分拼接，最终的后序遍历序列是 AEFDHZMG。
  - 结论：通过严谨的推导，我们得到的正确后序遍历序列为 AEFDHZMG。将此结果与所给选项对比，发现没有任何一个选项与之匹配。在正式的笔试或竞赛中，这种情况意味着题目本身或所给选项可能存在错误。解题时应相信自己清晰的逻辑推导过程。
一个栈用来实现二叉树的何种遍历最合适？ A. 中序遍历 B. 前序遍历 C. 后序遍历 D. 层序遍历
- 答案：B。
  - 前序遍历 ( $V \rightarrow L \rightarrow R$ ) 的迭代实现与栈的“后进先出”特性完美契合。基本逻辑是：弹出并访问当前节点，然后将其右孩子、再将其左孩子推入栈中。这样能确保左孩子比右孩子先被处理。
  - 中序和后序遍历 的迭代实现虽然也用栈，但逻辑更为复杂，通常需要辅助指针或额外处理，不如前序遍历那样直接。
  - 层序遍历 使用队列（先进先出）实现，而非栈。
  - 评注：中序/后序也能用单栈，但实现细节更繁琐，这里选 B 侧重 ‘最直接’ 而非 ‘唯一可行’。

6.3 程序阅读题

题意概括：分析以下代码，并写出对给定示例树的输出结果。

#include<bits/stdc++.h>
using namespace std;
struct Node { int val; Node *l, *r; Node(int v):val(v),l(nullptr),r(nullptr){} };

void fn(Node* u) {
    if (!u) return;
    if (u->l) fn(u->l);
    if (u->r) fn(u->r);
    cout << u->val << " ";
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    Node* root = new Node(1);
    root->l = new Node(2); root->r = new Node(3);
    root->l->l = new Node(4); root->l->r = new Node(5);
    root->r->l = new Node(6);
    fn(root);
    return 0;
}

分析：函数 fn 内部的执行顺序是：先对左子树 u->l 进行递归调用，再对右子树 u->r 进行递归调用，最后才处理（打印）当前节点 u 的值。这个顺序是典型的 $L \rightarrow R \rightarrow V$ ，即后序遍历。
结果：对于给定的树：
```
      (1)
     /   \
    (2)   (3)
   / \   /
  (4)(5)(6)
```
其后序遍历序列为 $4 \rightarrow 5 \rightarrow 2 \rightarrow 6 \rightarrow 3 \rightarrow 1$。
输出：4 5 2 6 3 1

6.4 程序补全题

题意概括：补全以下代码，使其能正确实现二叉树的层序遍历。

#include<bits/stdc++.h>
using namespace std;
struct Node { int val; Node *l, *r; Node(int v):val(v),l(nullptr),r(nullptr){} };

void levelOrder(Node* rt) {
    if (!rt) return;
    queue<Node*> q;
    q.push(rt);
    while (/*---补全代码 1---*/) {
        Node* cur = q.front();
        q.pop();
        cout << cur->val << " ";
        // ---补全代码 2---
        // ---补全代码 3---
    }
}

int main() {
    // ... main 函数同上 ...
}

分析：层序遍历是广度优先搜索的应用，其核心数据结构是队列。算法流程为：只要队列不为空，就不断从队头取出节点进行访问，并将其非空的左、右孩子依次加入队尾。
补全：
- 代码1: 循环的条件是队列非空，应填写 !q.empty()。
- 代码2: 访问当前节点后，应将其左孩子（如果存在）入队。应填写 if (cur->l) q.push(cur->l);。
- 代码3: 接着将其右孩子（如果存在）入队。应填写 if (cur->r) q.push(cur->r);。

7. 复杂度分析

对于一棵有 $N$ 个节点，高度为 $H$ 的二叉树：

遍历方法	时间复杂度	空间复杂度 (平均/平衡树)	空间复杂度 (最坏情况)
前序 (递归)	$O(N)$	$O(\log N)$	$O(N)$
中序 (递归)
后序 (递归)
前序 (迭代)
中序 (迭代)
后序 (迭代)
层序 (迭代)		$O(N)$

时间复杂度：所有标准的遍历算法都必须访问每个节点一次，因此时间复杂度总是 $O(N)$ 。
空间复杂度：
- 对于深度优先 (DFS) 族（前、中、后序），空间开销主要来自递归栈或手动维护的栈。栈的最大深度等于树的高度 $H$ 。对于一棵平衡二叉树， $H \approx \log_2 N$ 。最坏情况是树退化成链表，此时 $H=N$ 。
- 对于广度优先 (BFS)（层序），空间开销主要来自队列。队列的最大尺寸取决于树最宽一层的节点数 $W$ 。最坏情况是一棵完全二叉树，其宽度 $W$ 可达 $\Theta(N)$ ，此时空间为 $O(N)$ 。最好情况是退化的链表，宽度为 $O(1)$ 。

前序遍历 ( $V \rightarrow L \rightarrow R$ )：常用于复制树结构或表达式树求值。根节点总在最前。

中序遍历 ( $L \rightarrow V \rightarrow R$ )：在二叉搜索树中可以得到有序序列。根节点在中间，划分左右子树。

后序遍历 ( $L \rightarrow R \rightarrow V$ )：常用于释放树的内存或计算后缀表达式。根节点总在最后。

层序遍历 (BFS)：按层级访问，常用于寻找最短路径或需要按层处理的问题。

【CSP-J初赛】二叉树的遍历

二叉树的遍历

1. 什么是二叉树？

2. 树的“遍历”：为何与如何？

3. 深度优先遍历 (Depth-First Search, DFS)

3.1 前序遍历 (Pre-order Traversal)

3.2 中序遍历 (In-order Traversal)

3.3 后序遍历 (Post-order Traversal)

4. 广度优先遍历 (Breadth-First Search, BFS)

4.1 层序遍历 (Level-order Traversal)

5. 遍历的应用：从遍历序列重建二叉树

5.1 根据前序和中序遍历重建

5.2 根据后序和中序遍历重建

6. 例题

6.1 判断题

6.2 选择题

6.3 程序阅读题

6.4 程序补全题

7. 复杂度分析

还没有账户？

登录