考研笔记

树的定义、术语与性质

这一节的术语教材自己说了「无须刻意记忆」，但 5.1.3 的五条性质必须会算。

教材的注意框原话：「上述概念无须刻意记忆，根据实例理解即可。考研时不大可能直接考查概念，而都是结合具体的题目考查。」——所以 5.1.2 快速扫过，把时间全给 5.1.3 的数数公式。

那五条性质加上一个「三式联立」的技巧，构成了本章选择题里出现频率最高的一类：给部分度数，求结点数或叶结点数。

机制

定义与两个特点

树是 个结点的有限集。 时称为空树。在任意一棵非空树中应满足：

  1. 有且仅有一个特定的称为根的结点；
  2. 当 时，其余结点可分为 个互不相交的有限集 ，其中每个集合本身又是一棵树，并称为根的子树。

树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

  1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
  2. 树中所有结点可以有零个或多个后继。

因此在 个结点的树中有 条边。

必须精确的几个术语

术语定义易错处
堂兄弟双亲在同一层的结点互为堂兄弟不要求双亲相同——图 5.1 中 与 互为堂兄弟
结点的层次 / 深度根为第 1 层，深度就是结点所在的层次从 1 起算
树的高度（深度）树中结点的最大层数
结点的高度以该结点为根的子树的高度与「深度」方向相反
结点的度该结点的孩子个数
树的度树中结点的最大度数
分支结点 / 叶结点度 为分支结点（非终端结点）；度 为叶结点（终端结点）
路径长度路径上所经过的边的个数数边不数结点——与第 7 章的「查找长度数结点」正相反
树的路径长度从树根到每个结点的路径长度的总和包括所有结点，不只叶结点；根到自身的路径长度为 0；二叉树同样适用
森林 棵互不相交的树的集合 可以为 0

边界辨析：

教材的注意框：「因为树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的， 同一双亲的两个孩子之间不存在路径。」 亲兄弟之间没有路径——这一条与图论里的无向路径直觉相反，是判断题的常客。

关联对照：

森林与树只差一个根：只要把树的根结点删去就成了森林；反之，只要给 棵独立的树加上一个结点， 并把这 棵树作为该结点的子树，则森林就变成了树。 这条关系是 5.4.2 树、森林与二叉树的转换 的全部依据，也是 2016 年的命题点。

五条性质

  1. 树的结点数 等于所有结点的度数之和加 1。 结点的度是指该结点的孩子数量，每个结点与其每个孩子都由唯一的边相连，因此所有结点的度数之和等于边数之和；树中的结点（除根外）都有唯一的双亲，因此 边数之和 。
  2. 度为 的树中第 层上至多有 个结点（）。
  3. 高度为 的 叉树至多有 个结点。（等比数列）
  4. 度为 、具有 个结点的树的最小高度 。
  5. 度为 、具有 个结点的树的最大高度 。 由此也可逆推出：高度为 、度为 的树至少有 个结点。

边界辨析：

「度为 的树」和「 叉树」不是一回事。

  • 度为 的树：树的度恰好是 ，即至少有一个结点有 个孩子。
  • 叉树：每个结点至多有 个孩子，可以一个度为 的结点都没有（甚至可以是空树）。

性质 2、4、5 说的是度为 的树，性质 3 说的是 叉树。 性质 5 的 之所以要减 ，正是因为「度为 」强制要求某一层必须有 个孩子摊开。 这是本节最经典的陷阱。

三式联立：求结点与度的关系

教材在 5.1.4 的注意框里把这类题的解法固定成三个式子：

① ②度为的结点引出条分支 ③

「这类题目常在选择题中出现，读者对以上关系应当熟练掌握并灵活应用。」

手算模板

求结点数 / 叶结点数（三式联立）：

  1. 列 ①：总结点数 各度数的结点数之和。
  2. 列 ②：总分支数 。
  3. 用 ③ 把 ① 和 ② 连起来：。
  4. 代入已知量解方程。未知数只剩一个时就能出答案。

求最小 / 最大高度：先分清题目说的是「度为 的树」还是「 叉树」，再套性质 4 / 5 / 3。

边界

说法判断说明
「堂兄弟必须有相同的祖父」❌只要求双亲在同一层
「兄弟结点之间存在路径」❌分支是有向的，同一双亲的两个孩子之间不存在路径
「路径长度是路径上的结点数」❌是边的个数。与第 7 章的查找长度正相反
「结点的深度就是结点的高度」❌深度是所在层次（自上而下）；高度是以它为根的子树的高度（自下而上）
「森林至少有一棵树」❌，空森林也是森林
「度为 的树第 层至多 个结点」✅性质 2
「 叉树一定有度为 的结点」❌ 叉树只要求至多 个孩子
「度为 、 个结点的树最大高度是 」❌是 ——必须留出 个孩子摊在同一层
「 个结点的树有 条边」❌ 条，因为根没有前驱

口径差异：

算法竞赛里「树」几乎总是指无根树 / 图论意义上的树，会谈「直径」「重心」「路径」（无向、任意两点之间）。 408 的树是有根、有向、分层的：路径只能自上而下，兄弟之间没有路径，「高度」和「深度」是两个方向。 另外，「树的度」在算竞里基本不用（那里习惯说「最大出度」），而 408 的性质 2、4、5 全都建立在它上面。

对照速查

性质结论
结点数与度数度数
第 层最多（度为 ）
高度 最多（ 叉树）
最小高度（度为 ， 个结点）
最大高度（度为 ， 个结点）
高度 、度 的树至少 个结点
边数
三式内容
①
②
③

考点

  • 三式联立求结点与度的关系（2010、2016 命题追踪），本节最高频。
  • 「度为 的树」与「 叉树」的区分。
  • 指定结点数的 叉树的最小高度（2022 命题追踪），套性质 4。
  • 路径长度数边，且同一双亲的孩子之间无路径。
  • 森林与树相差一个根结点（2016 命题追踪）。
  • 深度与高度方向相反。

链接

反向链接