# 树

> CIE A-Level 计算机科学 · 9618
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u10-trees/

树是用于高效组织数据的层次化非线性数据结构。本模块涵盖CIE A-Level考试要求的核心术语、遍历方法、二叉搜索树以及树的常见实际应用。

**先修:** [递归基础](https://www.owlsprep.com/zh/study/cie-9618-u09-recursion/); [链表基础](https://www.owlsprep.com/zh/study/cie-9618-u09-linked-lists/)

## 学习目标

- 定义树的核心术语与性质
- 执行三种常见的二叉树深度优先遍历
- 构建二叉搜索树并执行插入/搜索操作
- 识别树的常见实际应用

## 树的核心术语与性质

**树** — 由边连接节点组成的层次化非线性数据结构，包含一个根节点且无环。除根节点外，每个节点恰好有一个父节点。

*例:* 计算机文件系统的目录结构

以下是描述树结构和度量的关键术语：

- 根节点：没有父节点的最顶层节点
- 叶节点：没有子节点的节点
- 节点深度：从根节点到该节点的边数
- 树的高度：任意叶节点的最大深度
- 二叉树：每个节点最多有2个子节点（左子节点和右子节点）

**例题:** 给定一棵树，根节点为A，子节点为B、C、D。B有子节点E和F。E的深度是多少？树的高度是多少？

1. 步骤1：计算E的深度：从根出发的路径为A → B → E，共2条边。因此E的深度为2。
2. 步骤2：计算树的高度：任意叶节点的最大深度为2（E和F）。因此树的高度为2。

**概念自测**

测试你的理解：

1. 一棵只有根节点、没有子节点的树，高度是多少？

   - 0
   - 1
   - 未定义
   - 无法确定

   *解析:* 高度是任意叶节点的最大深度，根节点自身的深度为0，因此根据CIE的定义，树的高度为0。

## 二叉树深度优先遍历

遍历是按照指定顺序恰好访问树中每个节点一次的过程。对于二叉树，三种常见深度优先遍历方法的命名，是根据根节点相对于其子树的访问顺序确定的。

**深度优先遍历** — 在回溯前尽可能沿每条分支深入探索的遍历方式，几乎总是通过递归实现。

> **顺序记忆口诀**
>
> 顺序由根节点的位置决定：先序 = 根优先，中序 = 根在中间，后序 = 根在最后。这正好对应表达式树的前缀/中缀/后缀表示法！

**例题:** 写出以下二叉树先序、中序、后序遍历的节点序列：根节点为A，左子节点B，右子节点C。B的左子节点D，右子节点E。C没有子节点。

1. 先序（根 → 左 → 右）：先访问A，然后遍历B的子树，最后访问C。
2. B的子树先序为B → D → E。最终先序序列：A, B, D, E, C。
3. 中序（左 → 根 → 右）：先遍历B的子树，然后访问A，最后访问C。
4. B的子树中序为D → B → E。最终中序序列：D, B, E, A, C。
5. 后序（左 → 右 → 根）：先遍历B的子树，然后访问C，最后访问A。
6. B的子树后序为D → E → B。最终后序序列：D, E, B, C, A。

## 二叉搜索树：插入与搜索

二叉搜索树（BST）是一种满足特殊排序性质的二叉树，该性质支持高效的值搜索和插入操作。BST性质可表述为：对任意节点，其左子树中所有节点的值都小于该节点的值，其右子树中所有节点的值都大于该节点的值。

**例题:** 按照以下顺序插入值构建一棵BST：8, 3, 10, 1, 6

1. 步骤1：将8插入为根节点。
2. 步骤2：插入3：3 < 8，添加为8的左子节点。
3. 步骤3：插入10：10 > 8，添加为8的右子节点。
4. 步骤4：插入1：1 < 8 → 左移到3，1 < 3 → 添加为3的左子节点。
5. 步骤5：插入6：6 < 8 → 左移到3，6 > 3 → 添加为3的右子节点。

BST的搜索通过递归比较目标值和当前节点实现：目标值更小则左移，更大则右移。对于平衡BST，搜索/插入的平均时间复杂度为$O(\log n)$，但对于不平衡树，最坏情况为$O(n)$。

**概念自测**

检查你的知识：

1. 如果你将有序值[1, 2, 3, 4, 5]插入一棵BST，最终结构是什么样的？

   - 一条直线状的链表
   - 平衡树
   - 满二叉树
   - 完全二叉树

   *解析:* 每个新值都大于当前节点，因此总是被添加为右子节点，最终形成不平衡的线性结构。

## 树的常见应用

树在计算领域被广泛使用，因为其层次结构支持高效的组织和搜索。你需要为CIE考试掌握的关键应用如下：

- 表达式树：存储算术表达式，运算符作为内部节点，操作数作为叶节点
- 文件系统目录：表示层次化的文件夹结构
- 堆：实现优先队列和堆排序
- 哈夫曼编码树：用于无损数据压缩
- 抽象语法树：供编译器解析代码时使用

**例题:** 画出中缀表达式$(3 + 4) * 2$的表达式树，并写出它的先序遍历序列

1. 步骤1：顶层运算符是*，因此*是根节点。右子节点是2，左子节点是运算符+。
2. 步骤2：+的左子节点是3，右子节点是4。先序遍历先访问根节点，结果为* + 3 4 2，这就是该表达式的前缀表示法。

## 常见错误

- **错误做法:** 混淆节点深度和树的高度
  - 原因: 许多学生分不清哪个度量是从根计数，哪个是从最深叶节点计数
  - 正确做法: 节点深度统计从根到该节点的边数；树的高度统计从根到最深叶节点的边数。
- **错误做法:** 混淆后序遍历的顺序
  - 原因: 学生经常类比先序遍历，把根放在子树前面而不是后面
  - 正确做法: 后序 = 根在最后：总是先访问左子树，再访问右子树，最后访问当前节点。
- **错误做法:** 插入新BST节点时重新排列现有节点
  - 原因: 学生认为插入需要重新平衡，但基础BST插入总是将新节点作为叶节点添加
  - 正确做法: 从根开始，遵循BST规则左移/右移直到找到空位置，然后将新节点作为叶节点添加。
- **错误做法:** 声称BST搜索的时间复杂度总是$O(\log n)$
  - 原因: 学生忘记不平衡BST会丧失高效搜索的性质
  - 正确做法: 只有平衡BST能保证$O(\log n)$的搜索时间；不平衡BST的最坏搜索时间为$O(n)$。
- **错误做法:** 认为单个根节点的高度为1
  - 原因: 计算高度时有些人统计节点数而不是边数
  - 正确做法: CIE将高度定义为边数，因此单个节点的高度为0。

## 速查表

| 术语 | 核心要点 |
| --- | --- |
| 根节点 | 最顶层节点，无父节点 |
| 叶节点 | 没有子节点的节点 |
| 节点深度 | 从根到节点的边数 |
| 树的高度 | 任意叶节点的最大深度 |
| 先序 | 根 → 左 → 右 |
| 中序 | 左 → 根 → 右 |
| 后序 | 左 → 右 → 根 |
| BST性质 | 左子树所有值 < 节点值 < 右子树所有值 |
| 平衡BST搜索 | $O(\log n)$ 平均时间 |

## 下一步

树是基础的非线性数据结构，是CIE 9618大纲中许多高级算法和数据结构的基础。扎实掌握树的性质、遍历和二叉搜索树，对于回答试卷1中的理论题和算法设计题至关重要。树还引入了核心的层次化思维，这种思维可以直接应用到下一个主要非线性数据结构——图中，也为后续单元的表达式求值、搜索等主题提供支撑。

- [图](https://www.owlsprep.com/zh/study/cie-9618-u10-graphs/)
- [哈希表](https://www.owlsprep.com/zh/study/cie-9618-u10-hash-tables/)
- [编程](https://www.owlsprep.com/zh/study/cie-9618-u11-overview/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u10-trees/