1

数据结构

所属模块：DS-3 树与二叉树 · 本模块第 12 / 16 个概念

在「DS-3 树与二叉树」概念体系中的位置

flowchart TD
    A["一对多的层次关系"] --> B["树的定义与基本术语<br/>度 / 深度 / 高度"]
    A --> C["二叉树：每个结点 ≤ 2 个孩子<br/>+ 五条性质"]
    C --> D["存储：二叉链表 / 顺序存储"]
    C --> E["遍历：先 / 中 / 后 / 层序<br/>（根何时被访问）"]
    E --> F["由两个序列重建唯一二叉树<br/>（必须含中序）"]
    E --> G["遍历要栈 → 线索二叉树<br/>空指针改指前驱/后继"]
    A --> H["树 / 森林 ↔ 二叉树<br/>孩子-兄弟表示法"]
    C --> I["应用：哈夫曼树<br/>WPL 最小 = 最优前缀编码"]
    C --> J["应用：并查集<br/>集合的并 / 查"]

核心概念（性质五条，选择题弹药库）：

性质	内容
1	第 $i$ 层至多 $2^{i-1}$ 个结点
2	深度 $k$ 的二叉树至多 $2^k - 1$ 个结点
3	任何二叉树： $n_0 = n_2 + 1$ （叶 = 双分支 + 1）——最常用
4	$n$ 个结点的完全二叉树深度 $\lfloor \log_2 n \rfloor + 1$
5	完全二叉树顺序编号：父 $\lfloor i/2 \rfloor$ 、左孩子 $2i$ 、右孩子 $2i+1$ ；由 $n$ 反推叶/度为 1 的结点数

2011-4：768 结点完全二叉树 → 叶 384（ $n_0=n_2+1$ 与 $n = n_0+n_1+n_2$ 联立，完全二叉树 $n_1 \in \{0,1\}$ ）。
2009-5：第 6 层 8 个叶的完全二叉树最多 111 个结点。
2016-5：森林 25 结点 15 边 → 树的棵数 = 25−15 = 10（每棵树结点数 = 边数+1）。