NOIP 普及组初赛 · NOIP 2018 普及组初赛试题 第 7 题

根节点深度为 $0$，一棵深度为 $h$ 的满 $k(k>1)$ 叉树，即除最后一层无任何子节点外，每一层上的所有结点都有 $k$ 个子结点的树，共有（ ）个结点。

这题本质就是等比数列求和。拿到题先别急着套公式，数数层数：深度h意味着从第0层到第h层，一共h+1层。每层节点数是k的幂次，首项1，公比k，直接代入求和公式即可，结果就是(k^(h+1)-1)/(k-1)。

最容易栽跟头的地方有两个：一是把深度h当成层数，漏加一层，导致指数算成h而不是h+1，这样总和就少了最后一层；二是公式记混，把(k^(h+1)-1)/(k-1)记成(k^h-1)/(k-1)或者把分母搞错。还有个陷阱是看选项时，B和C都只算到了倒数第二层或最后一层，D的指数又不对，必须用特例验证，比如k=2,h=1时，二叉树根加一层共3个节点，代入A得(2^2-1)/(2-1)=3正确，其他选项全错，这样一眼就能排除。

考点定位

这道题考查的是满k叉树的节点总数计算，核心知识点是等比数列求和以及树的深度与层数关系。命题人特别喜欢在“深度”和“层数”这两个容易混淆的概念上挖坑，同时把等比数列求和公式的指数部分作为干扰项，看学生是否真的理解了公式的推导过程，而不是死记硬背。对于信息学竞赛来说，这类基础概念题往往是第一道送分题，但也是最容易因为粗心丢分的地方。

概念拆解：什么是满k叉树？

想象一棵家族树：

• 最上面是根节点（老祖宗），深度是0
• 每个节点都恰好有 k个孩子（最底层除外）
• 深度为h的意思是共有h+1层（第0层到第h层）

注意这里的“深度”定义：根节点深度为0，所以深度为h的树，实际上包含了从0到h共h+1层节点。这是很多初学者容易忽略的，直接以为深度h就是h层。