树

CIE A-Level 计算机科学· 第10单元：数据类型与结构· 40 分钟阅读

1. 树的核心术语与性质★★☆☆☆⏱ 10 min

📘 定义

树

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

例:

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

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

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

📐 例题

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

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

✓ 快速检测

测试你的理解：

一棵只有根节点、没有子节点的树，高度是多少？
- 0
- 1
- 未定义
- 无法确定
显示答案
0 —
高度是任意叶节点的最大深度，根节点自身的深度为0，因此根据CIE的定义，树的高度为0。

2. 二叉树深度优先遍历★★★☆☆⏱ 15 min

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

📘 定义

深度优先遍历

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

📐 例题

写出以下二叉树先序、中序、后序遍历的节点序列：根节点为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。

3. 二叉搜索树：插入与搜索★★★☆☆⏱ 15 min

二叉搜索树（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 (lo g n)$ ，但对于不平衡树，最坏情况为 $O (n)$ 。

✓ 快速检测

检查你的知识：

如果你将有序值[1, 2, 3, 4, 5]插入一棵BST，最终结构是什么样的？
- 一条直线状的链表
- 平衡树
- 满二叉树
- 完全二叉树
显示答案
一条直线状的链表 —
每个新值都大于当前节点，因此总是被添加为右子节点，最终形成不平衡的线性结构。

4. 树的常见应用★★☆☆☆⏱ 10 min

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

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

📐 例题

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

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

5. 常见陷阱

错误做法:

混淆节点深度和树的高度

原因:

许多学生分不清哪个度量是从根计数，哪个是从最深叶节点计数

正确做法:

节点深度统计从根到该节点的边数；树的高度统计从根到最深叶节点的边数。

错误做法:

混淆后序遍历的顺序

原因:

学生经常类比先序遍历，把根放在子树前面而不是后面

正确做法:

后序 = 根在最后：总是先访问左子树，再访问右子树，最后访问当前节点。

错误做法:

插入新BST节点时重新排列现有节点

原因:

学生认为插入需要重新平衡，但基础BST插入总是将新节点作为叶节点添加

正确做法:

从根开始，遵循BST规则左移/右移直到找到空位置，然后将新节点作为叶节点添加。

错误做法:

声称BST搜索的时间复杂度总是 $O (lo g n)$

原因:

学生忘记不平衡BST会丧失高效搜索的性质

正确做法:

只有平衡BST能保证 $O (lo g n)$ 的搜索时间；不平衡BST的最坏搜索时间为 $O (n)$ 。

错误做法:

认为单个根节点的高度为1

原因:

计算高度时有些人统计节点数而不是边数

正确做法:

CIE将高度定义为边数，因此单个节点的高度为0。

6. 速查表

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

真题中的出现

AI 根据考纲规律估算的考点位置,请对照官方真题核实准确性。仅作复习重点参考。

2022 · 1
树遍历与二叉搜索树构建
2023 · 1
术语与遍历问题
2024 · 1
二叉搜索树插入与应用

下一步

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