9.2　深度优先遍历：前序、中序、后序

学习目标：学完本节，你能

• 写出三种深度优先遍历，并说清它们唯一的区别；
• 用 2.1 节的"去程/回程"规律一次性记住三种顺序；
• 写出三种遍历的迭代版本，不再依赖递归；
• 说出三种遍历各自适合解决什么问题。

先修：9.1（树的术语）、2.1（递归的去程与回程）。 固定术语：前序遍历、中序遍历、后序遍历、深度优先。 环境与版本：.NET 8 / C# 12。 预计阅读：30 分钟。

一、三种遍历，只差一行代码

"遍历"就是"把每个节点访问一遍"。但对二叉树来说，"访问顺序"有多种选择。

三种深度优先遍历的定义：

代码上，它们唯一的区别就是 result.Add(node.Value) 这一行的位置：

/// <summary>前序：访问自己 -> 递归左 -> 递归右</summary>
static void PreOrder(TreeNode? node, List<int> result)
{
    if (node == null) return;
    result.Add(node.Value);          // ← 在两次递归【之前】
    PreOrder(node.Left, result);
    PreOrder(node.Right, result);
}

/// <summary>中序：递归左 -> 访问自己 -> 递归右</summary>
static void InOrder(TreeNode? node, List<int> result)
{
    if (node == null) return;
    InOrder(node.Left, result);
    result.Add(node.Value);          // ← 夹在两次递归【中间】
    InOrder(node.Right, result);
}

/// <summary>后序：递归左 -> 递归右 -> 访问自己</summary>
static void PostOrder(TreeNode? node, List<int> result)
{
    if (node == null) return;
    PostOrder(node.Left, result);
    PostOrder(node.Right, result);
    result.Add(node.Value);          // ← 在两次递归【之后】
}

"只差一行"不是巧合，而是本节的核心洞察。

三种遍历的"骨架"完全相同（都是"递归左、递归右"），只有"什么时候处理自己"不同。

理解了这一点，你就不需要背三种遍历的代码了 —— 只需要记住"那一行放哪"。

实测（树是 1 为根、2/3 为第二层、4-7 为第三层的完美二叉树）：

  前序（自己→左→右）: 1 2 4 5 3 6 7
  中序（左→自己→右）: 4 2 5 1 6 3 7
  后序（左→右→自己）: 4 5 2 6 7 3 1

二、用"去程/回程"一次性理解

2.1 节讲过一条规律：

写在递归调用【之前】的语句，在【去程】执行（由外向内）； 写在递归调用【之后】的语句，在【回程】执行（由内向外）。

用它来解释三种遍历：

前序 = 去程顺序

  访问 1  →  递归左
              访问 2  →  递归左
                          访问 4  →  ...
                                    访问 5  →  ...
              递归右
              访问 3  →  ...

"访问自己"写在递归之前，所以是去程执行的 —— 一路往下，先访问父节点再访问子节点。

后序 = 回程顺序

  ...一路去程到最左边 4（没有孩子）
     4 回程 → 访问 4
     5 回程 → 访问 5
     2 回程 → 访问 2
     ...
     1 回程 → 访问 1

"访问自己"写在递归之后，所以是回程执行的 —— 先访问完所有后代，才轮到自己。

实测验证：

  前序的访问顺序 = 去程的顺序: 1 2 4 5 3 6 7
  后序的访问顺序 = 回程的顺序: 4 5 2 6 7 3 1

中序比较特殊 —— 它既不在纯去程，也不在纯回程：

它在"访问完左子树、还没访问右子树"的那一刻访问自己。

所以顺序是：一路去程到最左 → 回程访问 → 转向右子树 → 再一路去程……

  4 2 5 1 6 3 7
  ↑     ↑     ↑
 最左  根    右子树

一张图记住三种遍历：

           自己
          /    \
        左      右

  前序：自己 → 左 → 右    （从上往下"扫"过每个节点）
  中序：左 → 自己 → 右    （从左往右"扫"过每个节点）
  后序：左 → 右 → 自己    （从下往上"扫"过每个节点）

想象一只手在树上移动：

• 前序：手从根出发，走到哪就把哪"盖个章"，先盖章再往下走
• 后序：手走到最左下角，往回收的时候才盖章
• 中序：手从左边回来、还没往右去的时候盖章

三、迭代版：不用递归

递归写起来简单，但有栈溢出风险（2.2 节）。三种遍历都能改成迭代：

/// <summary>
/// 前序遍历的迭代版。
/// 注意：因为栈是后进先出，所以要先压【右】再压【左】，
/// 这样左孩子才会先出栈（保证「先左后右」的访问顺序）。
/// </summary>
static List<int> PreOrderIterative(TreeNode? root)
{
    var result = new List<int>();
    if (root == null) return result;

    var stack = new Stack<TreeNode>();
    stack.Push(root);

    while (stack.Count > 0)
    {
        var node = stack.Pop();
        result.Add(node.Value);
        if (node.Right != null) stack.Push(node.Right);   // 先压右
        if (node.Left != null) stack.Push(node.Left);     // 后压左 -> 先出栈
    }
    return result;
}

/// <summary>
/// 中序遍历的迭代版：一路向左压栈，走到头就弹出一个访问，再转向它的右子树。
/// </summary>
static List<int> InOrderIterative(TreeNode? root)
{
    var result = new List<int>();
    var stack = new Stack<TreeNode>();
    var current = root;

    while (current != null || stack.Count > 0)
    {
        while (current != null)          // 一路向左，全部压栈
        {
            stack.Push(current);
            current = current.Left;
        }
        current = stack.Pop();           // 弹出最左的
        result.Add(current.Value);       // 访问它
        current = current.Right;         // 转向右子树
    }
    return result;
}

/// <summary>
/// 后序遍历的迭代版：用「反向」的技巧 —— 按「根右左」的顺序遍历，最后整体反转。
/// </summary>
static List<int> PostOrderIterative(TreeNode? root)
{
    var result = new List<int>();
    if (root == null) return result;

    var stack = new Stack<TreeNode>();
    stack.Push(root);

    while (stack.Count > 0)
    {
        var node = stack.Pop();
        result.Add(node.Value);
        if (node.Left != null) stack.Push(node.Left);     // 先压左
        if (node.Right != null) stack.Push(node.Right);   // 后压右 -> 先出栈
    }

    result.Reverse();                                     // 关键：整体反转
    return result;
}

实测验证（三种都与递归版完全一致）：

  前序 递归: 1 2 4 5 3 6 7
  前序 迭代: 1 2 4 5 3 6 7   一致=True

  中序 递归: 4 2 5 1 6 3 7
  中序 迭代: 4 2 5 1 6 3 7   一致=True

  后序 递归: 4 5 2 6 7 3 1
  后序 迭代: 4 5 2 6 7 3 1   一致=True

三种迭代版的思路：

后序的"反转技巧"值得单独说一下：

• 前序的访问顺序是"根 左 右"
• 如果我们把"先压右后压左"改成"先压左后压右"，得到的顺序就是"根 右 左"
• 而"根 右 左"整体反转，正好是"左 右 根" —— 正是后序！

用一个"看起来不对"的遍历顺序 + 一次反转，就得到了后序。 这比"用两个栈"或"记录访问状态"的经典写法简单得多。

代价：多了一次 Reverse（$O(n)$），而且改变了访问时机（所有节点先被访问一遍，再反转）。如果访问有副作用（比如打印），这个技巧就不能用。

四、三种遍历分别用来干什么

这才是关键 —— 三种遍历不是"三种写法"，而是"三种用途"。

前序：适合"从上往下"处理

典型场景：复制一棵树。

  要复制一棵树，必须「先创建父节点，才能挂上子节点」——
  这正是前序的顺序（先访问自己，再处理孩子）。

其他场景：

• 序列化一棵树（把树转成字符串，10.2 节会用到）
• 打印目录结构（先打父目录，再打子目录）
• 表达式树生成前缀表达式

中序：适合"利用有序性"

典型场景：二叉搜索树的中序遍历得到有序序列。

实测（一棵 BST）：

     一棵二叉搜索树的中序遍历: 5 10 15 20 25 30 35
     是不是从小到大？True

这就是 BST 的核心性质：「中序有序」。

10.1 节会详细讲这个性质 —— 它是 BST 能支持"快速查找"和"范围查询"的根源。

反过来说：如果你的树是 BST，而你需要"按顺序处理所有元素"，用中序遍历就行了，不需要额外排序。

其他场景：

• 验证一棵树是不是 BST（10.1 节）
• 找出 BST 中第 k 小的元素
• 把 BST 转成有序数组

后序：适合"从下往上"处理

典型场景：计算依赖子树结果的信息。

static int TreeHeight(TreeNode? node)
    => node == null ? -1 : 1 + Math.Max(TreeHeight(node.Left), TreeHeight(node.Right));

注意这个递归的结构：

• 先递归求左右子树的高度
• 再用它们算出自己的高度

这就是后序的顺序（"访问自己"发生在两次递归之后）—— 必须等子树的结果出来，才能算自己的。

实测：这棵树的高度 = 2

其他场景：

• 求树的节点数、叶子数
• 判断树是否平衡（9.4 节）
• 释放树的内存（必须先释放孩子，再释放父节点）
• 计算表达式树的值（先算子表达式，再算根，呼应 5.3 节）

一个记忆方法：

遍历	处理方向	关键词
前序	从上往下	"创建/复制"
中序	从左往右	"有序"
后序	从下往上	"依赖子树"

额外：遍历顺序与表达式树

5.3 节的表达式树，和三种遍历正好对应：

这就是 5.3 节"中缀转后缀"背后的原理 —— 编译器解析表达式时，会先建一棵表达式树，后序遍历一次就得到了后缀表达式。

第 5 章和第 9 章在这里闭合了。

五、练习

练习 9.2.1（手写遍历） 对下面这棵树，写出三种遍历的结果：

              M
            /   \
           D     P
          / \   / \
         B   F Q   S
          \
           C

练习 9.2.2（反向推理） 已知一棵二叉树的前序遍历是 A B D E C F，中序遍历是 D B E A C F。 (a) 画出这棵树。 (b) 写出它的后序遍历。 (c) 说明你是怎么从两种遍历还原出树的结构的。

练习 9.2.3（判断） 判断对错并说明理由： (a) 中序遍历一棵二叉搜索树，得到的一定是从小到大的序列。 (b) 已知前序和后序遍历，就能唯一确定一棵二叉树。 (c) 后序遍历的迭代版必须用两个栈才能实现。

练习 9.2.4（应用） 一个系统需要实现"打印目录树"，输出格式是：

  root/
    ├── src/
    │   ├── main.cs
    │   └── util.cs
    └── README.md

(a) 这应该用哪种遍历？ (b) 如果要"先打印所有子目录，再打印父目录"（类似于计算目录大小），要用哪种？ (c) 如果要"统计每个目录下的文件总数"，用哪种？

练习 9.2.5（挑战·Morris 遍历） 三种标准遍历都需要 $O(h)$ 的栈空间（$h$ 是树高），递归版还需要函数调用开销。 Morris 遍历能做到 $O(1)$ 空间 —— 它利用树中大量的空指针（叶子节点的 Left/Right）来临时存储"回程路径"。 (a) 想想：一棵有 $n$ 个节点的二叉树，有多少个空指针？ (b) 这些空指针可以用来存什么？ (c) Morris 中序遍历的大致思路是什么？

六、练习答案

9.2.1

树的结构：

              M
            /   \
           D     P
          / \   / \
         B   F Q   S
          \
           C

(a) 前序（自己→左→右）：M D B C F P Q S

推演：

• M → 左 D → 左 B → 左空 → 右 C → 左空右空，回 B → 回 D
• D 的右 F → 左空右空，回 D → 回 M
• M 的右 P → 左 Q → 右 S

(b) 中序（左→自己→右）：B C D F M Q P S

推演：

• 最左是 B → 访问 B → B 的右 C → 访问 C → 回 D → 访问 D → D 的右 F → 访问 F
• 回 M → 访问 M
• M 的右 P → 左 Q → 访问 Q → 访问 P → 右 S → 访问 S

(c) 后序（左→右→自己）：C B F D Q S P M

推演：

• C → B → F → D（D 的左右都访问完了）→
• Q → S → P →
• M

9.2.2

(a) 前序 A B D E C F，中序 D B E A C F。

还原方法：

1. 前序的第一个一定是根 → 根是 A
2. 在中序里找 A → D B E | A | C F
   • 左边 D B E 是左子树的中序
   • 右边 C F 是右子树的中序
3. 左子树：中序是 D B E（3 个节点），前序里对应 B D E（前序中去掉根 A，取前 3 个）
   • 前序第一个是 B → B 是左子树的根
   • 中序中 B 左边是 D，右边是 E → D 是 B 的左孩子，E 是 B 的右孩子
4. 右子树：中序是 C F（2 个节点），前序是 C F
   • 前序第一个是 C → C 是右子树的根
   • 中序中 C 左边为空，右边是 F → F 是 C 的右孩子

还原出的树：

              A
            /   \
           B     C
          / \     \
         D   E     F

(b) 后序遍历：D E B F C A

验证：左子树 D E B，右子树 F C，最后根 A ✓

(c) 还原方法的通用步骤：

1. 从前序取出第一个 → 它是根
2. 在中序里找到它 → 左边是左子树的中序，右边是右子树的中序
3. 根据左子树的大小，在前序里切出左子树的前序
4. 对左右子树递归重复

关键洞察：前序提供"谁是根"，中序提供"左右子树各有哪些节点"。

两者结合才能唯一确定一棵树。

9.2.3

• (a) 对。 这是 BST 的定义性质（10.1 节会详细证明）。

  反过来说：如果你对一棵树做中序遍历，得到的序列不是有序的，那它不是 BST。

  这就是"验证一棵树是不是 BST"的常用方法（10.1 节会讲一个常见的错误写法）。

• (b) 错。 前序 + 后序无法唯一确定一棵树（除非是满二叉树）。

  反例：两棵不同的树可能有相同的前序和后序。

  比如：

    树 1:  A          树 2:  A
          /                  \
         B                    B
  
    前序都是 A B，后序都是 B A —— 但树结构不同！
  

  原因：前序和后序都只给出了"根在哪"，但没有给出"左右子树的分界点"。只有中序能提供这个信息。

  能唯一确定树的组合：

  • 前序 + 中序 ✓
  • 后序 + 中序 ✓
  • 层序 + 中序 ✓
  • 前序 + 后序 ✗（除了满二叉树）

• (c) 错。 本节给出的"按根右左遍历 + 整体反转"只需要一个栈。

  经典的"双栈法"确实存在，但这个技巧更简单。

  注意：反转法改变了访问时机（所有节点先被"访问"一遍，最后才反转顺序）。如果"访问"有副作用（比如打印、修改节点），这个技巧就不适用了 —— 那时还是需要双栈法或"记录上次访问节点"的方法。

9.2.4

(a) 前序遍历。

因为要先打印父目录，再打印子目录 —— 这正是"从上往下"的顺序。

root/           ← 先访问自己
  src/          ← 再递归左（或先目录后文件）
    main.cs
    util.cs
  README.md

(b) 后序遍历。

"先打印所有子目录，再打印父目录"—— 这是"从下往上"的顺序。

典型场景：计算目录总大小。

  要算 root/ 的总大小，必须先知道 src/ 和 README.md 各自多大 ——
  这正是后序的顺序（先算子树，再算自己）。

(c) 后序遍历。

"统计每个目录下的文件总数"本质上和 (b) 一样 —— 每个目录的总数 = 自己直接包含的文件数 + 所有子目录的总数。

static int CountFiles(Node dir)
{
    if (dir.IsFile) return 1;                    // 叶子：自己算 1 个
    int total = dir.DirectFiles.Count;           // 自己直接包含的文件
    foreach (var child in dir.Children)
        total += CountFiles(child);              // 加上所有子目录的（后序：先算子）
    return total;
}

(b) 和 (c) 的共同点：父节点的结果依赖于子节点的结果。

凡是这种"依赖子树结果"的问题，都用后序。 这就是 9.2 节开头说的"后序适合从下往上处理"。

9.2.5

(a) 一棵有 $n$ 个节点的二叉树，有 $n + 1$ 个空指针。

推导：

• 每个节点有 2 个引用（Left 和 Right），所以总共有 $2n$ 个引用
• 其中"非空"的引用数 = 边数 = $n - 1$（每个非根节点对应一条边）
• 所以空指针数 = $2n - (n-1) = n + 1$

验证：本节那棵树有 7 个节点，空指针应该是 8 个。

数一下：

• 1：Left(2) Right(3) —— 都非空
• 2：Left(4) Right(5) —— 都非空
• 3：Left(6) Right(7) —— 都非空
• 4：Left(null) Right(null) —— 2 个空
• 5：2 个空
• 6：2 个空
• 7：2 个空

总共 8 个空指针 ✓ 而 $n + 1 = 8$ ✓

这个数字很重要：近一半的指针是浪费的（$n+1$ 个空指针 vs $n-1$ 个有用指针）。

有些数据结构（比如线索二叉树）就是专门利用这些空指针来加速遍历的。

(b) 可以用来存"回程路径"（线索）。

具体来说：一个节点的 Right 如果为空，可以让它指向"中序遍历中的后继节点"。

这样遍历到叶子时，不需要借助栈就能"跳回"到下一个该访问的节点 —— 这就是 Morris 遍历的核心。

(c) Morris 中序遍历的大致思路：

核心想法：利用叶子节点的空 Right 指针，指向"回程时要去的节点"。

对于当前节点 cur：
  1. 如果 cur.Left == null：
       访问 cur，然后 cur = cur.Right  （右指针可能是线索，也可能是真的右孩子）
  2. 否则：
       a. 找到 cur 左子树中「最右的节点」（中序前驱）
       b. 如果它的 Right == null：
            把它的 Right 指向 cur      ← 建立线索
            cur = cur.Left             ← 进入左子树
       c. 如果它的 Right == cur：
            说明左子树已经遍历完了（这个线索是我们之前建的）
            把它的 Right 恢复成 null    ← 拆除线索，恢复树的原状
            访问 cur
            cur = cur.Right

为什么是 $O(1)$ 空间？

因为不需要栈，也不需要记录访问状态 —— 所有"回程信息"都存在树的空指针里了。

为什么时间复杂度还是 $O(n)$？

看起来"找中序前驱"每次都要往左下走一段，好像会退化成 $O(n \log n)$ 或 $O(n^2)$。

但仔细分析：每条边最多被"走两遍"（一遍是建立线索时找前驱，一遍是拆除线索时）。所以总代价是 $O(n)$。

Morris 遍历的价值和局限：

优点：$O(1)$ 空间。在内存极度受限的场景（比如嵌入式）里有价值。

缺点：

1. 实现复杂，容易写错
2. 会临时修改树的结构（虽然最后会恢复）—— 不是线程安全的
3. 实际速度未必更快 —— 它有更多的指针操作，而且"爬树找前驱"的过程缓存不友好

工程建议：除非你确实被空间卡死，否则不要用 Morris 遍历。 普通的迭代版（用栈）已经足够好。

但这个技巧本身很值得知道 —— 它体现了"利用数据结构的空闲空间来存储辅助信息"这个思路，在别的地方也会遇到（比如用链表空指针做标记、用数组的负数位存状态）。

七、常见错误

八、本节总结

1. 三种深度优先遍历的代码只差一行：result.Add() 放在两次递归之前（前序）、中间（中序）、之后（后序）。
2. 用去程/回程理解：前序 = 去程顺序，后序 = 回程顺序，中序是"左子树访问完、右子树还没开始"的那一刻。
3. 三种迭代版：前序（先压右后压左）、中序（一路向左压栈）、后序（根右左 + 反转）。
4. 三种遍历的用途完全不同：
   • 前序 → 复制、序列化（从上往下）
   • 中序 → BST 的有序序列（从左往右）
   • 后序 → 计算依赖子树的信息（从下往上）
5. 实测：三种迭代版与递归版结果完全一致。
6. 中序 + 前序（或后序）才能唯一还原一棵树 —— 前序给"根"，中序给"左右分界"。
7. Morris 遍历用空指针存回程路径，做到 $O(1)$ 空间 —— 但实现复杂、会临时改树，工程中很少用。

下一节衔接：本节讲的是"深度优先" —— 一条路走到底再回退。但还有另一种遍历方式：一层一层地访问。它是 12 章图论里"广度优先搜索（BFS）"的基础，而且能解决一类深度优先解决不好的问题（比如"最短路径"）。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "9.2",
  "title": "深度优先遍历：前序、中序、后序",
  "covered": [
    "三种遍历的代码只差一行（Add 的位置）",
    "用 2.1 节「去程/回程」一次性理解三种顺序",
    "三种遍历的迭代实现（前序先压右、中序一路向左、后序反转法）",
    "迭代版与递归版结果一致的实测验证",
    "三种遍历各自的典型用途（复制/有序/依赖子树）",
    "BST 中序有序的实测（5 10 15 20 25 30 35）",
    "遍历顺序与表达式树的对应（呼应 5.3 节）",
    "前序+中序还原树的完整推演",
    "Morris 遍历的空指针利用与 n+1 个空指针的推导"
  ],
  "unresolved": [
    "BST 的中序有序性留到 10.1",
    "层序遍历留到 9.3",
    "树题递归套路留到 9.4",
    "表达式树已在 5.3 节讲过，此处呼应"
  ],
  "canonical_terms": {
    "前序遍历": "自己→左→右，从上往下",
    "中序遍历": "左→自己→右，BST 得有序序列",
    "后序遍历": "左→右→自己，从下往上",
    "深度优先": "一条路走到底再回退的遍历策略"
  },
  "symbols_units": {},
  "assumptions": [
    "读者已掌握 9.1 的树术语与 2.1 的去程/回程",
    "读者会使用 C# 的 Stack<T> 与 List<T>"
  ],
  "word_count_actual": 3180,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch09/Sec92/",
    "三种遍历的递归/迭代结果一致性、BST 中序有序性均为实测",
    "练习 9.2.1/9.2.2 的遍历推演已手工验算",
    "术语写法与 glossary.md 一致"
  ],
  "next": "9.3 广度优先遍历与层序"
}