【数据结构】深入理解：完全二叉树中叶子节点与分支节点的数量关系推导
在研究二叉树结构时，完全二叉树（Complete Binary Tree）是一种非常常见也非常有规律的结构。它在数据结构与算法题中应用广泛，比如堆排序、树的层序遍历等。
我们今天要探讨的问题是：
对于一棵完全二叉树，其度为0、1、2的节点数分别为多少？它们之间有什么关系？
二、基本概念回顾
在一棵二叉树中，节点根据“度”可以分为三类：
- 度为0（n₀）：叶子节点（没有子节点）
- 度为1（n₁）：只有一个子节点的节点
- 度为2（n₂）：有两个子节点的节点
整个二叉树的总节点数：
n = n₀ + n₁ + n₂
在完全二叉树中，还具有一些特性：
- 所有层都被完全填满，除了最后一层；
- 最后一层的节点从左到右连续排列；
- 所以，最多只有一个度为1的节点（n₁ ≤ 1），否则就不是完全二叉树了。
三、推导节点数量关系
Step 1：边数公式
在任何一棵树中，总的边数为节点数减1，即：
总边数 = n - 1
而每个节点的“出边数”取决于它的度数：
- 度为1的节点提供1条边；
- 度为2的节点提供2条边；
- 叶子节点（度为0）没有边。
因此：
n - 1 = n₁ + 2n₂ ——【公式①】
Step 2：节点总数公式
我们知道：
n = n₀ + n₁ + n₂ ——【公式②】
将【公式②】代入【公式①】：
(n₀ + n₁ + n₂) - 1 = n₁ + 2n₂
消掉 n₁：
n₀ + n₂ - 1 = 2n₂
整理得：
n₀ = n₂ + 1 ——【结论①】
这就是我们常听说的经典关系：
完全二叉树中，叶子节点数 = 双分支节点数 + 1
四、奇数性质的推导
根据上面【结论①】，我们接着可以得到：
n₀ + n₂ = (n₂ + 1) + n₂ = 2n₂ + 1
这就是一个奇数形式：
叶子节点 + 双分支节点 = 奇数
也就是说：
- 无论这棵完全二叉树有多少个节点；
- 只要它是完全二叉树；
- 那么它的 n₀ + n₂ 必定是奇数！
你甚至可以进一步整理为：
n₀ = 2n₂ + 1
这在某些算法题中可以直接使用，无需重新建树或遍历。
五、举个例子验证一下
我们来看一棵完全二叉树，如下：
A/ \B C/ \ /D E F
统计一下：
- 度为2的节点：A（有左右子树）、B（有左右子树） → n₂ = 2
- 度为1的节点：C（只有左子树） → n₁ = 1
- 度为0的节点：D、E、F → n₀ = 3
验证：
- n₀ = n₂ + 1 → ✅ 3 = 2 + 1
- n₀ + n₂ = 3 + 2 = 5 → 是奇数 ✅
- n = 6，总边数为 5，计算 n₁ + 2n₂ = 1 + 2×2 = 5 ✅
全部验证通过。
六、总结
本文通过推导与公式推演，得出了如下关于完全二叉树的重要结论：
- 完全二叉树中，叶子节点数 = 双分支节点数 + 1
- 所以 ( n₀ + n₂ = 2n₂ + 1 )，一定是奇数
- 最多只存在一个度为1的节点（n₁ ≤ 1）
如果觉得这篇推导对你有帮助，欢迎点赞、收藏或者留言交流。🌱