二叉树的遍历 - Shaw 的小屋

p32（10.9 分钟）、p33（10.9 分钟）

遍历的定义与难点#

定义：以某种顺序恰好访问树中每个节点一次的过程。

「访问一个节点」= 读取或处理该节点中的数据；这里访问 = 打印节点中的数据。

难点在于树不是线性结构，没有唯一的「下一个」。

1
例如指向根 F，有两个可能方向：向左到 D、向右到 J
2
选了其中一个之后，还得回来走另一个方向

BFS 和 DFS 是遍历/搜索图的通用技术；树只是图的一种特殊形式。

两大类策略#

	特征表述
BFS（广度优先）	先访问同一深度/层级的所有节点，再访问下一层级的节点；对任何一个节点，先访问其所有子节点，然后才访问孙节点
DFS（深度优先）	去到一个子节点，就得先完整处理完这个子节点的整个子树，然后再去下一个子节点

树的 BFS 就是层次序遍历（level order traversal）。

示例树（全篇基准图）#

1
            F              ← L0，深度 0
2
          /   \
3
         D     J           ← L1，深度 1
4
        / \   / \
5
       B   E G   K         ← L2
6
      / \     \
7
     A   C     I           ← L3
8
              /
9
             H             ← L4

BFS / 层序访问顺序：

1
F → D J → B E G K → A C I → H

一层一层、从左往右。

DFS 的三种策略#

相对顺序可以不同，但通常总是先左后右，只有根的位置在变化：

策略	顺序	记忆法
前序 preorder	根 → 左 → 右	DLR
中序 inorder	左 → 根 → 右	LDR
后序 postorder	左 → 右 → 根	LRD

D = 访问数据、L = 左边、R = 右边。写成 VLR（V = visit）也是常见的，这里采用 DLR。

左右根共 6 种排列组合，但实际只用「先左后右」这 3 种。

手推前序遍历#

1
F（读数据）
2
→ 左到 D → 读 D
3
→ 左到 B → 读 B
4
→ 左到 A → 读 A（A 左右皆空）
5
→ B 左子树完成 → 右到 C → 读 C（C 左右空）
6
→ D 左子树完成 → 右到 E → 读 E（E 左右空）
7
→ F 左子树完成 → 右到 J
8
→ J 左到 G → 读 G（G 左空）
9
→ 右到 I → I 左到 H → 读 H（H 左右空）
10
→ I 左子树完成、右子树空 → 回到 J（J 左子树完成）
11
→ 右到 K → 读 K
12
→ 结束

前序序列 = F, D, B, A, C, E, J, G, I, H, K

手推中序遍历#

1
从根先往左 → D → B → A
2
A 左空 → 读 A → A 右空 → A 结束
3
B 左子树完成 → 读 B → 右到 C
4
C 左空 → 读 C → C 右空
5
D 左完成 → 读 D → 右到 E → 读 E
6
F 左子树完成 → 读 F → 再去 F 的右边…

已推出的前缀：A, B, C, D, E, F, …

一个重要结论#

这棵树其实是一棵二叉搜索树（每节点左子树值较小、右子树值较大）。

对 BST 进行中序遍历会得到一个排序列表，完整序列应为 A B C D E F G H I J K。

这条结论是后面「判断是否为 BST」那一节的基础。

后序#

板书上给出了后序结果，字幕里没有。自己推一遍验证。

层次遍历#

为什么单个指针不行#

1
假设一个 current 指针指向正在访问的当前节点：
2
  可以从 F 走到 D（有链接）
3
  但从 D 无法走到 J（D 与 J 之间没有链接），只能从 F 走到 J
4
  而且一旦指针移到 D，甚至回不到 F，因为从 D 到 F 不存在反向链接
5
→ 仅靠一个指针不行

算法：队列 + 已发现节点#

做法：访问一个节点时，把它所有子节点的引用/地址保存在一个队列中，之后再访问它们。

「已发现节点」指的是：其地址我们已知但尚未访问的节点，也就是队列中的节点。

算法步骤：

1
① 最初把根节点的地址入队（表示最初这是唯一的已发现节点）
2
② 只要队列不为空（至少存在一个已发现节点）：
3
     从前端取出一个节点 → 访问它（打印其值）
4
     → 把它的子节点入队（先左孩子、再右孩子）

队列起到的两个作用#

1
① 从一个节点转移时不会丢失其子节点的引用（因为保存着这些引用）
2
② 队列是先入先出（FIFO）结构，所以最先被发现的节点会最先被访问
3
   → 从而得到期望的有序性

第 ② 条就是「为什么必须用队列而不是栈」的答案。

示例走查（根地址设为 400）#

1
入队 400 → 出队访问 F → 左孩子（200）入队、右孩子入队
2
→ 出队 200 访问 → 其子节点入队
3
   （此时 2 个已访问、3 个已发现、6 个未发现）
4
→ 出队 120 访问 → 子节点入队
5
→ … 直到所有节点被访问且队列为空

代码（C++）#

1
void levelOrder(struct btNode *root) {
2
    if (root == NULL) return;              /* 极端情况：空树直接返回 */
3

4
    queue<btNode*> Q;                      /* 创建「指向节点的指针」队列 */
5
    Q.push(root);                          /* 最初唯一已发现节点 = 根 */
6

7
    while (!Q.empty()) {                   /* 只要至少存在一个已发现节点 */
8
        struct btNode *current = Q.front();  /* front() 返回前端元素（不移除） */
9
        printf("%c ", current->data);        /* 访问 = 打印数据 */
10

11
        if (current->left  != NULL) Q.push(current->left);   /* 左孩子入队 */
12
        if (current->right != NULL) Q.push(current->right);  /* 右孩子入队 */
13

14
        Q.pop();                             /* 必须调用 pop 才移除元素 */
15
    }
16
}

front() 只返回元素，并不会从队列中移除元素，必须调用 pop() 才能移除。很多人代码里忘了 pop，结果死循环。

复杂度#

时间复杂度 = O(N)：

1
「访问一个节点」= 读取该节点的数据 + 将其子节点插入队列，两者都是恒定时间
2
每个节点恰好被访问一次 → 总时间与节点数量成正比
3
无论树的形状如何，对于所有情况层序遍历的时间复杂度都是 O(N)

空间复杂度衡量的是随着输入规模增加，额外所用内存的增长速率：

情况	队列最大元素数	空间
最省：每个节点只有一个子节点（链状）	最多 1 个	O(1)
最费：完美二叉树	最深层有 N/2 个节点同时在队列中	O(N)

所以一般情况下空间复杂度是 O(N)，最坏情况也是 O(N)。

这里的最佳/平均/最差情况只是就空间复杂度而言的，所有情况下时间复杂度都将是 O(N)。

BFS vs DFS 对照#

	BFS（层次遍历）	DFS（前/中/后序）
访问顺序	一层一层	一条路走到底再回头
实现手段	队列 + 迭代循环	递归
时间	O(N)	O(N)
空间	O(1) ~ O(N)	O(h)（递归栈）
典型用途	找最短路径、按层处理	表达式树、排序输出

这里 DFS 的手段就是递归，没有用显式栈。递归之所以等价于栈，是因为函数调用本身占用系统调用栈（p29 讲栈帧时铺垫过）。

坑#

前序 = DLR，中序 = LDR，后序 = LRD，名字由根的位置决定；中序遍历 BST 会得到有序序列。
层次遍历必须用队列，用栈会变成深度优先。
front() 只返回不移除，必须 pop()，忘了就死循环。
层次遍历的时间复杂度在所有情况下都是 O(N)，「最好/最坏」只针对空间；空间最省是链状树 O(1)，最费是完美二叉树 O(N)，因为最深层有 N/2 个节点同时在队列里。
树是图的特例，BFS/DFS 是图的通用技术。