Trees

欢迎进入高级数据结构：树！

各位未来的计算机科学家们，大家好！你们已经掌握了数组、队列和栈等基本数据结构。现在，我们即将进入层次化数据结构的世界。这一章关于树 (Trees) 的内容至关重要，因为树是存储和组织信息以实现超高效搜索和排序的最强大工具之一。

如果起初觉得有些棘手，也不必担心。不要仅仅把树看作一个数学概念，可以把它想象成你在日常生活中经常使用的结构，比如电脑里的文件系统，或者家谱。我们将拆解其中的专业术语，重点关注 9645 大纲要求的核心概念。让我们开始吧！

快速回顾：什么是树？（基本定义）

在深入细节之前，首先要知道树是一种源自图 (Graphs)（你在 3.10.1 节中学习过）的特殊结构。

树 (Tree) 在形式上被定义为一种连通、无环的无向图。

• 连通 (Connected)： 你可以从任意节点到达其他任何节点。
• 无向 (Undirected)： 连接（边）没有方向；移动可以是双向的。
• 无环 (No Cycles)： 没有回路或闭合路径。如果你从一个节点出发并沿着边走，在不原路返回的情况下，你不可能回到起始节点。

你知道吗？ 虽然一般的“树”没有指定的起点，但在计算机科学中（尤其是考试中）使用的大多数树都是有根树 (Rooted Trees)。

4.1 有根树与核心术语（大纲 3.10.2）

4.1.1 有根树的定义

有根树是指其中一个特定的顶点（节点）被指定为根节点 (root) 的树。这种简单的指定建立了一个清晰的层次结构，并引入了重要的关系。

有根树的关键特征：

1. 根节点是唯一没有父节点的节点。
2. 所有其他节点都是根节点的后代 (descendants)。
3. 该结构在节点之间建立了父子关系 (parent-child relationships)。

类比： 想象组织架构图中顶层的 CEO 或创始人。他们就是根节点，而其他人都是他们的下属。

4.1.2 重要的树术语

你必须熟悉以下术语：

• 节点 (Node 或 Vertex)： 树中存储数据的元素。
• 边 (Edge 或 Arc)： 两个节点之间的连接。
• 根节点 (Root)： 树的起始节点（没有父节点）。
• 父节点 (Parent)： 拥有通往其下方直接相连节点的节点的节点。
• 子节点 (Child)： 位于另一个节点（其父节点）正下方的节点。
• 叶节点 (Leaf Node 或 Terminal Node)： 没有子节点的节点。它们位于分支的“末端”。
• 子树 (Subtree)： 树的一部分，其本身也是一棵树，根节点是原树中的某个节点。
• 祖先/后代 (Ancestor/Descendant)： 从根节点到节点 X 路径上的所有节点都是它的祖先。节点 X 下方的所有节点都是它的后代。

4.2 二叉树与二叉搜索树 (BST)

4.2.1 二叉树（大纲 3.10.2）

二叉树 (Binary Tree) 是一种特殊的有根树，其连接数量遵循严格的规则：

定义： 一种每个节点最多有两个子节点的有根树。

这两个子节点通常被区分为左子节点 (left child) 和右子节点 (right child)。如果一个节点只有一个子节点，它也必须明确指定是左子节点还是右子节点。

4.2.2 二叉搜索树 (BST)（大纲 3.10.2）

如果说普通二叉树仅规定了结构（最多两个子节点），那么二叉搜索树 (BST) 则规定了顺序。正是这种排序规则使得它们在快速数据检索方面非常有用。

定义： 一种二叉树，对于任何给定的节点，其左子树中的所有值都小于该节点的值，而其右子树中的所有值都大于该节点的值。

BST 规则：

• 左子节点 < 父节点
• 右子节点 > 父节点

需要避免的常见错误： 该规则适用于整个*子树*，而不仅仅是直接子节点。例如，左子树中的玄孙节点也必须小于根节点。

为什么要使用 BST？
BST 可以显著加快搜索速度。如果你要查找数字 50，而根节点是 75，你立刻就知道只需要检查左子树。这可以在一步之内排除掉大约一半的数据，类似于对已排序数组进行二分查找，使得搜索时间非常高效（对数复杂度，\(O(\log n)\)）。

4.3 树的遍历算法（大纲 3.11.2）

树的遍历 (Tree Traversal) 是指按照某种系统顺序，正好访问（处理或检查）树中每个节点一次的过程。与只有一种明显顺序的线性结构（如列表或队列）不同，树有多种遍历方式。我们重点关注三种主要类型，它们取决于根节点/父节点在输出序列中的相对位置。

4.3.1 三种遍历方法

这三种方法通常都是通过递归（子程序调用自身）来实现的，因为定义可以自然地应用于节点及其子树。

要记住这三种类型，请关注父节点 (P) 相对于其左 (L) 和右 (R) 子节点的访问顺序：

1. 前序遍历 (Pre-order Traversal) (P L R)
当前节点（根/父节点）在子节点之前被访问。

步骤：
1. 访问根节点（处理数据）。
2. 递归遍历左子树。
3. 递归遍历右子树。

2. 中序遍历 (In-order Traversal) (L P R)
当前节点（父节点）在左、右子节点之间被访问。

步骤：
1. 递归遍历左子树。
2. 访问根节点（处理数据）。
3. 递归遍历右子树。

3. 后序遍历 (Post-order Traversal) (L R P)
当前节点（父节点）在两个子节点之后被访问。

步骤：
1. 递归遍历左子树。
2. 递归遍历右子树。
3. 访问根节点（处理数据）。

4.3.2 遍历追踪（分步示例）

想象一个小的 BST：
       50 (根节点)
      /    \
     25    75

追踪前序遍历 (P L R)：
1. 从 50 (P) 开始。打印 50。
2. 向左 (L) 到 25。打印 25。
3. 从 25 向左（无）。从 25 向右（无）。
4. 回到 50。向右 (R) 到 75。打印 75。
结果： 50, 25, 75

追踪中序遍历 (L P R)：
1. 从 50 (P) 开始。向左 (L) 到 25。
2. 从 25 出发，向左 (L)（无）。
3. 打印 25 (P)。
4. 从 25 向右 (R)（无）。
5. 回到 50。打印 50 (P)。
6. 向右 (R) 到 75。从 75 向左（无）。
7. 打印 75 (P)。
结果： 25, 50, 75

重要关联： 使用中序遍历 (L P R) 对 BST 进行追踪，输出的元素总是升序排列的。这是中序遍历的主要用途。

追踪后序遍历 (L R P)：
1. 从 50 (P) 开始。向左 (L) 到 25。
2. 从 25 出发，向左 (L)（无）。向右 (R)（无）。
3. 打印 25 (P)。
4. 回到 50。向右 (R) 到 75。
5. 从 75 出发，向左 (L)（无）。向右 (R)（无）。
6. 打印 75 (P)。
7. 回到 50。打印 50 (P)。
结果： 25, 75, 50

4.4 树遍历的应用（大纲 3.11.2）

根据你需要执行的任务，不同的遍历方法各有用途。

4.4.1 中序遍历的应用

主要用途是针对二叉搜索树：

1. 将 BST 的内容按升序输出。

4.4.2 前序遍历的应用

由于父节点首先被访问，这种方法在处理细节之前建立结构非常有用。

1. 复制一棵树： 如果按前序遍历，你先创建根节点，然后是左分支，接着是右分支——这正是重建副本所需的顺序。
2. 生成前缀表达式： 这适用于表达式树，其中运算符置于操作数之前（例如 \((+ A B)\)）。

4.4.3 后序遍历的应用

由于父节点最后被访问，这通常用于需要在操作父节点（或销毁结构）之前处理所有子节点的情况。

1. 清空或删除一棵树： 你必须先删除所有子节点（叶节点），才能删除父节点（否则你会丢失对子节点的访问权限）。后序遍历确保了删除工作从最底层开始。
2. 生成后缀表达式： 这适用于表达式树，其中运算符置于操作数之后（例如 \((A B +)\)）。这也被称为逆波兰表示法 (RPN)。