3.2 树与图
本篇定位：树与图是数据结构的"非线性结构"部分（一对多 / 多对多）。9 年真题中二叉树直接考过 1 题（2025 单48 满二叉树节点数），图未直接考过——但二叉树性质、遍历、二叉排序树是计算机专业基础课的常客考点，且 2027 预测（栈/队列应用、二叉树、查找、排序、复杂度）明确把二叉树列为补考点。本章把树与图的核心考点讲透，防漏网优先。 数据依据：
01-真题/真题文本/+01-真题/考点汇总/；答案以专业判断为准。 阅读提示：二叉树与 3.3 章查找（二叉排序树）和排序（堆排序）直接衔接；图与 5.x 网络（路由算法）概念互通。
一、考点定位（本章真题统计）
| 考点 | 真题锚点 | 频次 | 考法 |
|---|---|---|---|
| 满二叉树节点数 | 2025 单48 | 1 年 | 深度 K 的满二叉树有 2^K − 1 个节点 |
| 二叉树（其他） | — | 0 年 | 未考（2027 预测补考点） |
| 图 | — | 0 年 | 未考（防漏网） |
命题规律：树与图在 9 年真题中只有 1 题（2025 单48），直接考"满二叉树节点数 = 2^K − 1"。但二叉树性质是计算机基础课的高频概念题素材，且与查找（二叉排序树）、排序（堆）交叉，2027 预测 0–1 题：大概率是"二叉树性质/节点数计算/遍历序列"类送分题。图大概率仍不考，但基础概念（顶点/边/度、有向无环）值得防漏网。
二、知识框架（先搭骨架）
树（非线性：一对多）
├── 术语：根、节点、叶子（度为 0）、度（孩子数）、深度/高度（层数）、
│ 双亲/孩子/兄弟、子树
├── 二叉树（每个节点最多两个孩子，左/右有序）
│ ├── 满二叉树：每层都满，深度 K → 节点数 2^K − 1（2025 单48）
│ ├── 完全二叉树：除最后一层外每层满，最后一层靠左连续
│ ├── 二叉排序树（BST）：左<根<右（见 3.3 章）
│ ├── 平衡二叉树（AVL）：左右子树高度差 ≤ 1
│ ├── 堆：完全二叉树，大根堆/小根堆（见 3.3 章排序）
│ └── 哈夫曼树：带权路径长度 WPL 最小
├── 二叉树性质（必背）
│ ├── 第 k 层最多 2^(k−1) 个节点
│ ├── 深度 K 的二叉树最多 2^K − 1 个节点（满二叉树达到）
│ ├── 叶子数 n0 = 度为 2 的节点数 n2 + 1（n0 = n2 + 1）
│ └── 完全二叉树节点 i 的孩子：左 2i、右 2i+1，双亲 ⌊i/2⌋
├── 遍历（先序/中序/后序/层序）
│ ├── 先序：根→左→右；中序：左→根→右；后序：左→右→根
│ └── 已知中序 + 先序/后序 可唯一重建二叉树
└── 树的存储：双亲表示法、孩子表示法、孩子兄弟表示法
图（非线性：多对多）
├── 有向图/无向图；顶点、边（弧）、度（无向）/入度出度（有向）
├── 存储：邻接矩阵（二维数组）、邻接表（链表）
├── 遍历：深度优先 DFS（栈/递归）、广度优先 BFS（队列）
├── 连通性：连通图、连通分量、生成树
├── 最短路径：Dijkstra（单源）、Floyd（任意两点）
├── 最小生成树：Prim、Kruskal
└── 拓扑排序：有向无环图（DAG）顶点线性序列（AOV 网）
一句话记忆：树一对多、图多对多；二叉树性质三条（第 k 层 2^(k−1)、满树 2^K−1、n0=n2+1）；遍历"先根、中左根右、后根"；图的核心=邻接矩阵/邻接表 + DFS/BFS + 最短路径 + 拓扑排序。
三、考点详解
3.1 树的术语
精确定义：树 = n（n≥0）个节点的有限集合，有且仅有一个根节点；其余节点分为若干互不相交的子树。树是一对多的非线性结构。
必背术语：
- 度：节点拥有的子树数（孩子数）；树中最大度称为树的度；
- 叶子（终端节点）：度为 0 的节点；
- 深度/高度：节点所在层数（根在第 1 层）；
- 双亲/孩子/兄弟：直接上层节点/直接下层节点/同双亲的节点。
3.2 二叉树的性质（2025 单48，必考计算）
精确定义：二叉树 = 每个节点至多有两个孩子（左孩子、右孩子），且左右有序（区分左/右子树）的树。
三条必背性质：
- 第 k 层最多 2^(k−1) 个节点（k≥1）；
- 深度为 K 的二叉树最多 2^K − 1 个节点（当且仅当满二叉树时取等号）；
- 叶子节点数 n0 = 度为 2 的节点数 n2 + 1（即 n0 = n2 + 1）。
符号读法（全书首现，之后各章通用）：⌊x⌋ = x 向下取整（floor／地板：不超过 x 的最大整数，如 ⌊3.9⌋ = 3、⌊4⌋ = 4）；⌈x⌉ = x 向上取整（ceiling／天花板：不小于 x 的最小整数，如 ⌈3.1⌉ = 4、⌈4⌉ = 4）。记法：横杠在下 = 地板、横杠在上 = 天花板；两者对恰好整数都不动（⌊4⌋ = ⌈4⌉ = 4）。 ⚠️ 两个符号必须"同向配对"（⌊…⌋ 或 ⌈…⌉）——混搭不是标准数学符号：⌊x⌉（下一个上）偶见于部分教材，表示"四舍五入到最近整数"（.5 怎么处理各书不一）；⌈x⌋（上一个下）无通行含义，见到按笔误处理。另注意老教材的高斯符号 [x]（长得就是普通方括号）表示"不超过 x 的最大整数"，等价于 ⌊x⌋（如 [−1.5] = −2，不是 −1）——见 [x] 得按上下文区分"取整"还是"就是个括号／数组下标"。
性质 3 讲透（记号：n0/n1/n2 分别是度为 0/1/2 的节点数，总节点数 n = n0+n1+n2）：
- 推导（数孩子）：除根以外，每个节点都是某节点的孩子 → 孩子总数 = n−1；孩子由谁生——n1 个节点各生 1 个、n2 个节点各生 2 个、叶子不生 → 孩子总数 = n1+2n2。联立：n1+2n2 = n−1 = n0+n1+n2−1，消去 n1 → n0 = n2+1。
- 直觉（树怎么长出来的）：起步只有根，它自己就是叶子（n0=1、n2=0，差恰好 1）；树每长一步只有两种动作——给某叶子添 1 个孩子（旧叶子不再是叶子、新孩子补位，n0 不变、n2 不变），或添 2 个孩子（n0 净 +1，该节点同时升级为度 2，n2 也 +1）——两边永远同步 +1，差保持 1。
- 验证：A 生 B、C；B 生 D、E；C 生 F——度 2 的是 A、B（n2=2），度 1 的是 C（n1=1），叶子是 D、E、F（n0=3）：3 = 2+1 ✓。
- 考试用法：①正向 n2=5 → n0=6（摸底卷第 8 题原题）；②反向 n0=9 → n2=8；③完全二叉树变体：n 个节点 → 叶子 = ⌈n/2⌉（完全二叉树 n1 只能取 0 或 1，与 n=n0+n1+n2、n0=n2+1 联立解出；例：100 个节点 → 叶子 50、度 2 有 49、度 1 有 1）。
2025 单48 直接考性质 2：深度为 K 的满二叉树有 2^K − 1 个节点（答案 D）。满二叉树 = 每一层节点数都达到最大值（第 k 层 2^(k−1) 个），各层求和：1+2+4+…+2^(K−1) = 2^K − 1。
完全二叉树：除最后一层外，每层节点数都达到最大；最后一层靠左连续排列。性质：完全二叉树可用数组顺序存储，节点 i 的左孩子 2i、右孩子 2i+1、双亲 ⌊i/2⌋（从 1 编号）。
满二叉树 vs 完全二叉树（易混）：
- 满二叉树：每一层都满（所有叶子在同一层）——一定也是完全二叉树；
- 完全二叉树：最后一层可能不满，但必须靠左连续——不一定是满二叉树。
- 例：深度 3 的满二叉树 7 个节点；深度 3 的完全二叉树 4~7 个节点都算（必须靠左）。
3.3 二叉树的遍历
遍历 = 按某种次序访问每个节点一次。四种方式：
| 方式 | 次序 | 口诀 |
|---|---|---|
| 先序（前序） | 根 → 左子树 → 右子树 | 根左右 |
| 中序 | 左子树 → 根 → 右子树 | 左根右 |
| 后序 | 左子树 → 右子树 → 根 | 左右根 |
| 层序 | 从上到下、从左到右（队列实现） | 一层层来 |
已知中序 + 先序（或后序）可唯一确定一棵二叉树（先序第一个=根，中序定位左右子树，递归）；但只有先序+后序不能唯一确定（无法区分左右子树）。
3.4 二叉排序树 / 平衡二叉树 / 哈夫曼树（防漏网重点）
- 二叉排序树（BST）：左子树所有节点 < 根 < 右子树所有节点；中序遍历 BST 得到递增有序序列（重要性质）。查找：从根出发，比根小往左、大往右，平均 O(log n)，最坏 O(n)（退化成链表）。见 3.3 章。
- 平衡二叉树（AVL）：任意节点的左右子树高度差 ≤ 1；保证查找 O(log n)（不会退化）。
- 哈夫曼树（最优二叉树）：带权路径长度 WPL 最小的二叉树；用于哈夫曼编码（出现频率高的字符编码短）——构造：每次取权值最小的两棵树合并。
3.5 图（防漏网重点）
精确定义：图 = 顶点（节点）集合 + 边（弧）集合，表示多对多关系。
基本概念：
- 有向图：边有方向（弧，<vi,vj>）；无向图：边无方向（(vi,vj)）；
- 度：无向图顶点的度 = 关联的边数；有向图分入度/出度；
- 连通图/连通分量：无向图任意两点可达 → 连通图（否则有多个连通分量）；
- 生成树：连通图的极小连通子图（n 个顶点 n−1 条边）；
- 有向无环图（DAG）：无环的有向图——可用于拓扑排序、关键路径。
存储结构：
- 邻接矩阵：n×n 二维数组，A[i][j]=1 表示有边——判断两点是否相邻 O(1)，但稀疏图浪费空间；
- 邻接表：每个顶点一个链表存邻接点——省空间，适合稀疏图。
遍历（与树遍历对应）：
- DFS 深度优先：一条路走到底再回溯（栈/递归）——类似先序遍历；
- BFS 广度优先：逐层扩展（队列）——类似层序遍历。
经典算法（了解名称+用途即可）：
- Dijkstra：单源最短路径（贪心，不能处理负权边）；
- Floyd：任意两点最短路径（动态规划）；
- Prim / Kruskal：最小生成树（Prim 加点、Kruskal 加边）；
- 拓扑排序：DAG 中顶点线性排序（AOV 网，如课程先修关系）。
四、易错坑汇总（命题人惯用陷阱）
- 满二叉树节点数 = 2^K − 1（2025 单48）——注意是深度 K；"第 k 层最多 2^(k−1) 个"是另一问，别混。选项常设 2K、2^(K−1) 等干扰项。
- n0 = n2 + 1——叶子数比度为 2 的节点数多 1（任何非空二叉树都成立）。常与"求叶子数/求度为 2 的节点数"搭配考。
- 满二叉树 vs 完全二叉树——满二叉树每层都满；完全二叉树仅最后一层可能不满且必须靠左连续。"完全二叉树一定是满二叉树"是错误说法（反过来对）。
- 遍历序列——先序"根左右"、中序"左根右"、后序"左右根"；中序 + 先序（或后序）才能唯一确定二叉树，"只有先序+后序可确定"是错误说法。
- BST 中序遍历是递增序列——"中序遍历二叉排序树得到递减序列"是错误说法（左<根<右 → 中序递增）。
- 图 vs 树——图可以成环（树无环）；树是图的特例（连通无环）；"树是线性结构"错误（一对多，非线性）。
- DFS 用栈、BFS 用队列——深度优先"后进先出"（栈/递归），广度优先"先进先出"（队列）；正好对应 3.1 章的栈/队列特性。
- Dijkstra 不能处理负权边——"Dijkstra 适用于含负权边的图"是错误说法（负权须用 Bellman-Ford）。
五、横向扩展（防漏网：本章边界内、真题尚未考但可能补考的点）
说明：横向扩展覆盖"大纲范围内但 9 年真题未考过"的知识，标注【新增概率】供取舍。
- 二叉树性质计算【高】：已知"深度为 5 的二叉树最多多少个节点？"（31 个）、"n0=5，求 n2"（n2=4）——2025 单48 的直接变体，2027 高概率。
- 由遍历序列重建二叉树【中】：先序+中序求后序类题——概念题高频变体。
- 完全二叉树节点编号【中】：节点 i 的孩子 2i/2i+1、双亲 ⌊i/2⌋——数组存储堆（堆排序）的底层（见 3.3 章）。
- 哈夫曼树与编码【中】：WPL 计算、哈夫曼编码（频率高的字符短编码）——计算机基础常见送分题。
- 二叉排序树查找/插入【中】：BST 查找比较次数、插入位置——与 3.3 章查找衔接。
- 图的度与边数关系【低】：无向图所有顶点度之和 = 2×边数；有向图入度之和 = 出度之和 = 边数——计算题素材。
- 拓扑排序【低】：AOV 网先修课程排序——"拓扑排序只适用于有向无环图"。
- 最小生成树/最短路径算法对应【低】：Prim=加点、Kruskal=加边、Dijkstra=单源最短路、Floyd=任意两点——"算法名称↔用途"匹配题。
六、真题演练（代表性真题 + 解析）
例 1（2025 单48） 深度为 K 的满二叉树有（口径已核）个节点。 A. K² B. 2K C. 2^(K−1) D. 2^K−1
答案：D。满二叉树每一层节点数都达到最大值：第 k 层 2^(k−1) 个，深度 K 共 1+2+4+…+2^(K−1) = 2^K − 1 个节点。C 项 2^(K−1) 是第 K 层（最后一层）的节点数——经典干扰：只数最后一层，漏掉上面所有层（最后一层只占总数的一半多一点）。口诀：总节点 = 2^深度 − 1，最后一层 = 2^(深度−1)。 ⚠️ 文本勘误：真题 OCR 原文 C、D 均作"2k-1"（上标丢失、存档里两者无法区分）；据流传解析原文"深度为 k 的满二叉树的结点数为 2^k−1；第 k 层上的结点数为 2^(k−1)"推断——D = 2^K−1（答案）、C = 2^(K−1)（干扰项）。本书旧版选项 C 误写成 2^K−1（与 D 重复）、解析又误称"C 是 2K−1"，均为对 OCR 的误读，已按上述推断恢复。
例 2（2025 单48 变体·防漏网） 一棵深度为 5 的满二叉树，叶子节点的个数是（口径已核）。 A. 8 B. 16 C. 31 D. 15
答案：B。第 k 层（叶子层）节点数 = 2^(k−1) = 2^4 = 16（性质 1）；整棵树节点数 2^5−1=31（性质 2）。口诀：叶子数看最后一层 2^(k−1)，总节点数看 2^K−1。
例 3（防漏网） 在一棵二叉树中，度为 2 的节点有 5 个，则叶子节点有（口径已核）个。 A. 4 B. 5 C. 6 D. 无法确定
答案：C。二叉树性质 n0 = n2 + 1 = 5 + 1 = 6。口诀：叶子数 = 度为 2 的节点数 + 1。
例 4（防漏网） 下列关于二叉排序树的说法，正确的是（口径已核）。 A. 中序遍历二叉排序树得到递减序列 B. 左子树所有节点值均小于根节点值 C. 二叉排序树的查找效率与树的高度无关 D. 二叉排序树一定是平衡二叉树
答案：B。二叉排序树定义：左子树所有节点 < 根 < 右子树所有节点，故中序遍历得到递增序列（A 错、B 对）。查找效率取决于高度（C 错）；BST 可能退化成链（不平衡），不一定是 AVL（D 错）。口诀：左小右大，中序递增。
七、本章小结
- 一条主线：树（一对多）→ 二叉树性质三条（第 k 层 2^(k−1)、满树 2^K−1、n0=n2+1）→ 遍历四种（根左右/左根右/左右根/层序）→ 二叉排序树/哈夫曼 → 图（多对多）→ 邻接矩阵/邻接表、DFS/BFS、最短路/拓扑。
- 必背计算：满二叉树节点数 2^K−1（2025 单48）；叶子数 n0=n2+1；第 k 层最多 2^(k−1)。
- 必背对应：DFS→栈/递归，BFS→队列；Dijkstra→单源最短路，Floyd→任意两点，Prim/Kruskal→最小生成树；中序+先序（或后序）→唯一确定二叉树。
- 防漏网重点：哈夫曼编码、完全二叉树编号（堆的底层）、图的度与边数、拓扑排序（AOV）。
- 衔接预告：二叉排序树/堆→3.3 章查找与排序；复杂度（O(log n)/O(n log n)）→3.4 章。