Tree algorithms

欢迎来到高级算法：树结构算法！

大家好！本章我们将深入探讨计算机科学中最强大且基础的非线性数据结构之一：树（Tree）。你可能觉得树只是一些简单的图示，但在算法层面，它们对于高效组织数据至关重要。

在本节中，我们将重点理解特定类型树（尤其是二叉树）的结构，并掌握一项核心技能——树的遍历（Tree Traversal），即访问树中每一个节点的方法。这些算法是许多复杂数据处理系统（从数据库到编译器）的基石。

如果一开始觉得有些棘手也不用担心！我们将通过清晰的步骤和助记技巧，让算法跟踪变得直观简单。让我们开始吧！

1. 快速复习：到底什么是树？(3.10.2)

在对树执行算法之前，让我们先巩固一下数据结构部分中关于树的定义。

A. 树的定义

在计算机科学中，树是一种特殊的图（用于表示复杂关系的数据结构），具有两个主要特征：

• 它是连通的：你可以从任何一个节点到达其他任何节点。
• 它没有环路：如果不走回头路，你无法从一个节点出发并回到该节点。

B. 有根树与二叉树

虽然满足上述条件的结构都是树，但我们通常处理的是有根树（Rooted Trees），它引入了层次结构（父子关系）。

• 有根树： 其中一个节点被特别指定为根（Root）。
  • 根是唯一没有父节点的节点。
  • 所有其他节点都是根的后代。
  • 某个节点下方的节点是它的子节点（Children）。
• 二叉树（Binary Tree）： 一种有根树，其中每个节点最多有两个子节点。这些子节点通常被称为左子节点（Left child）和右子节点（Right child）。

---

核心要点： 树是层次化的、无环的结构。我们主要关注二叉树。

---

2. 二叉搜索树 (BST)

二叉树最常见且最有用的应用之一是二叉搜索树（Binary Search Tree，简称 BST）。这种特定结构使得搜索、插入和删除操作极其高效。

二叉搜索树 (BST) 的性质

在 BST 的每个节点中：

• 其左子树中的所有数据值都小于节点本身的值。
• 其右子树中的所有数据值都大于节点本身的值。

你知道吗？ 正因为这些严格的排序规则，BST 成为了下文提到的某种遍历算法的完美候选者。

3. 树的遍历算法 (3.11.2)

树的遍历是按照特定顺序精确访问树中每个节点一次的过程。与具有自然线性顺序的列表或数组不同，树可以以多种不同的顺序进行处理。

三种主要的递归遍历算法是根据中央节点 (Node/Root) 相对于其左子树 (Left) 和右子树 (Right) 的处理时间来定义的。

A. 前序遍历 (NLR: 节点, 左, 右)

在前序遍历中，首先访问节点（根），然后递归访问左子树，最后递归访问右子树。

分步跟踪（“根优先”规则）

1. 访问节点 (N)（处理数据）。
2. 递归遍历左子树 (L)。
3. 递归遍历右子树 (R)。

记忆助手： 前序（Pre-order）意味着根节点被优先（Prioritised）且抢先（Pre-emptively）访问。

前序遍历的应用 (3.11.2)

• 复制树： 如果你想创建一棵树的结构副本，先处理根节点可以确保结构被准确重建。
• 生成前缀表达式（波兰表示法）： 对表达式树进行前序遍历会生成运算符位于操作数之前的算术表达式（例如：\(+ \ A \ B\)）。

B. 中序遍历 (LNR: 左, 节点, 右)

在中序遍历中，首先访问左子树，然后访问节点（根），最后是右子树。

分步跟踪（“节点在中间”规则）

1. 递归遍历左子树 (L)。
2. 访问节点 (N)（处理数据）。
3. 递归遍历右子树 (R)。

记忆助手： 中序（In-order）把根节点放在左访问和右访问的中间 (IN-between)。

中序遍历的应用 (3.11.2)

这是最著名的应用，特别是在 BST 中：

• 按升序输出二叉搜索树 (BST) 的内容： 由于 BST 的定义规则是“左 < 节点 < 右”，因此按 LNR 顺序访问节点自然会以排序（升序）序列打印数据。

C. 后序遍历 (LRN: 左, 右, 节点)

在后序遍历中，在访问节点（根）本身之前，先递归访问左子树和右子树。

分步跟踪（“根最后”规则）

1. 递归遍历左子树 (L)。
2. 递归遍历右子树 (R)。
3. 访问节点 (N)（处理数据）。

记忆助手： 后序（Post-order）意味着根节点的处理被推迟 (POSTponed) 到最后。

后序遍历的应用 (3.11.2)

• 清空树（删除）： 为了安全地删除一棵树，必须先删除子节点，再删除父节点。后序遍历保证你先处理叶节点，最后回到根节点。
• 生成后缀表达式（逆波兰表示法）： 对表达式树进行后序遍历会生成运算符位于操作数之后的算术表达式（例如：\(A \ B \ +\)）。

---

4. 跟踪树的遍历

跟踪是你需要掌握的实用技能。请记住，这些是递归算法：你总是将规则（NLR、LNR 或 LRN）应用于当前节点及其所有子树。

让我们想象一棵简单的二叉树，节点包含字母：
根 A（B 和 C 的父节点）
B（D 和 E 的父节点）
C（叶节点）
D（叶节点）
E（叶节点）
结构：A 为根。左子节点为 B，右子节点为 C。B 的子节点为 D（左）和 E（右）。

A. 前序遍历跟踪 (NLR)

从 A (根) 开始。

1. N: 访问 A。(输出: A)
2. L: 前往左子节点 B。对 B 应用 NLR。
   1. N: 访问 B。(输出: A, B)
   2. L: 前往左子节点 D。对 D 应用 NLR。
      1. N: 访问 D。(输出: A, B, D)
      2. L/R: D 无子节点。返回。
   3. R: 前往右子节点 E。对 E 应用 NLR。
      1. N: 访问 E。(输出: A, B, D, E)
      2. L/R: E 无子节点。返回。
3. R: 从 A 前往右子节点 C。对 C 应用 NLR。
   1. N: 访问 C。(输出: A, B, D, E, C)
   2. L/R: C 无子节点。返回。

最终前序序列： A, B, D, E, C

B. 中序遍历跟踪 (LNR)

从 A (根) 开始。

1. L: 前往左子节点 B。对 B 应用 LNR。
   1. L: 前往左子节点 D。对 D 应用 LNR。
      1. L: D 无左子节点。
      2. N: 访问 D。(输出: D)
      3. R: D 无右子节点。返回 B。
   2. N: 访问 B。(输出: D, B)
   3. R: 前往右子节点 E。对 E 应用 LNR。
      1. L: E 无左子节点。
      2. N: 访问 E。(输出: D, B, E)
      3. R: E 无右子节点。返回 A。
2. N: 访问 A。(输出: D, B, E, A)
3. R: 前往右子节点 C。对 C 应用 LNR。
   1. L: C 无左子节点。
   2. N: 访问 C。(输出: D, B, E, A, C)
   3. R: C 无右子节点。返回。

最终中序序列： D, B, E, A, C

注意：如果这些是 BST 中的数字，这个序列就是有序的！

C. 后序遍历跟踪 (LRN)

从 A (根) 开始。

1. L: 前往左子节点 B。对 B 应用 LRN。
   1. L: 前往左子节点 D。对 D 应用 LRN。
      1. L/R: D 无子节点。
      2. N: 访问 D。(输出: D)
      3. 返回 B。
   2. R: 前往右子节点 E。对 E 应用 LRN。
      1. L/R: E 无子节点。
      2. N: 访问 E。(输出: D, E)
      3. 返回 B。
   3. N: 访问 B。(输出: D, E, B)
   4. 返回 A。
2. R: 前往右子节点 C。对 C 应用 LRN。
   1. L/R: C 无子节点。
   2. N: 访问 C。(输出: D, E, B, C)
   3. 返回 A。
3. N: 访问 A。(输出: D, E, B, C, A)

最终后序序列： D, E, B, C, A

---

核心要点： 递归遍历的跟踪过程是将“三步规则 (L, N, R)”应用于当前节点，如果某一步是另一棵子树，则立即进入该子树进行完整遍历。

---

5. 实现树的遍历（概念）

虽然在考试中可能不会让你手写这些复杂算法的完整代码，但理解其概念实现（通常是递归实现）是至关重要的。

递归结构

所有三种遍历通常都遵循相似的递归蓝图，即子程序对左子节点和右子节点进行递归调用。

前序遍历的伪代码示例结构：

        
    SUBROUTINE PreOrder(Node)
        IF Node IS NOT NULL THEN
            // 1. 访问节点 (N)
            OUTPUT Node.Data
            // 2. 遍历左子树 (L)
            PreOrder(Node.LeftChild)
            // 3. 遍历右子树 (R)
            PreOrder(Node.RightChild)
        END IF
    END SUBROUTINE
        
    

若要改为中序遍历，只需将 OUTPUT Node.Data 行移动到对左右子程序调用的中间即可。

若要改为后序遍历，则将 OUTPUT Node.Data 行移动到两个递归调用之后。

---

核心要点： 实现依赖于递归，其中“访问节点”这一步所处的位置决定了遍历的类型。

---