第 9 章　二叉树与遍历

本章解决的问题：数组和哈希表都无法同时做到"有序"和"快速增删"，树是怎么做到的？

9.1　树的术语与二叉树的形态

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

准确使用根、叶子、深度、高度这些术语，不再把"深度"和"高度"搞混；
说清满二叉树、完全二叉树、完美二叉树的区别；
解释为什么平衡二叉树的高度是 $O(\log n)$ —— 这是后面所有树结构性能的来源。

先修：2.1（递归）、8.3（堆的数组表示）。 固定术语：树、根、叶子、深度、高度、完全二叉树。 环境与版本：.NET 8 / C# 12。 预计阅读：26 分钟。

一、直觉：一张家族树

树是最自然的层级结构。 想想你的家谱：

                    祖父
                  /      \
              父亲        叔叔
             /    \          \
          你      妹妹       堂弟

这套"祖先-后代"的词汇，直接就是树的术语：

家族	树
最上面的祖父	根（root）
没有孩子的人	叶子（leaf）
父亲是"你的上级"	父亲是你的父节点，你是他的子节点
你和妹妹	兄弟节点
从祖父到你	路径

而"二叉树"就是"每个人最多有两个孩子"的家谱。

二、术语表

先把这个表看一遍，后面每节都会用到：

术语	定义	图示（下面那棵树）
根（Root）	最上面的节点，没有父节点	节点 1
叶子（Leaf）	没有子节点的节点	8、9、5、6、7
父节点（Parent）	直接上层	4 的父节点是 2
子节点（Child）	直接下层	2 的子节点是 4、5
兄弟（Sibling）	同一个父节点的节点	4 和 5
子树（Subtree）	以某节点为根的整棵小树	以 2 为根的子树
深度（Depth）	从根往下数到该节点的边数	节点 4 的深度 = 2
高度（Height）	从该节点往下数到最远叶子的边数	节点 2 的高度 = 2
层（Level）	深度相同的节点算一层	第 0 层只有节点 1

用代码构造这棵树：

//                 1
//               /   \
//              2     3
//             / \   / \
//            4   5 6   7
//           / \
//          8   9

var root = new TreeNode(1)
{
    Left = new TreeNode(2)
    {
        Left = new TreeNode(4) { Left = new TreeNode(8), Right = new TreeNode(9) },
        Right = new TreeNode(5),
    },
    Right = new TreeNode(3)
    {
        Left = new TreeNode(6),
        Right = new TreeNode(7),
    },
};

节点定义：

public class TreeNode
{
    public int Value;
    public TreeNode? Left;
    public TreeNode? Right;      // 链表节点有一个 Next，树节点有两个孩子

    public TreeNode(int value) => Value = value;
}

注意它和第 4 章链表节点的关系：链表节点是"一个数据 + 一个引用"，树节点是"一个数据 + 两个引用"。

树就是"每个节点可以分叉的链表"。

三、最容易搞混的：深度 vs 高度

这是本节最重要的一组定义。

	方向	从哪开始数	端点
深度（Depth）	从上往下	从根（深度 0）	到该节点
高度（Height）	从下往上	从最远叶子（高度 0）	到该节点

实测数据：

  各个节点的深度（到根的距离）：
    节点 1: 深度 = 0
    节点 2: 深度 = 1
    节点 3: 深度 = 1
    节点 4: 深度 = 2
    节点 6: 深度 = 2
    节点 8: 深度 = 3
    节点 9: 深度 = 3

  树的高度: 3

关键关系：

整棵树的高度 = 根节点的高度。

换句话说：树的高度，等于"最深的那个节点的深度"。

验证：节点 8 和 9 的深度是 3（最深），所以树高是 3 ✓

记忆方法：

深度是"你站在根上往下看" —— 根最深为 0
高度是"你站在叶子上往上看" —— 叶子最高为 0
整棵树的高度 = 最深的深度

约定说明：也有教材把单节点树的高度定义为 1、空树高度定义为 0。本书统一采用"边数"定义：空树高度 = -1，叶子高度 = 0。

看别人代码时注意这个差异 —— 它经常导致 off-by-one 的错误。

四、二叉树的三种形态

这三个概念经常被搞混，但它们的定义是清晰的：

形态	定义	关键
完美二叉树（Perfect）	每一层都填满	节点数 = $2^{h+1} - 1$
完全二叉树（Complete）	除最后一层外全满，最后一层的节点靠左连续排列	可以用数组紧凑存储
满二叉树（Full）	每个节点要么有 2 个孩子，要么 0 个	没有"只有一个孩子"的节点

实测对比：

  完美二叉树（高度 3，15 个节点）:
    第 0 层: 3
    第 1 层: 2  2
    第 2 层: 1  1  1  1
    第 3 层: 0  0  0  0  0  0  0  0

  完全二叉树（最后一层的节点都靠左）:
    第 0 层: 1
    第 1 层: 2  3
    第 2 层: 4  5  6
    -> 中间没有空洞，所以能用数组紧凑表示（堆就是这样，见 8.3 节）

  满二叉树（每个节点要么有 2 个孩子，要么 0 个）:
    第 0 层: 1
    第 1 层: 2  3
    第 2 层: 4  5
    -> 注意它【不是】完全二叉树：右子树只有 3，没有孩子，
       但最后一层的 3 左边是空的 —— 不完全。

它们的关系（这里有个常见的误区）：

  完美二叉树 ⊆ 完全二叉树    ✓
  完美二叉树 ⊆ 满二叉树      ✓
  完全二叉树 和 满二叉树【互不包含】！

为什么互不包含？

满但不完全：上面那棵满二叉树（最后一层有空缺）
完全但不满：一棵树上只有左孩子 —— 它满足"完全"（节点靠左连续），但不满足"满"（有节点只有一个孩子）

最有用的是"完全二叉树" —— 因为只有它可以用数组紧凑存储（8.3 节的堆就是例子）。

完全二叉树的性质：节点按层编号后，第 $i$ 个节点的孩子是 $2i+1$ 和 $2i+2$ —— 没有空洞，所以数组里不会有浪费。

五、高度与 $\log n$ 的关系

这是整棵树结构性能的来源。

完美二叉树的节点数：

高度 $h$	节点数 $2^{h+1}-1$
0	1
1	3
2	7
3	15
4	31
5	63

实测全部吻合 ✓

反过来解出高度：

$$n = 2^{h+1} - 1 \quad \Longrightarrow \quad h = \log_2(n+1) - 1$$

所以高度是 $O(\log n)$。

看这个对比：

  n = 1,000,000 时：
    完美二叉树的高度: 19
    退化链的高度:     999,999

差了 5 万倍。

这就是为什么"树是否平衡"是所有树结构的生死线：

平衡的树：高度 $O(\log n)$，所以查找、插入、删除都是 $O(\log n)$

退化的树：高度 $O(n)$，所有操作退化到 $O(n)$ —— 和链表没有区别

10.3 节会详细讲"退化"是怎么发生的，以及怎么防止它。

有意思的是：这个"每层翻倍，所以高度是对数"的关系，你在二分查找（每次砍一半）、快速幂（指数减半）里已经见过。

$O(\log n)$ 的本质是"每操作一次，问题规模就按固定比例缩小" —— 无论是"减半"（二分）还是"分叉"（树），数学是一样的。

六、练习

练习 9.1.1（术语）对下面这棵树，回答各问题：

               A
             /   \
            B     C
           / \     \
          D   E     F
             / \
            G   H

(a) 根、叶子分别是谁？ (b) 节点 G 的深度和高度各是多少？ (c) 整棵树的高度是多少？ (d) 以 E 为根的子树有多少个节点？

练习 9.1.2（计算） (a) 一棵完美二叉树有 1023 个节点，它的高度是多少？ (b) 高度为 10 的完美二叉树有多少节点？ (c) 一棵高度为 $h$ 的二叉树，最多有多少节点？最少有多少节点（$h \geq 0$）？

练习 9.1.3（判断）判断对错并说明理由： (a) "深度"和"高度"是同一回事，只是叫法不同。 (b) 满二叉树一定是完全二叉树。 (c) 完全二叉树一定是满二叉树。 (d) 一棵二叉树有 100 个节点，高度一定不超过 99。

练习 9.1.4（设计）一个系统要用二叉树存储 100 万个元素，要求所有操作在 20 次比较内完成。 (a) 这棵树的高度必须控制在多少以内？ (b) 如果树退化成链表，需要多少次比较？ (c) 你会选择什么措施来保证高度？

练习 9.1.5（挑战·证明）证明：任何二叉树，如果叶子节点（度为 0）有 $n_0$ 个、度为 2 的节点有 $n_2$ 个，那么 $n_0 = n_2 + 1$。 （提示：从"节点总数 = 边数 + 1"这个关系出发。）

七、练习答案

9.1.1

(a)

根：A（没有父节点）
叶子：D、G、H、C、F（没有子节点）

注意 C 也是叶子 —— 它有一个右孩子 F，但"叶子"的定义是"没有子节点"，而 C 有孩子 F……

等一下，重看树的结构：
           C
            \
             F
C 有右孩子 F，所以 C 不是叶子。

正确的叶子是：D、G、H、F（4 个）。

这个容易看错 —— C 虽然没有左孩子，但有右孩子，所以不是叶子。

(b) 节点 G：

深度：从根 A 往下数到 G：A→B→E→G，共 3 条边，所以深度 = 3
高度：从 G 往下数到最远叶子 —— G、H 本身就是叶子，没有更深的了，所以高度 = 0

(c) 整棵树的高度 = 最深的深度。

最深的叶子是 D（深度 2）、G（深度 3）、H（深度 3）、F（深度 2）。

所以树高 = 3。

(d) 以 E 为根的子树包含 E、G、H —— 3 个节点。

9.1.2

(a) 完美二叉树节点数 $= 2^{h+1} - 1 = 1023$。

$$2^{h+1} = 1024 = 2^{10} \quad \Longrightarrow \quad h + 1 = 10 \quad \Longrightarrow \quad h = 9$$

高度是 9。

(b) $2^{10+1} - 1 = 2048 - 1 = 2047$。

2047 个节点。

(c)

最多：完美二叉树，$2^{h+1} - 1$ 个
最少：一条链（每个节点只有右孩子），$h + 1$ 个

验证：高度 0 时，最少 1 个节点（只有根），$0+1 = 1$ ✓

这个"最多最少差 5 万倍"（$n = 10^6$ 时）正是"树是否平衡"决定性能的原因 —— 同样 100 万个节点，可能是高度 19 的完美树，也可能是高度 99 万的链。

9.1.3

(a) 错。 它们是方向相反的两个概念：
- 深度：从根往下数（根为 0）
- 高度：从最远叶子往上数（叶子为 0） >
  它们只有一个共同点：整棵树的高度 = 根节点的深度所对应的那个"最深值"。但这是结论，不是定义。
  
  一个反例：一棵"只有左孩子的链"（A→B→C，A 是根）。
  - 节点 A 的深度是 0，高度是 2
  - 节点 C 的深度是 2，高度是 0
  完全不同的两个数。
(b) 错。 本节的实测例子就是反例：[1, 2, 3, 4, 5] 那棵树满足"满"（每个节点有 0 或 2 个孩子），但不是完全二叉树（最后一层的 3 左边有空缺）。
(c) 错。 一棵只有左孩子的树（比如 1 → 左 2 → 左 3）是完全二叉树（节点靠左连续排列），但不是满二叉树（节点 2 只有一个孩子）。
(d) 对。 100 个节点最多排成一条链，高度为 99。

(b) 和 (c) 都错，恰恰说明"满"和"完全"是两个独立的概念。

9.1.4

(a) "20 次比较内完成"意味着高度不超过 20。

完美二叉树的关系：$h = \log_2(n+1) - 1$。

$$h = \log_2(1{,}000{,}001) - 1 \approx 19.93 - 1 = 18.93$$

所以高度控制在 19 以内就够了 —— 完美二叉树恰好能做到。

实际上，只要树是"平衡"的（左右子树高度差不超过某个常数），高度就是 $O(\log n)$。

(b) 退化成链表时，高度 = $n - 1 = 999{,}999$，最坏需要约 100 万次比较。

从 19 次变成 100 万次 —— 差了 5 万倍。

(c) 几个方向：

用自平衡的树（推荐）：AVL 树或红黑树会在插入删除时自动调整结构，保证高度始终是 $O(\log n)$。10.4 节会讲。
用 B 树 / B+ 树（数据在磁盘上时）：每个节点存多个键，高度更低。这是数据库索引的做法。
随机化：比如 Treap（树堆），用随机优先级来保证期望平衡。
保证插入顺序是随机的：但这在现实中几乎做不到 —— 数据往往是有序的（比如自增 ID），而有序插入恰好是让 BST 退化的最常见原因（10.3 节）。

工程结论：不要自己实现普通 BST 用于生产。需要有序的快速查找时，用 SortedDictionary / SortedSet（内部是红黑树），或者数据库的索引。

9.1.5

证明：在任何二叉树中，$n_0 = n_2 + 1$。

第一步：建立"节点数"和"边数"的关系。

设树的节点总数为 $n$。除了根节点，每个节点都恰好有一条边连向它的父节点。

所以：

$$\text{边数} = n - 1$$

第二步：用度数来数边数。

从"父节点"的角度看：每条边都对应一个"孩子"。

度为 2 的节点贡献 2 条边（2 个孩子）
度为 1 的节点贡献 1 条边（1 个孩子）
度为 0 的节点贡献 0 条边

所以：

$$\text{边数} = 2n_2 + 1 \cdot n_1 + 0 \cdot n_0 = 2n_2 + n_1$$

第三步：把两个式子连起来。

由第一步和第二步：

$$n - 1 = 2n_2 + n_1$$

而节点总数也可以按度数分类：

$$n = n_0 + n_1 + n_2$$

代入：

$$(n_0 + n_1 + n_2) - 1 = 2n_2 + n_1$$

两边消去 $n_1$：

$$n_0 + n_2 - 1 = 2n_2$$

移项：

$$n_0 = n_2 + 1$$

证毕。 ∎

验证：本节那棵树

叶子（度为 0）：8、9、5、6、7 —— $n_0 = 5$
度为 2 的节点：1、2、3、4 —— $n_2 = 4$
$5 = 4 + 1$ ✓

这个结论的用处：

它让你能快速推算树的结构。 比如你知道一棵满二叉树有 10 个内部节点（度为 2），那么叶子一定是 11 个，总节点数就是 21。

更重要的是，它展示了"用两种方式数同一个东西"这个证明技巧 —— 先数节点、再数边，让两个表达式相等。这个手法在图论（第 12 章）里会反复出现。

八、常见错误

误区	纠正
混淆"深度"和"高度"	深度从根往下数（根为 0），高度从最远叶子往上数（叶子为 0）。方向相反。
认为"满二叉树"就是"完全二叉树"	两者互不包含。满看的是"孩子个数"，完全看的是"排列是否靠左"。
认为"有右孩子但没有左孩子"的节点是叶子	叶子 = 没有孩子（左右都没有）。C 有右孩子 F，所以不是叶子。
忽略高度定义的差异	有教材定义空树高度为 0、单节点为 1。本书用"边数"：空树 -1、叶子 0。看别人代码要确认。
认为树"天然"就是 $O(\log n)$	只有平衡的树才是。退化链的高度是 $n-1$，和链表一样慢。

九、本节总结

树的术语：根、叶子、父节点、子节点、兄弟、子树、深度、高度。
深度 vs 高度：深度从根往下数，高度从最远叶子往上数。整棵树的高度 = 最深的深度。
三种形态：完美（每层填满）、完全（最后一层靠左）、满（每个节点 0 或 2 个孩子）。完全和满互不包含。
完全二叉树最有价值 —— 因为它可以用数组紧凑存储（8.3 节的堆）。
完美二叉树：节点数 $= 2^{h+1}-1$，高度 $= \log_2(n+1)-1$。
高度 $O(\log n)$ 是所有树结构性能的来源：$n = 10^6$ 时，平衡树高度 19，退化链高度 999,999 —— 差 5 万倍。
$n_0 = n_2 + 1$（叶子数 = 度为 2 的节点数 + 1），用"数节点 vs 数边"两种方式证明。

下一节衔接：树的结构讲完了，但怎么"走遍"一棵树？这需要遍历。二叉树的遍历有三种深度优先的顺序，它们代码上只差一行 —— 但用途完全不同。下一节会用 2.1 节讲过的"去程/回程"把这件事一次性讲清楚。

状态外显

{
  "book": "数据结构与算法自学：从工程直觉到复杂度思维",
  "section": "9.1",
  "title": "树的术语与二叉树的形态",
  "covered": [
    "树的家谱类比与完整术语表",
    "TreeNode 定义与树/链表节点的关系",
    "深度 vs 高度的定义差异与实测验证",
    "完美/完全/满二叉树的定义与互不包含的关系",
    "完全二叉树可用数组紧凑存储的原因（呼应 8.3 堆）",
    "完美二叉树节点数 2^(h+1)-1 的实测验证",
    "高度 O(log n) 与退化链的对比（19 vs 999999）",
    "n0 = n2 + 1 的证明（数节点 vs 数边）"
  ],
  "unresolved": [
    "三种遍历留到 9.2",
    "层序遍历留到 9.3",
    "BST 的有序性留到 10.1",
    "树的退化与平衡留到 10.3/10.4"
  ],
  "canonical_terms": {
    "树": "由节点和边组成的层级结构",
    "根": "最上面的节点，没有父节点",
    "叶子": "没有子节点的节点",
    "深度": "从根往下数到该节点的边数，根为 0",
    "高度": "从该节点往下数到最远叶子的边数，叶子为 0",
    "完全二叉树": "除最后一层外全满，最后一层节点靠左连续排列"
  },
  "symbols_units": {
    "h": "树的高度",
    "n0": "叶子节点数",
    "n2": "度为 2 的节点数"
  },
  "assumptions": [
    "读者已掌握 2.1 的递归与 8.3 的堆数组表示",
    "读者理解 C# 的类与对象初始化器语法"
  ],
  "word_count_actual": 2860,
  "checks": [
    "C# 代码已在 .NET 8 (SDK 10.0.303) Release 下实跑，输出见正文",
    "项目文件：99-tools/samples/Ch09/Sec91/",
    "完美二叉树节点数 2^(h+1)-1 逐项实测验证（h=0..5）",
    "深度/高度/退化链高度均为实测",
    "练习 9.1.5 的证明已逐步验算",
    "术语写法与 glossary.md 一致"
  ],
  "next": "9.2 深度优先遍历：前序、中序、后序"
}

9.1　树的术语与二叉树的形态

第 9 章　二叉树与遍历

9.1　树的术语与二叉树的形态

一、直觉：一张家族树

二、术语表

三、最容易搞混的：深度 vs 高度

四、二叉树的三种形态

五、高度与 $\log n$ 的关系

六、练习

七、练习答案

八、常见错误

九、本节总结

results matching ""

No results matching ""

第 9 章 二叉树与遍历

9.1 树的术语与二叉树的形态

一、直觉：一张家族树

二、术语表

三、最容易搞混的：深度 vs 高度

四、二叉树的三种形态

五、高度与 $\log n$ 的关系

六、练习

七、练习答案

八、常见错误

九、本节总结

results matching ""

No results matching ""

第 9 章　二叉树与遍历

9.1　树的术语与二叉树的形态