树¶
方法速览¶
| 任务 | 方法 | 口诀 |
|---|---|---|
| 判断是不是树 | 连通 + 无环（n 点恰好 n−1 边且连通） | 连通无环就是树 |
| 点与边 | n 个结点的树恰有 \(n-1\) 条边 | 点数减一 |
| 度数方程 | \(\sum \text{度} = 2(n-1)\)（每条边贡献两个度） | 度和是边数两倍 |
| 森林 | m 棵树、n 个点 → \(n - m\) 条边 | 树数也扣 |
| 找父 / 找子 | 父亲表示法找父 O(1)；孩子表示法找子快 | 父快用父表，子快用子表 |
树的基本概念¶
树是连通且无环的无向图。家族称谓：
| 称谓 | 含义 |
|---|---|
| 根 | 没有父亲的结点（画在顶上） |
| 父亲（双亲） | 指向自己的那个结点——每个非根结点恰有一个父亲 |
| 孩子 | 自己指向的结点 |
| 兄弟 | 同一个父亲的结点 |
| 叶子（终端结点） | 度为 0（没有孩子）的结点 |
| 分支结点 | 度 ≥ 1 的非叶结点 |
| 森林 | m 棵互不相连的树 |
三条硬结论：
- 树没有环——任意两点之间恰有一条路径；
- n 个结点的树恰有 \(n - 1\) 条边；
- 度数方程：\(\sum \deg = 2(n-1)\)（每条边给两端各贡献 1 度）。
例：n = 13 的树，有 3 个度为 3 的结点、5 个度为 2 的结点，求叶子数。设叶子 x 个：\(3\times3 + 5\times2 + x = 2\times(13-1) = 24\)，解得 \(x = 5\)——先数非叶结点的度，剩下的度全给叶子。
二叉树是“每个结点至多两个孩子”的树（左右孩子有区别）——注意二叉树与“度为 2 的树”不同：二叉树允许只有左孩子/为空，且子树有左右之分（详细性质见二叉树页）。
删边成树：n 点 m 边的连通图要变成树，保留 \(n-1\) 条、删去 \(m-(n-1) = m-n+1\) 条。
树的存储方式¶
| 存储法 | 结构 | 找父亲 | 找孩子 |
|---|---|---|---|
| 父亲表示法 | parent[i] 存 i 的父亲编号（根存 0 或 −1） |
\(O(1)\) | 要扫全表 \(O(n)\) |
| 孩子表示法 | 每个结点挂一个孩子链表（或 vector<int>） |
要扫全表 | \(O(\text{孩子数})\) |
| 孩子兄弟表示法 | 每结点两个指针：第一个孩子 + 右兄弟 | — | 森林/树转二叉结构 |
例（父亲表示法，下标从 1 开始）：
| 结点 i | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| parent[i] | 0 | 1 | 1 | 2 | 2 |
根是 1（父亲为 0）；4、5 的父亲是 2——从任意结点顺 parent 向上走就到根，判根、求祖先都是 O(树高)。
竞赛里最常用的是 vector 邻接表存无向树（每条边存两次），DFS/BFS 遍历。
练习题目¶
练习 1 · 树的定义¶
题目
下列关于树的说法，错误的是（ ）
- A. 树是连通的无环图
- B. 树中任意两点之间恰有一条路径
- C. 树中可能存在环
- D. 树中每个非根结点恰有一个父亲
答案与解析
答案：C
无环是树的定义成分；有环就成了普通图。
练习 2 · 点数与边数¶
题目
一棵 100 个结点的树有（ ）条边。
- A. \(100\)
- B. \(101\)
- C. \(99\)
- D. \(50\)
答案与解析
答案：C
n 点恰 \(n-1\) 条边。
练习 3 · 由边数反推点数¶
题目
一棵树有 37 条边，则结点数为（ ）
- A. \(36\)
- B. \(37\)
- C. \(74\)
- D. \(38\)
答案与解析
答案：D
结点 = 边 + 1 = 38。
练习 4 · 度数和¶
题目
10 个结点的树，所有结点的度数之和为（ ）
- A. \(9\)
- B. \(10\)
- C. \(20\)
- D. \(18\)
答案与解析
答案：D
\(\sum \deg = 2(n-1) = 18\)——每条边给两端各记 1 度。
练习 5 · 度数方程求叶子¶
题目
一棵 13 个结点的树中，有 3 个度为 3 的结点、5 个度为 2 的结点，其余为叶子。叶子有（ ）个。
- A. \(5\)
- B. \(4\)
- C. \(6\)
- D. \(8\)
答案与解析
答案：A
\(\sum\deg = 2\times12 = 24\)；非叶贡献 \(3\times3 + 5\times2 = 19\)，叶子贡献 \(24 - 19 = 5\)（每个叶子 1 度）→ 5 个，且 \(3+5+5 = 13\) 对账成功。
练习 6 · 叶子的度¶
题目
树中“叶子结点”的度数是（ ）
- A. \(2\)
- B. \(1\)
- C. \(0\)
- D. 不确定
答案与解析
答案：C
叶子 = 没有孩子 = 度为 0。（注意根若只有一个孩子，它在“有根树”里度数为 1，不算叶子。）
练习 7 · 父亲的唯一性¶
题目
关于树中结点的父亲（ ）
- A. 每个结点都恰好有一个父亲
- B. 根结点没有父亲，其余结点恰有一个父亲
- C. 一个结点可以有多个父亲
- D. 叶子没有父亲
答案与解析
答案：B
根没有父亲；其余结点“到根的路径上倒数第二个”就是唯一父亲。C 多父亲成图（有环或非树）。
练习 8 · 兄弟的定义¶
题目
结点 A、B 是兄弟，当且仅当（ ）
- A. A 是 B 的祖先
- B. A、B 都是叶子
- C. A、B 在同一层
- D. A、B 有同一个父亲
答案与解析
答案：D
兄弟 = 同父；同层不一定是兄弟（堂兄弟）。
练习 9 · 森林的边数¶
题目
由 3 棵树组成的森林共有 20 个结点，边数为（ ）
- A. \(17\)
- B. \(18\)
- C. \(19\)
- D. \(20\)
答案与解析
答案：A
每棵树“点 − 1”条边：\(20 - 3 = 17\)。
练习 10 · 森林与树的关系¶
题目
含 n 个结点、m 棵树的森林，再添加（ ）条边可以变成一棵树。
- A. \(m\)
- B. \(n - m\)
- C. \(m - 1\)
- D. \(n - 1\)
答案与解析
答案：C
把 m 棵树串成一棵，需要 m−1 条“桥”边。
练习 11 · 删边成树¶
题目
有 6 个顶点、9 条边的连通无向图，至少删去（ ）条边才能变成一棵树。
- A. \(3\)
- B. \(4\)
- C. \(5\)
- D. \(6\)
答案与解析
答案：B
树只需 \(6-1=5\) 条边，删 \(9-5 = 4\) 条，即 \(m-n+1\)。
练习 12 · 环的判定¶
题目
n 个结点的无向图有 \(n\) 条边，则它（ ）
- A. 一定是树
- B. 一定是森林
- C. 一定不是树
- D. 可能是树
答案与解析
答案：C
树恰有 \(n-1\) 条边；n 条边必然含环（连通与否都多了一条）。
练习 13 · 二叉树的定位¶
题目
二叉树是（ ）
- A. 每个结点恰好有两个孩子的树
- B. 任何无环图
- C. 度为 2 的树
- D. 每个结点至多有两个孩子、且子树分左右的树
答案与解析
答案：D
“至多”+“分左右”两个要点：结点可以只有左孩子；这是它与一般“度为 2 的树”的区别。
练习 14 · 三叉树的每层上限¶
题目
三叉树（每个结点至多 3 个孩子）第 5 层（根为第 1 层）最多有（ ）个结点。
- A. \(27\)
- B. \(81\)
- C. \(243\)
- D. \(15\)
答案与解析
答案：B
第 i 层最多 \(3^{i-1}\)：\(3^4 = 81\)。
练习 15 · 三叉树高度下界¶
题目
根的高度为 1，一棵 100 个结点的三叉树高度至少为（ ）
- A. \(5\)
- B. \(4\)
- C. \(6\)
- D. \(7\)
答案与解析
答案：A
高度 h 最多容纳 \(\dfrac{3^h - 1}{2}\) 个结点：h=4 时 \(\frac{81-1}{2} = 40 < 100\)；h=5 时 \(\frac{243-1}{2} = 121 \ge 100\) → 至少 5。
练习 16 · 父亲表示法找父亲¶
题目
父亲表示法 parent[i] 存每个结点的父亲，找结点 7 的父亲需（ ）
- A. 做不到
- B. \(O(n)\)——扫描全表
- C. \(O(\log n)\)
- D. \(O(1)\)——直接读
parent[7]
答案与解析
答案：D
父亲就存在数组里，一步读到；代价是找孩子要扫全表。
练习 17 · 父亲表示法找孩子¶
题目
用父亲表示法，要列出结点 v 的所有孩子，需要（ ）
- A. \(O(n)\) 扫描整个 parent 数组
- B. \(O(1)\)
- C. \(O(\deg v)\)
- D. \(O(1)\) 但要递归
答案与解析
答案：A
孩子没被直接存，只能找“所有 parent[i] == v 的 i”，扫全表。
练习 18 · 孩子表示法¶
题目
孩子表示法（每个结点挂孩子链表）的优势是（ ）
- A. 找父亲 O(1)
- B. 访问某结点的所有孩子高效
- C. 省一半内存
- D. 树变成二叉树
答案与解析
答案：B
孩子直接挂链上，逐个遍历即可；但找父亲要扫全表——与父亲表示法互为镜像。
练习 19 · 选存储的依据¶
题目
应用需要频繁“从结点向上走到根”，最合适的存储是（ ）
- A. 父亲表示法
- B. 孩子表示法
- C. 邻接矩阵
- D. 孩子兄弟表示法
答案与解析
答案：A
沿 parent 一路向上，每步 O(1)，共 O(树高)。
练习 20 · 父亲表示法的根¶
题目
父亲表示法中，通常把根的 parent 值设为（ ）
- A. \(1\)
- B. 它自己
- C. \(0\)（或 \(-1\)）——一个不会撞上真实结点的标记
- D. 树的高度
答案与解析
答案：C
0 / −1 表示“没有父亲”，用来识别根、终止向上的遍历。设成自己会死循环。
练习 21 · 孩子兄弟表示法¶
题目
孩子兄弟表示法中，每个结点的两个指针分别指向（ ）
- A. 父亲和母亲
- B. 第一个孩子和右邻的兄弟
- C. 左右两个孩子
- D. 前驱和后继
答案与解析
答案：B
“第一个孩子 + 右兄弟”两根指针，能把任何树/森林转成二叉结构处理。
练习 22 · 树 vs 图¶
题目
树与一般图的本质区别（ ）
- A. 树的结点更少
- B. 树连通且无环；一般图可以有环、可不连通
- C. 树不能用邻接表存
- D. 图有向、树无向
答案与解析
答案：B
树是图的特例：连通 + 无环 + n−1 边三者互相推出。
练习 23 · 结点数与祖先¶
题目
一棵树中，从根到某叶子的路径上有 6 个结点，该叶子的深度（根深度为 1）是（ ）
- A. \(5\)
- B. \(12\)
- C. \(7\)
- D. \(6\)
答案与解析
答案：D
路径上有几个结点，深度就是几：根（1）到叶（6）。
练习 24 · 树的边数下界¶
题目
n 个结点的连通图至少要（ ）条边。
- A. \(n\)
- B. \(n-2\)
- C. \(n-1\)
- D. \(\frac{n(n-1)}{2}\)
答案与解析
答案：C
连通最少 = 树 = n−1 条；再少必不连通。
练习 25 · 完全图的边数对比¶
题目
8 个结点的无向完全图有 28 条边，把它变成一棵树要删（ ）条边。
- A. \(21\)
- B. \(20\)
- C. \(27\)
- D. \(7\)
答案与解析
答案：A
树保留 7 条：\(28 - 7 = 21\) 条被删，即 \(m - n + 1\)。
练习 26 · 综合判断¶
题目
n = 5 的无向图有 4 条边且连通，则它（ ）
- A. 一定有环
- B. 是一棵树
- C. 是森林但不是树
- D. 无法确定
答案与解析
答案：B
连通 + 恰 \(n-1\) 条边 = 树（此时无环自动成立）。
历年真题¶
2021 年 · 第 6 题¶
题目
对于有 \(n\) 个顶点、\(m\) 条边的无向连通图 (\(m > n\))，需要删掉（ ）条边才能使其成为一棵树。
- A.
n - 1 - B.
m - n - C.
m - n - 1 - D.
m - n + 1
答案与解析
答案：D
树保留 \(n-1\) 条边，删去 \(m - (n-1) = m - n + 1\) 条。
干扰项思路：B 是 \(m-n\)（把“保留 n−1”算成“保留 n”的差一错误）。
2023 年 · 第 5 题¶
题目
根节点的高度为 \(1\)，一棵拥有 \(2023\) 个节点的三叉树高度至少为（ ）。
- A. \(6\)
- B. \(7\)
- C. \(8\)
- D. \(9\)
答案与解析
答案：C
高度 h 的三叉树最多 \(\dfrac{3^h - 1}{2}\) 个结点（等比求和 \(1 + 3 + \dots + 3^{h-1}\)）：
| h | 最大结点数 \(\frac{3^h-1}{2}\) |
|---|---|
| 7 | \(1093 < 2023\) |
| 8 | \(3280 \ge 2023\) |
装下 2023 个结点至少要高度 8。
易错小结¶
- 树 = 连通无环，n 点恰 \(n-1\) 边；三条件知二推一；
- 度数方程 \(\sum\deg = 2(n-1)\)：已知各度结点数求叶子，先算非叶的度、余数除以 1；
- 删边成树删 \(m - n + 1\) 条（连通图）；森林 n 点 m 棵树 \(n - m\) 条边，串成树再补 m−1 条；
- 父亲表示法找父 O(1) 找子 O(n)，孩子表示法正相反——按“频繁问什么”选存储；
- 二叉树是“至多两孩子 + 分左右”，不是“度为 2 的树”；
- 三叉树（m 叉树）高度 h 最多 \(\frac{3^h - 1}{2}\)（一般式 \(\frac{m^h - 1}{m - 1}\)）个结点。