跳转至

408 高频考点精讲:树的概念(Tree Concepts, Degree, Nodes, and Height Relations)

模块归属:数据结构 · 树与二叉树
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生


一、 考情档案

  • 近十年考查频次:3 次(2016~2025 年:2016#42、2021#9、2022#4)
  • 历年总考查频次:6 次(历年统考考查还包含 2009#4、2010#5、2014#5)
  • 出题形式:单项选择题与综合解答题兼具。选择题分值为 2 分,解答题分值为 10 分。命题集中于树的形态极值代数推导、结点与度数的平衡方程求解、正则多叉树结构性质证明、特定约束(如 B 树各层容量)下的全树结点极大极小值计算。
  • 命题特点:
  • 结构代数恒等关系突出:严格依托图论与组合数学,重点考查顶点的度数累加、分支边数与总结点数的代数平衡方程。
  • 极值与边界形态分析频繁:围绕给定结点数推导最小高度或最大高度,或给定树高求解容量边界,考查满树模型与单支最窄模型的构造能力。
  • 概念术语严谨多维:重点辨析“度为 \(m\)$ \text{的树”与“} $\(m\) 叉树”的区别、正则多叉树约束、树高与层数的起点界定标准(从 1 还是从 0 起算)。
近十年考查年份分布:
2016   2017   2018   2019   2020   2021   2022   2023   2024   2025
 √      -      -      -      -      √      √      -      -      -
(#42)                               (#9)   (#4)

二、 具体考察内容

1. 树的形式化定义与拓扑图论特征

(1)递归定义

树(Tree)是 \(n\)(\(n \ge 0\))个结点的有限集合。 * 当 \(n = 0\) 时,称为空树。 * 在任意一棵非空树中: 1. 有且仅有一个特定的称为根(Root)的结点; 2. 当 \(n > 1\)$ \text{时,其余结点可划分为} $\(m\)(\(m > 0\)$ \text{)个互不相交的有限集合} $\(T_1, T_2, \dots, T_m\),其中每一个集合本身又是一棵树,并且称为根结点的子树(Subtree)。

(2)图论定义

  • 无向图视阈:树是连通且无简单回路(无环)的无向图。
  • 有向图视阈:树是一种特殊的弱连通有向无环图,称为有向树(Directed Tree)或有根树(Rooted Tree)。其拓扑特征为:有且仅有一个入度为 0 的结点(即根结点),其余每个结点的入度均严格等于 1。

(3)核心拓扑术语界定

  • 结点的度(Degree):结点拥有的子树个数(即该结点的分支孩子个数)。

    辨析说明:在图论无向图中,顶点的度定义为与该顶点相关联的边数;在树结构中,结点的度特指其向下的出度,不计入指向其双亲的入度。

  • 树的度:树中所有结点度的最大值,记为: $\(\deg(T) = \max_{v \in T} \{\deg(v)\}\)$
  • 分支结点(内部结点,Internal Node):度大于 0 的结点(非叶结点)。
  • 叶结点(终端结点,Leaf Node):度为 0 的结点。
  • 结点的孩子、双亲、兄弟与祖先:
  • 结点的子树之根称为该结点的孩子(Child);
  • 该结点称为孩子的双亲(Parent);
  • 同一个双亲的孩子之间互称兄弟(Sibling);
  • 从根到该结点所经分支上的所有结点称为该结点的祖先(Ancestor)。
  • 路径与路径长度:
  • 两结点之间的路径是由两个结点之间所经过的结点序列构成的单向分支序列;
  • 路径长度定义为路径上所经过的分支边(Edge)的数目,绝对不是路径上的结点数目。
  • 结点的层次、深度与高度:
  • 层次(Level):通常从根结点起算为第 1 层,其孩子结点为第 2 层,以此类推。
  • 结点的深度(Depth):从根结点(深度为 1)开始自顶向下逐层累加至该结点的层数(亦有部分教材定义根深度为 0,即根到该结点的路径边数)。
  • 结点的高度(Height):从该结点自底向上到该结点子树中最远叶结点的层数(叶结点高度为 1)。
  • 树的高度(深度):树中结点的最大层次。

2. 度数、边数与结点数的代数恒等定理及严格证明

(1)定理一:树的边数与总结点数恒等式

在任意一棵包含 \(n\)$ \text{个结点的树中,其总分支边数} $\(e\) 恒满足: $\(e = n - 1\)$

严格证明(入度映射法):
考虑树的有向拓扑特性。在树结构中,除根结点之外,其余每一个结点都有且仅有一个唯一的双亲结点。因此,从双亲指向子结点的每一条有向边,都与该有向边所指向的子结点构成一一映射。
即:每一个非根结点有且仅有一条进入它的边(入度为 1),而根结点的入度为 0。
设树中全部结点的集合为 \(V\)$ \text{,总结点数为} $\(|V| = n\)。则树的总边数等于所有结点的入度之和: $\(e = \sum_{v \in V} ID(v) = ID(\text{root}) + \sum_{v \in V \setminus \{\text{root}\}} ID(v) = 0 + \sum_{v \in V \setminus \{\text{root}\}} 1 = n - 1\)$ 证毕。

(2)定理二:树的度数累加恒等式

设一棵树中各结点的最大度数为 \(k\)$ \text{。记度为} $\(i\)$ \text{的结点个数为} $\(n_i\)(\(0 \le i \le k\))。则存在两组基础代数方程: 1. 结点分类累加方程: $\(n = \sum_{i=0}^k n_i = n_0 + n_1 + n_2 + \cdots + n_k\)$ 2. 分支边数累加方程(由各结点的出度向下引出): $\(e = \sum_{i=0}^k i \cdot n_i = 0 \cdot n_0 + 1 \cdot n_1 + 2 \cdot n_2 + \cdots + k \cdot n_k\)$

(3)定理三:叶结点数与高阶分支结点数关系核心定理

将定理一与定理二联立: $\(e = n - 1 \implies \sum_{i=0}^k i \cdot n_i = \left( \sum_{i=0}^k n_i \right) - 1\)$ 展开并对齐两端: $\(n_1 + 2n_2 + 3n_3 + \cdots + kn_k = (n_0 + n_1 + n_2 + \cdots + n_k) - 1\)$ 方程两端同时消去度为 1 的结点项 \(n_1\): $\(2n_2 + 3n_3 + \cdots + kn_k = n_0 + n_2 + n_3 + \cdots + n_k - 1\)$ 将 \(n_0\) 隔离至等式左侧,其余项移至右侧并合并同类项: $\(n_0 = 1 + \sum_{i=2}^k (i - 1)n_i = 1 + n_2 + 2n_3 + 3n_4 + \cdots + (k - 1)n_k\)$

推论辨析: * 二叉树推论(\(k=2\)): $\(n_0 = n_2 + 1\)$ 即二叉树中叶结点数恒等于度为 2 的分支结点数加 1。 * 独立性规律: 在任意树结构中,叶结点的数量 \(n_0\)$ \text{完全独立于度为 1 的结点数量} $\(n_1\)。改变度为 1 的单分支链长度,绝不改变树中叶结点的总数。


3. m 叉树与度为 m 的树的辨析及极值推导

(1)概念辨析

辨析维度 度为 \(m\)$ \text{的树 } $\(m\)$ \text{叉树(} $\(m\)-ary Tree)
度数极值限制 结点的最大度数严格等于 \(m\)$ \text{ 结点的最大度数不超过} $\(m\)$ \text{(即} $\(\le m\))
存在性要求 树中至少存在一个结点的度等于 \(m\)$ \text{ 允许所有结点的度数均小于} $\(m\)
空树允许性 树必定非空,结点数 \(n \ge m + 1\)$ \text{ 允许为空树(} $\(n = 0\))
子树位置有序性 若为一般无序树,子树无严格槽位次序 各子树具有严格的位置编号(从第 1 到第 \(m\) 孩子)

(2)极值定理与容量推导

  • 定理四:第 \(i\) 层最大结点数
    在 \(m\)$ \text{叉树中,第} $\(i\)$ \text{层(} $\(i \ge 1\))最多拥有的结点数为: $\(N_i \le m^{i-1}\)$ 证明:根结点为第 1 层,结点数为 \(1 = m^0\)$ \text{。第 2 层每个结点最多引出} $\(m\)$ \text{个孩子,故最多} $\(m^1\)$ \text{个结点。依此类推,由数学归纳法可知第} $\(i\)$ \text{层结点数上限为} $\(m^{i-1}\)。

  • 定理五:高度为 \(h\)$ \text{的} $\(m\)$ \text{叉树的最大结点数(满} $\(m\) 叉树)
    当高度为 \(h\)$ \text{的} $\(m\)$ \text{叉树中每一层均达到容量上限时,称为满} $\(m\) 叉树。其结点总数为等比数列求和: $\(N_{\max}(h) = \sum_{i=1}^h m^{i-1} = \frac{m^h - 1}{m - 1}\)$

  • 定理六:含有 \(n\)$ \text{个结点的} $\(m\) 叉树的最小高度
    要使高度最小,树中各层应尽可能排满结点。设最小高度为 \(h_{\min}\)$ \text{,则} $\(n\)$ \text{个结点必须能被高度为} $\(h_{\min}\)$ \text{的满} $\(m\)$ \text{叉树容纳,但无法被高度为} $\(h_{\min}-1\)$ \text{的满} $\(m\) 叉树容纳: $\(N_{\max}(h_{\min} - 1) < n \le N_{\max}(h_{\min})\)$ 代入满树求和公式: $$\frac{m^{h_{\min}-1}

  • 1}{m

  • 1} < n \le \frac{m^{h_{\min}}

  • 1}{m

  • 1}$$ 不等式各项同乘 \(m - 1\) 并加 1: $\(m^{h_{\min}-1} < n(m - 1) + 1 \le m^{h_{\min}}\)$ 两端取以 \(m\) 为底的对数: $\(h_{\min} - 1 < \log_m [n(m - 1) + 1] \le h_{\min}\)$ 根据天花板整函数(向上取整)定义: $\(h_{\min} = \lceil \log_m [n(m - 1) + 1] \rceil\)$

  • 定理七:高度为 \(h\)$ \text{且度为} $\(m\) 的树的最小结点数
    一棵高度为 \(h\)$ \text{且度为} $\(m\) 的树,必须同时满足两个约束:

  • 高度为 \(h\)$ \text{:意味着树至少有} $\(h\) 层,每一层至少有 1 个结点;
  • 度为 \(m\)$ \text{:意味着树中至少存在 1 个结点拥有} $\(m\)$ \text{个孩子。这} $\(m\) 个孩子必须位于同一层。 为使结点总数最少,使该度为 \(m\)$ \text{的特异结点分布于某一层,提供} $\(m\) 个子结点,其余各层均保持仅有 1 个结点: $\(N_{\min}(h) = (h - 1) + m = h + m - 1\)$

4. 正则 k 叉树与严格 m 叉树的代数结构

(1)正则 k 叉树的定义

若一棵非空 \(k\)(\(k \ge 2\)$ \text{)叉树} $\(T\)$ \text{中,每一个非叶结点的度数均严格等于} $\(k\)$ \text{(即树中结点的度数只能取 0 或} $\(k\)$ \text{两类,不存在度在} $\(1\)$ \text{到} $\(k-1\)$ \text{之间的结点),则称} $\(T\)$ \text{为正则} $\(k\)$ \text{叉树(Regular} $\(k\)$ \text{-ary Tree)。当} $\(k = 2\) 时,即为严格二叉树(Strictly Binary Tree)。

(2)叶结点与非叶分支结点的严格代数关系

设正则 \(k\)$ \text{叉树中非叶分支结点数为} $\(m\)$ \text{,叶结点数为} $\(n_0\)。 * 树中全部结点数为 \(n = n_0 + m\); * 树中每一个非叶分支结点均向下引出 \(k\) 条边,故整棵树的分支边数总和为: $\(e = m \cdot k\)$ * 由树的边数公理 \(e = n - 1\),联立方程: $\(m \cdot k = (n_0 + m) - 1\)$ * 解出叶结点数 \(n_0\): $\(n_0 = (k - 1)m + 1\)$ * 总结点数 \(n\)$ \text{与非叶结点数} $\(m\) 的关系为: $\(n = m + n_0 = m + [(k - 1)m + 1] = k \cdot m + 1\)$

(3)树高为 h 时的极值形态推导(单结点树 h=1)

  • 最大结点总数 \(N_{\max}\): 树达到饱和状态,即为满 \(k\)$ \text{叉树。从第 1 层到第} $\(h\)$ \text{层,每层结点数依次为} $\(k^0, k^1, \dots, k^{h-1}\): $\(N_{\max} = \sum_{i=1}^h k^{i-1} = \frac{k^h - 1}{k - 1}\)$
  • 最小结点总数 \(N_{\min}\): 为使总结点数最少,树的结构应尽可能“细长”,即每一层仅容许 1 个分支结点向下裂变:
  • 第 1 层(根结点):有且仅有 1 个度为 \(k\) 的分支结点;
  • 第 2 层至第 \(h-1\)$ \text{层:每一层均由上一层的唯一分支结点引出} $\(k\)$ \text{个结点,且在这} $\(k\)$ \text{个结点中,有且仅有 1 个继续作为分支结点,其余} $\(k - 1\) 个结点均为叶结点;
  • 第 \(h\)$ \text{层:由第} $\(h-1\)$ \text{层唯一的分支结点引出} $\(k\) 个叶结点。 因此,除第 1 层仅有 1 个结点外,第 2 层至第 \(h\)$ \text{层的每一层均恰有} $\(k\) 个结点。全树最小结点总数为: $\(N_{\min} = 1 + (h - 1) \cdot k\)$

5. 树的高度的两种基准界定规范

在 408 统考历年真题及各大高校教材中,对于“树的高度”、“深度”以及“层数”的基准定义存在两种主要流派,审题时必须依据题干上下文准确锚定:

基准对比模型示意图:

       (根)        --- 基准 A:深度/层数 = 1;  基准 B:深度 = 0
      /   \
    (B)   (C)      --- 基准 A:深度/层数 = 2;  基准 B:深度 = 1
   /
 (D) [叶]          --- 基准 A:树高 h = 3;    基准 B:树高 h = 2(边数定义)
  • 基准 A(国内绝大多数教材标准,408 主流):
  • 单个根结点的树,高度 \(h = 1\);
  • 根结点位于第 1 层;
  • 空树高度 \(h = 0\);
  • 叶结点的高度为 1(若自底向上计算)。
  • 基准 B(部分国际教材标准,如算法导论 CLRS):
  • 树的高度定义为根结点到最远叶结点的最长简单路径的分支边数;
  • 单个根结点的树,高度 \(h = 0\);
  • 根结点深度为 0。

408 审题法则:
统考命题人通常会在题干中附带括号明确注明基准,例如“(单结点的树 \(h=1\))”或“(叶结点的高度为 1)”。一旦出现此类说明,必须严格套用对应的数学模型;若未显式注明,一律默认采用基准 A(单结点树高为 1)。


6. 树、森林到二叉树的拓扑转换映射法则

(1)孩子兄弟表示法(Left-Child Right-Sibling)

通过二叉链表存储一般树或森林:结点的左指针指向其长子(First Child),右指针指向其紧邻的右侧下一个兄弟(Next Sibling)。

(2)拓扑映射对应定理

  • 定理八:森林叶结点与二叉树左空指针的对应法则
    在树或森林转换为对应的二叉树后: 森林中所有叶结点的个数,严格等于二叉树中左孩子指针为空(lchild == NULL)的结点个数。 严格证明:
    在孩子兄弟表示法中,结点的左指针指向该结点的第一个孩子。若某结点在原树或森林中为叶结点,则该结点不存在任何孩子,故其左孩子指针必然为空(lchild == NULL)。反之,若二叉树中某结点的左指针为空,说明其在原树中无孩子结点,必为叶结点。两者构成双射关系。

  • 定理九:根结点链与右指针映射法则
    若一棵非空树转换为二叉树,由于树根不存在右侧兄弟,故二叉树的根结点的右指针必然为空(rchild == NULL)。
    若由包含 \(m\)$ \text{棵树的森林转换为二叉树,森林中第 1 棵树的根作为二叉树的根,第 2 棵至第} $\(m\)$ \text{棵树的根依次通过右指针串联成一条右斜链。因此二叉树根结点的右子树包含其余} $\(m-1\) 棵树的所有结点。


三、 近十年真题精讲(2016~2025)


【真题 1】2022 年 408 第 4 题 · 三叉树最小高度计算

题目
若三叉树 \(T\)$ \text{中有 244 个结点(叶结点的高度为 1),则} $\(T\) 的高度至少是( )。
A. 8          B. 7          C. 6          D. 5

【解析】

  1. 审题与数学模型建立:
    题干指出“叶结点的高度为 1”,且询问高度“至少”是多少。这等价于求解容纳 \(n = 244\)$ \text{个结点的三叉树所能达到的理论最小高度} $\(h_{\min}\)。
    在树的高度固定的前提下,当且仅当该树为满三叉树时,其所能容纳的结点总数达到极大值。若高度为 \(h\)$ \text{的满三叉树最大容量仍小于 244,则树的高度必然大于} $\(h\)。

  2. 数学推导与计算:
    在三叉树中,每一层结点的最大分支容量为 3。

  3. 第 1 层(叶结点向上回溯至根结点)最多容纳结点数:\(3^0 = 1\);
  4. 第 2 层最多容纳结点数:\(3^1 = 3\);
  5. 第 \(i\)$ \text{层最多容纳结点数:} $\(3^{i-1}\)。
    高度为 \(h\) 的满三叉树,其总结点数上限为等比数列求和:
    $$N_{\max}(h) = \sum_{i=1}^h 3^{i-1} = \frac{3^h

  6. 1}{3

  7. 1} = \frac{3^h

  8. 1}{2}$$

  9. 代入树高极值检验:

  10. 取 \(h = 5\):
    $\(N_{\max}(5) = \frac{3^5 - 1}{2} = \frac{243 - 1}{2} = 121\)$
    此时 \(121 < 244\),表明高度为 5 的三叉树至多只能承载 121 个结点,无法容纳 244 个结点。
  11. 取 \(h = 6\):
    $\(N_{\max}(6) = \frac{3^6 - 1}{2} = \frac{729 - 1}{2} = 364\)$
    此时 \(121 < 244 \le 364\)。高度为 6 的满三叉树最大容量为 364,足以容纳 244 个结点。
    故容纳 244 个结点所需的高度至少为 6。

  12. 选项辨析:

  13. A 选项 8、B 选项 7:高度为 7 或 8 均能容纳 244 个结点,但不是“至少”的高度(非极小值);
  14. C 选项 6:满足容量约束的最小高度整数解,正确;
  15. D 选项 5:最大容量仅为 121,无法容纳 244 个结点,错误。

正确答案:C


【真题 2】2021 年 408 第 9 题 · 3 阶 B 树特定约束下最大结点数推导

题目
在一棵高度为 3 的 3 阶 B 树中,根为第 1 层,若第 2 层中有 4 个关键字,则该树的结点个数最多是( )。
A. 11          B. 10          C. 9          D. 8

【解析】

  1. 核心原理与结构约束回顾:
    \(m\)$ \text{阶 B 树是一棵平衡的} $\(m\)$ \text{叉搜索树。对于 3 阶 B 树(} $\(m = 3\)):
  2. 关键字个数约束:
    除根结点外,每个非叶结点的关键字个数 \(k\) 必须满足:
    $$\lceil m/2 \rceil

  3. 1 \le k \le m

  4. 1 \implies \lceil 3/2 \rceil

  5. 1 \le k \le 2 \implies 1 \le k \le 2$$
    即第 2 层及以下非叶结点的关键字数只能是 1 或 2。根结点若非叶,关键字个数范围为 \(1 \le k \le 2\)。

  6. 分支数(孩子数)约束:
    结点的子树分支数严格等于该结点的关键字数加 1(即分支数 \(= k + 1\))。含 1 个关键字的结点有 2 个孩子,含 2 个关键字的结点有 3 个孩子。

  7. 逐层推导全树极大结点数:
    题目目标:全树高度为 3,第 2 层总计包含 4 个关键字,求全树结点个数最多是多少。
    全树结点总数等于第 1 层、第 2 层与第 3 层结点数之和:
    $\(N_{\text{total}} = N_1 + N_2 + N_3\)$

  8. 第 1 层(根结点):
    根结点只有 1 个,即 \(N_1 = 1\)。
    根结点的孩子即为第 2 层的结点。因为 3 阶 B 树中结点的最大分支数为 3,所以根结点的孩子数最多为 3,这意味着第 2 层的结点数上限为 3(即 \(N_2 \le 3\))。

  9. 第 2 层结点分布与分支极大化:
    已知第 2 层全部结点的关键字总数为 4。为了使第 3 层的结点数(即第 2 层结点的孩子总数)达到最大,必须满足两个条件:

    1. 第 2 层本身的结点数 \(N_2\) 尽可能多;
    2. 第 2 层所有结点的关键字总数能衍生出最多的孩子分支。
      每个结点若包含 \(k_j\)$ \text{个关键字,其孩子数为} $\(k_j + 1\)。
      若第 2 层有 \(N_2\) 个结点,则第 3 层的总结点数为:
      $\(N_3 = \sum_{j=1}^{N_2} (k_j + 1) = \sum_{j=1}^{N_2} k_j + \sum_{j=1}^{N_2} 1 = 4 + N_2\)$
      该代数式表明:第 3 层结点数 \(N_3\)$ \text{严格随第 2 层结点数} $\(N_2\) 的增加而单调递增。

    考察 \(N_2\) 的可能取值:
    - 能否 \(N_2 = 4\)$ \text{?若} $\(N_2 = 4\)$ \text{,需要第 2 层有 4 个结点,每个结点含 1 个关键字。但根结点在 3 阶 B 树中至多只能拥有 3 个分支孩子,因此第 2 层结点数至多为 3,即} $\(N_2\) 不可能达到 4。
    - 能否 \(N_2 = 3\)$ \text{?若} $\(N_2 = 3\)$ \text{,将 4 个关键字分配给 3 个结点。由于每个非根结点的关键字数范围为} $\([1, 2]\)$ \text{,可以将 4 个关键字合法划分为:} $\(1, 1, 2\)。
    此时 3 个结点的关键字数分别为 1, 1, 2,均满足合法性范围。
    根结点此时拥有 3 个孩子,根结点的关键字数取 2,分支数达到上限 3,完全合法。
    因此,\(N_2\) 的最大可能取值为 3。

  10. 第 3 层结点数计算:
    当 \(N_2 = 3\)$ \text{且关键字分布为} $\((1, 1, 2)\) 时,各结点的孩子数分别为:

    • 结点 1(1 个关键字):\(1 + 1 = 2\) 个孩子;
    • 结点 2(1 个关键字):\(1 + 1 = 2\) 个孩子;
    • 结点 3(2 个关键字):\(2 + 1 = 3\) 个孩子。
      第 3 层结点数达到理论极大值:
      $\(N_3 = 2 + 2 + 3 = 7\)$
      (或直接由公式 \(N_3 = 4 + N_2 = 4 + 3 = 7\) 计算)。
  11. 全树最大结点总数汇总:
    $\(N_{\text{total}} = N_1 + N_2 + N_3 = 1 + 3 + 7 = 11\)$

  12. 选项逐项辨析:

  13. A 选项 11:推导完全吻合,正确;
  14. B 选项 10:未将第 2 层结点数最大化(例如误将第 2 层设为 2 个各含 2 个关键字的结点,此时 \(N_2 = 2\),\(N_3 = 3 + 3 = 6\)$ \text{,总数为} $\(1 + 2 + 6 = 9 < 11\));
  15. C 选项 9、D 选项 8:均为非极大形态下的计算结果,错误。

正确答案:A


【真题 3】2016 年 408 第 42 题 · 正则 k 叉树叶子与极值结点数综合推导(解答题,10 分)

题目
如果一棵非空 \(k\)(\(k \ge 2\)$ \text{)叉树} $\(T\)$ \text{中每个非叶结点都有} $\(k\)$ \text{个孩子,则称} $\(T\)$ \text{为正则} $\(k\) 叉树。请回答下列问题并给出推导过程。
(1) 若 \(T\)$ \text{有} $\(m\)$ \text{个非叶结点,则} $\(T\) 中的叶结点有多少个?
(2) 若 \(T\)$ \text{的高度为} $\(h\)$ \text{(单结点的树} $\(h = 1\)$ \text{),则} $\(T\) 的结点数最多为多少个?最少为多少个?

【解析】

(1)第 (1) 问解析与数学推导

  • 步骤一:定义结构变量
    根据题设,正则 \(k\)$ \text{叉树中所有结点的度数只能是 0 或} $\(k\)。树中仅包含两类结点:
  • 叶结点:度数为 0,其数量记为 \(n_0\);
  • 非叶分支结点:度数严格为 \(k\)$ \text{,其数量记为} $\(n_k = m\)。
    全树的总结点数 \(n\) 为叶结点数与非叶结点数之和:
    $\(n = n_0 + m\)$

  • 步骤二:建立分支边数双向等式

  • 从树的整体拓扑性质考查:在任何非空树中,除根结点外每个结点有且仅有 1 条入边,故全树的边数 \(e\) 恒等于总结点数减 1:
    $\(e = n - 1 = n_0 + m - 1\)$
  • 从分支引出考查:树中全部边均由度为 \(k\)$ \text{的非叶结点引出,每个非叶结点恰好引出} $\(k\)$ \text{条边,而叶结点引出的边数为 0,故全树边数} $\(e\) 亦可表示为:
    $\(e = m \cdot k\)$

  • 步骤三:联立求解
    将上述两式联立:
    $\(n_0 + m - 1 = m \cdot k\)$
    移项整理,解得叶结点数:
    $\(n_0 = m \cdot k - m + 1 = (k - 1)m + 1\)$


(2)第 (2) 问解析与数学推导

题目设定树的高度的基准为“单结点的树 \(h = 1\)”。

  • 情况一:总结点数最多的树形分析(\(N_{\max}\))
    为使高度为 \(h\)$ \text{的正则} $\(k\)$ \text{叉树容纳最多的结点,树结构必须达到完全饱和状态,即为满} $\(k\) 叉树。
  • 结构形态:从第 1 层至第 \(h-1\)$ \text{层的每一个结点均为度为} $\(k\)$ \text{的非叶分支结点,第} $\(h\) 层的结点全部为叶结点;
  • 逐层结点数:第 \(j\)$ \text{层(} $\(1 \le j \le h\)$ \text{)的结点数为} $\(k^{j-1}\);
  • 结点总数求和:
    $\(N_{\max} = \sum_{j=1}^h k^{j-1} = 1 + k + k^2 + \cdots + k^{h-1} = \frac{k^h - 1}{k - 1}\)$

  • 情况二:总结点数最少的树形分析(\(N_{\min}\))
    为使高度为 \(h\)$ \text{的正则} $\(k\) 叉树容纳最少的结点,各层分支结点必须尽可能压缩,即每一层只允许有 1 个结点继续向下延伸分支:

  • 结构形态:
    • 第 1 层:只有 1 个根结点,该结点为度为 \(k\) 的分支结点;
    • 第 2 层至第 \(h-1\)$ \text{层:每一层均有上一层的唯一步骤分支结点生成的} $\(k\)$ \text{个结点。为了维持树的高度达到} $\(h\)$ \text{且不增加多余结点,在这} $\(k\)$ \text{个结点中,仅选出 1 个结点作为度为} $\(k\)$ \text{的分支结点继续向下延伸,其余} $\(k - 1\) 个结点均为叶结点;
    • 第 \(h\)$ \text{层:由第} $\(h-1\)$ \text{层唯一的那个分支结点向下引出} $\(k\) 个叶结点,不再继续延伸。
  • 逐层统计结点数:
    • 第 1 层结点数:\(1\);
    • 第 2 层至第 \(h\)$ \text{层(共计} $\(h - 1\)$ \text{层):每一层包含的结点数均严格等于} $\(k\)。
  • 总结点数累加:
    $\(N_{\min} = 1 + \sum_{j=2}^h k = 1 + (h - 1) \cdot k\)$

【答题规范与得分要点总结】

在 408 统考评分标准中,本题满分 10 分: 1. 第 (1) 问满分 4 分:正确列出边数与结点数关系式(\(e = n - 1\)$ \text{及} $\(e = mk\)$ \text{)得 2 分,准确推导出} $\(n_0 = (k - 1)m + 1\) 得 2 分;若仅写出结论未给出推导扣 2 分。 2. 第 (2) 问满分 6 分: - 最大值部分(3 分):说明满树形态得 1 分,给出等比求和表达式及化简结果 \(\frac{k^h - 1}{k - 1}\) 得 2 分; - 最小值部分(3 分):说明每层仅 1 个分支结点的形态得 1 分,推导并得出 \(1 + (h - 1)k\) 得 2 分。


四、 核心解题套路与易错陷阱

1. 核心解题套路

套路一:树型代数方程求解“三步法”

无论遇到何种给出结点度数分布、要求反求某类结点数或总结点数的题型,按顺序执行以下三步: 1. 写出结点总数方程: $\(n = n_0 + n_1 + n_2 + \cdots + n_k\)$ 2. 写出边数与出度方程: $\(e = 1 \cdot n_1 + 2 \cdot n_2 + \cdots + k \cdot n_k\)$ 3. 代入树的图论公理 \(e = n - 1\) 消元: $\(\sum_{i=1}^k i \cdot n_i = \left( \sum_{i=0}^k n_i \right) - 1\)$ 通过直接消去 \(n_1\)$ \text{,可秒杀所有关于叶结点} $\(n_0\) 的求解问题: $\(n_0 = 1 + \sum_{i=2}^k (i - 1)n_i\)$

套路二:树高极值“双向夹逼”不等式法

求解含有 \(n\)$ \text{个结点的} $\(m\) 叉树的最小树高(或给定树高求结点范围): 1. 牢记满树上界公式: $\(N_{\max}(h) = \frac{m^h - 1}{m - 1}\)$ 2. 建立双向不等式: $$\frac{m^{h-1}

  • 1}{m

  • 1} < n \le \frac{m^h

  • 1}{m

  • 1}$$

  • 直接计算 \(m^h\) 的临界幂次,利用向上取整公式: $\(h = \lceil \log_m [n(m - 1) + 1] \rceil\)$

套路三:森林转换二叉树指针推导法则

分析森林到二叉树的映射时: 1. 森林叶结点 \(\iff\) 二叉树左空指针:统计森林中叶结点的个数,直接寻找二叉树中 lchild == NULL 的结点数; 2. 二叉树空指针总数恒等式:任意包含 \(n\)$ \text{个结点的二叉树,其二叉链表中共有} $\(2n\)$ \text{个指针域,由于只有} $\(n-1\)$ \text{条边(即} $\(n-1\)$ \text{个非空指针),因此空指针总数恒等于} $\(2n - (n - 1) = n + 1\)。


2. 易错陷阱清单

  • 陷阱 1:混淆“度为 \(m\)$ \text{的树”与“} $\(m\) 叉树”的极小形态
  • 具有 \(n\)$ \text{个结点的} $\(m\)$ \text{叉树的高度,允许退化为} $\(n\)(当每个分支结点度数均为 1 时,退化为单支树);
  • 但对于“度为 \(m\)$ \text{的树”,树中至少必须有一个结点的度达到} $\(m\)$ \text{。因此高度为} $\(h\)$ \text{的度为} $\(m\)$ \text{的树,结点数最少为} $\(h + m - 1\)$ \text{,绝不是} $\(h\)。
  • 陷阱 2:忽视题目给出的树高与层数基准
    必须在审题时第一眼确认根结点是算作第 1 层还是第 0 层。若按根为第 0 层算,公式中的所有高度指数均需下移 1 位(满树总结点变为 \(\frac{m^{h+1} - 1}{m - 1}\))。
  • 陷阱 3:误将森林的叶结点对应为二叉树的叶结点
    在孩子兄弟表示法中:
  • 森林中的叶结点,其对应二叉树结点的左孩子必为空,但其右孩子完全可以非空(原森林中的叶结点可以有右侧兄弟)。
  • 二叉树中的真正叶结点要求左、右孩子指针均为空,这在原森林中对应“既无孩子、又无右兄弟”的结点。两者概念完全不同,切忌等同。
  • 陷阱 4:B 树分支数与关键字数关系的错位
    在涉及多叉树或 B 树结构综合考查时,牢记:结点的分支子树个数等于该结点所含关键字个数加 1。关键字数总和固定时,结点拆分越碎(结点数越多),产生的冗余分支总数就越多。

五、 考点速记清单

1. 核心公式与代数极值速查表

考点 / 概念 核心公式 / 约束关系式 关键物理意义与边界说明
树的边数公理 \(e = n - 1\) 根入度为 0,其余每个结点入度恒为 1
叶结点与度数关系 \(n_0 = 1 + \sum_{i=2}^k (i - 1)n_i\)$ \text{ 叶结点数完全独立于度为 1 的结点数} $\(n_1\)
二叉树叶结点公式 \(n_0 = n_2 + 1\) 二叉树叶结点数等于度为 2 的结点数加 1
满 \(m\)$ \text{叉树结点数 } $\(N_{\max} = \frac{m^h - 1}{m - 1}\)$ \text{ 高度为} $\(h\),根为第 1 层
\(n\)$ \text{结点} $\(m\)$ \text{叉树最小高度 } $\(h_{\min} = \lceil \log_m [n(m - 1) + 1] \rceil\) 各层达到饱和排布时的理论下界
度为 \(m\)$ \text{的树最小结点数 } $\(N_{\min} = h + m - 1\)$ \text{ 树高为} $\(h\)$ \text{,其中有且仅有 1 个结点度为} $\(m\)
正则 \(k\)$ \text{叉树叶结点数 } $\(n_0 = (k - 1)m + 1\) \(m\)$ \text{为度为} $\(k\) 的分支结点数
正则 \(k\)$ \text{叉树最小结点数 } $\(N_{\min} = 1 + (h - 1)k\)$ \text{ 树高为} $\(h\)$ \text{,除根外每层恰有} $\(k\) 个结点
二叉链表空指针总数 \(\text{NullPtrCount} = n + 1\)$ \text{ 适用于任意含} $\(n\) 个结点的二叉树

2. 核心概念对比速辨表

辨析对象 A 辨析对象 B 核心判别标准与本质区别
度为 \(m\)$ \text{的树 } $\(m\)$ \text{叉树 度为} $\(m\)$ \text{的树至少存在一个度等于} $\(m\)$ \text{的结点;} $\(m\)$ \text{叉树结点的度只需} $\(\le m\) 即可(允许空树)
森林的叶结点 转换后二叉树的叶结点 森林叶结点映射为二叉树中 lchild == NULL 的结点;二叉树叶结点要求 lchild == NULL 且 rchild == NULL
正则 \(k\)$ \text{叉树 满} $\(k\)$ \text{叉树 正则树只要求所有分支结点度为} $\(k\)(各叶结点可在不同层);满树要求所有叶结点必须在最底层
结点的度 图论顶点的度 树中结点的度特指其分支孩子数(出度);图论中无向顶点的度为关联的全部边数