本讲定位：选择题第一大户。七年真题统计（见
cspj-exam-analysis-2019-2025.md）：树类考点七年合计 26 分、年年有题，其中完全二叉树七年六考、哈夫曼四考、遍历还原三考、前中后缀表达式三考——本讲每个小节都有真题原型，是知识类专题里性价比最高的一讲。全部内容都是手算题：认结构、套公式、画图数数，一道 2 分题的标准耗时应在一分钟以内。前置知识：第 02 讲的 $2^n$ 数感（$2^{10} = 1024$ 系列要背熟）；第 05 讲的组合数（形态计数偶尔用）；第 01 讲的栈（表达式一节会呼应）。
适合对象：CSP-J 初赛。标注 ⭐ 的小节为进阶内容，第一遍学习可以跳过。
树 = 不含环的连通结构：一个根结点，其余结点各有唯一的父结点。术语一次记全：
| 术语 | 含义 | 备注 |
|---|---|---|
| 结点的度 | 它的孩子个数 | 注意：初赛语境的”度”不算父亲那条边 |
| 树的度 | 所有结点度的最大值 | “度为 2 的树”≠ 二叉树（二叉树区分左右孩子） |
| 叶子 | 度为 0 的结点 | 也叫终端结点 |
| 深度/层数 | 根为第 1 层，往下逐层加 1 | 初赛默认从 1 数；见到”从 0 数”的题面要立刻换算 |
| 祖先 / 子孙 | 从根到 $u$ 路径上的点 / $u$ 子树里的点 | 兄弟 = 同父结点 |
第一条公式：边数 $=$ 结点数 $- 1$。 理由一句话：除根外每个结点恰好向上贡献一条边。它有个高频推论——所有结点的度数之和 $=$ 边数 $= n - 1$（每条边恰好被一个”父亲”数到一次）：
$$ 0 \cdot n_0 + 1 \cdot n_1 + 2 \cdot n_2 + 3 \cdot n_3 + \cdots = n - 1 $$
例 1（真题常见皮）：一棵树有 8 个度为 2 的结点、4 个度为 3 的结点，其余全是叶子，求叶子数。设叶子 $x$ 个：总结点 $n = 8 + 4 + x$，度数和 $= 8 \times 2 + 4 \times 3 = 28 = n - 1$，故 $n = 29$，$x = 29 - 12 = 17$。“度数和 = 结点数 − 1”是解一切”数叶子”题的万能钥匙。
二叉树：每个结点至多两个孩子，且分左右（只有一个孩子时，“是左是右”算两棵不同的树——形态计数题的常设陷阱）。三条性质从上往下推：
性质一：第 $i$ 层至多 $2^{i-1}$ 个结点（每层翻倍）。
性质二：深度为 $h$ 的二叉树至多 $2^h - 1$ 个结点（等比求和 $1 + 2 + \cdots + 2^{h-1}$；装满的叫满二叉树）。
性质三（最常考）
：
$$ n_0 = n_2 + 1 \qquad \text{（叶子数 = 双孩子结点数 + 1）} $$
推导只需两行，建议当场跟学生推一遍而不是死背：结点数按度分类 $n = n_0 + n_1 + n_2$；边数按”孩子”数 $n - 1 = n_1 + 2n_2$。两式相减即得。它与 $n_1$ 无关——出题人最爱在题面里塞一个用不上的 $n_1$ 当烟雾弹。
例 2：某二叉树度为 2 的结点有 10 个，度为 1 的结点有 7 个，共有多少结点？——叶子 $n_0 = 10 + 1 = 11$，共 $11 + 7 + 10 = 28$ 个。