二叉树结点、度、边核心计算方法总结

一、核心概念定义

1.1 结点相关定义

  • 结点：二叉树中存储数据的基本单元（含数据项和指向子树的指针）。
  • 分类：
    • 根结点：无父结点的唯一结点（二叉树的起点）；
    • 叶子结点（终端结点）：无左、右子树的结点（度为 0）；
    • 内部结点（非终端结点）：至少有一个子树的结点（度为 1 或 2）；
    • 父结点 / 子结点：若结点 A 指向结点 B，则 A 是 B 的父结点，B 是 A 的子结点（左子结点 / 右子结点）。

1.2 度相关定义

  • 结点的度：一个结点拥有的

    子结点个数

    （二叉树中结点度只能是 0、1、2）：

    • 度为 0：叶子结点（无左、右子）；
    • 度为 1：只有左子或只有右子的结点；
    • 度为 2：同时有左子和右子的结点。

  • 树的度：二叉树中所有结点的度的最大值（二叉树的度固定≤2）。

1.3 边的定义

  • 连接两个相邻结点（父结点与子结点）的线段，即结点之间的逻辑关联。
  • 例：根结点到左子结点的连线是一条边，度为 2 的结点有两条边（分别连接左、右子结点）。

二、通用计算关系

2.1 边数与结点总数的关系

公式：边数（E）= 结点总数（n）- 1

推导逻辑：

  • 二叉树是 “连通且无环” 的结构，根结点是唯一无父结点的结点；
  • 除根结点外，每个结点都恰好对应一条来自父结点的边（1 个结点→1 条入边）；
  • 因此：边数 = 结点总数 - 1（根结点无入边，需减去）。

示例：

  • 3 个结点的二叉树（根 + 左子 + 右子），边数 = 3-1=2（根→左、根→右）；
  • 5 个结点的二叉树，边数 = 5-1=4。

2.2 结点总数与各度数结点数的关系

2.2.1 基本公式

结点总数（n）= 度为0的结点数（n₀） + 度为1的结点数（n₁） + 度为2的结点数（n₂）
  • 说明：二叉树中所有结点的度只能是 0、1、2，因此总数等于三类结点数之和。

2.2.2 二叉树特有推论（关键！）

度为0的结点数（n₀）= 度为2的结点数（n₂） + 1
  • 核心结论：叶子结点数永远比度为 2 的结点数多 1，与度为 1 的结点数（n₁）无关。

2.2.3 推导逻辑（零基础可懂）

结合 “边数的两种计算方式” 联立推导：

  1. 方式一：从结点度推导边数度为 0 的结点：无子女→贡献 0 条边；度为 1 的结点：1 个子女→贡献 1 条边；度为 2 的结点：2 个子女→贡献 2 条边；因此：总边数（E）= 0×n₀ + 1×n₁ + 2×n₂ = n₁ + 2n₂。
  2. 方式二：从结点总数推导边数由 2.1 的公式：E = n - 1，且n = n₀ + n₁ + n₂，因此：E = (n₀ + n₁ + n₂) - 1。
  3. 联立等式求解两种方式计算的边数相等，因此：n₁ + 2n₂ = (n₀ + n₁ + n₂) - 1化简：两边消去 n₁，得 2n₂ = n₀ + n₂ - 1 → n₀ = n₂ + 1。

2.3 示例应用（巩固公式）

例题 1：已知某二叉树有 n₂=5（度为 2 的结点 5 个），n₁=3（度为 1 的结点 3 个），求 n₀（叶子结点数）和总结点数 n。

  • 解：
    1. 由推论 n₀ = n₂ + 1 → n₀ = 5 + 1 = 6；
    2. 总结点数 n = n₀ + n₁ + n₂ = 6 + 3 + 5 = 14；
    3. 边数 E = n - 1 = 13（或 E = n₁ + 2n₂ = 3 + 2×5 = 13，验证一致）。

例题 2：已知某二叉树有叶子结点 10 个，求度为 2 的结点数。

  • 解：由 n₀ = n₂ + 1 → n₂ = n₀ - 1 = 10 - 1 = 9。

三、特殊二叉树的额外计算规则

3.1 满二叉树

定义：

除叶子结点外，所有结点的度均为 2（无度为 1 的结点，n₁=0），且叶子结点都在同一层。

核心计算：

设满二叉树的深度为 h（根结点深度为 1）：

  1. 结点总数：n = 2ʰ - 1；
  2. 叶子结点数（n₀）：n₀ = 2ʰ⁻¹（最后一层全是叶子）；
  3. 度为 2 的结点数（n₂）：n₂ = 2ʰ⁻¹ - 1（符合 n₀ = n₂ + 1）；
  4. 边数：E = n - 1 = 2ʰ - 2。

示例：

深度 h=3 的满二叉树：

  • 结点总数 = 2³ -1=7；
  • 叶子结点数 = 2³⁻¹=4；
  • 度为 2 的结点数 = 4-1=3；
  • 边数 = 7-1=6。

3.2 完全二叉树

定义：

深度为 h 的完全二叉树，前 h-1 层是满二叉树，第 h 层的叶子结点从左到右连续排列（无空缺）。

核心计算：

  1. 度为 1 的结点数（n₁）：只能是 0 或 1（因第 h 层叶子连续，不会出现 “单个子结点不连续” 的情况）；
  2. 结点总数与深度的关系：2ʰ⁻¹ ≤ n < 2ʰ（h 是深度），可通过此公式求深度 h：h = ⌊log₂n⌋ + 1（向下取整）；
  3. 叶子结点数（n₀）：
    • 若 n 为奇数（n₁=0）：n₀ = (n + 1) / 2；
    • 若 n 为偶数（n₁=1）：n₀ = n / 2；（本质仍满足 n₀ = n₂ + 1，可推导验证）。

四、核心公式总结

计算目标 公式 适用场景
边数（E） E = 结点总数（n）- 1 所有二叉树
结点总数（n） n = n₀ + n₁ + n₂ 所有二叉树
叶子结点数（n₀） n₀ = n₂ + 1 所有二叉树
满二叉树结点总数 n = 2ʰ - 1（h 为深度） 满二叉树
满二叉树叶子结点数 n₀ = 2ʰ⁻¹ 满二叉树
完全二叉树深度（h） h = ⌊log₂n⌋ + 1 完全二叉树
完全二叉树叶子结点数 奇数 n：n₀=(n+1)/2；偶数 n：n₀=n/2 完全二叉树

五、解题步骤

  1. 明确已知条件（如 n₀、n₁、n₂、n、h 等）；
  2. 优先使用核心推论（n₀ = n₂ + 1）和边数公式（E = n-1）；
  3. 若为特殊二叉树（满 / 完全），调用对应专属公式；
  4. 联立方程求解未知量，验证结果是否符合二叉树定义（如 n₁只能是 0 或 1，n₀≥1 等）。

通过以上公式和逻辑，可解决二叉树结点、度、边的绝大多数计算问题，建议结合例题反复练习，强化记忆核心推论（n₀ = n₂ + 1）的应用。