1. 简介
在本教程中，我们将讨论如何计算满 k 叉树（Full k-Ary Tree）的总节点数。我们将先从迭代和递归方法入手，最后再引入一个纯数学公式解法。
2. 什么是满 k 叉树？
满 k 叉树是一种树结构，其中除了叶子节点外，每个节点都有恰好 k 个子节点。
如下是一个 k = 3 的满 k 叉树示意图：
在这个例子中，叶子节点数为 27，总节点数为 40。
✅ 只要 k ≥ 2，我们就可以仅通过叶子节点数来推导出整棵树的节点总数。
3. 迭代解法
3.1 算法流程
迭代方法从叶子节点向上回溯到根节点：
- 每层节点数是上一层的 1/k（向上取整）
- 每次将当前层的节点数加到总和中
- 直到当前层只剩一个节点（即根节点）
3.2 伪代码实现
function ComputeTotalNodes(leaves, k):
if k < 2 or leaves < 0:
return error "Invalid Input"
total = leaves
count = leaves
finished = false
while count > 0 and count % k == 0:
count = count / k
total += count
if count == 1:
finished = true
break
if not finished:
return error "Invalid Input"
return total
⚠️ 注意：该算法对输入进行了验证，确保输入合法。
4. 递归解法
4.1 递归思路
递归的本质是：当前层以下的总节点数 = 当前层节点数 + 上层以下的总节点数
公式表示如下：
$$ T_i = N_i + T_{i-1} \quad (i \geq 1), \quad T_0 = 1 $$
其中：
- $ T_i $：第 i 层及以下的总节点数
- $ N_i $：第 i 层的节点数
4.2 伪代码实现
function ComputeTotalNodes(leaves, k):
if k < 2 or leaves < 0:
error "Invalid Input"
return ComputeTotalNodesRecursive(leaves, k, leaves)
function ComputeTotalNodesRecursive(count, k, total):
if count % k != 0:
return error "Invalid Input"
count = count / k
total += count
if count <= 1:
return total
else:
return ComputeTotalNodesRecursive(count, k, total)
✅ 优点：
- 将验证逻辑集中于入口函数
- 隐藏递归实现细节，对外提供统一接口
5. 数学公式解法
5.1 先计算树的高度
每一层的节点数构成一个等比数列：
$$ 1, k, k^2, k^3, ..., \text{leaves} $$
总节点数就是这个等比数列的前 n 项和：
$$ \text{Total} = \frac{k^h - 1}{k - 1} $$
其中 h 是树的高度：
$$ h = 1 + \log_k(\text{leaves}) $$
5.2 直接计算公式
我们可以将高度计算过程合并到公式中，最终得到：
$$ \text{Total} = \text{leaves} + \frac{\text{leaves} - 1}{k - 1} $$
✅ 伪代码实现如下：
function ComputeTotalNodes(leaves, k):
if k < 2 or leaves < 0:
error "Invalid Input"
total = leaves + (leaves - 1) / (k - 1)
if total % 1 != 0:
error "Invalid Input"
return total
⚠️ 注意：该公式要求 (leaves - 1) 能被 (k - 1) 整除，否则说明输入非法。
6. 时间复杂度分析
| 方法 | 时间复杂度 | 说明 |
|---|---|---|
| 迭代法 | O(log leaves) | 每次除以 k，直到为 1 |
| 递归法 | O(log leaves) | 与迭代法相同 |
| 高度计算法 | O(log leaves) | 依赖 log 运算 |
| 公式法 | O(1)（假设支持除法） | 实际可能仍为 O(log leaves) |
7. 总结
本教程介绍了多种计算满 k 叉树总节点数的方法：
✅ 迭代法：从叶子向上回溯
✅ 递归法：逻辑清晰，易于理解
✅ 数学公式法：最简洁高效，但依赖输入合法性
最终，推荐使用公式法，因为它简洁、高效，适合工程中快速实现。但在实际编码中，建议加入输入合法性校验以避免运行时异常。