NOIP 提高组初赛 · NOIP 2009 提高组初赛试题 第 5 题

一个包含 $n$ 个分支结点（非叶结点）的非空满 $k$ 叉树，$k\geq 1$，它的叶结点数目为：

这题本质就是数边：满k叉树里每个非叶结点都贡献k条出边，总边数就是n×k；再利用树中‘边数=结点数-1’这个铁律，把总结点数拆成分支结点和叶结点，就能直接解出叶结点个数，千万别硬套二叉树的结论。

最容易栽跟头的是把‘边数=结点数-1'记混，或者看到k叉就下意识用二叉树性质去凑，结果把nk+1当成答案；还有人会把分支结点数当成叶结点数去代入公式，导致算出来是nk-1；还有一种情况是只盯着根节点想，忘了除根以外每个分支结点都有k个子结点，从而漏掉k-1这个系数，最后选错C。

考点与概念

这道题考的是树的边与结点关系以及满k叉树的定义。

什么是满k叉树？简单说，就是树里每一个非叶结点（分支结点）都恰好有k个子结点，不多也不少。

命题人怎么挖坑

命题人喜欢让你把二叉树的公式硬套到k叉树上，或者让你忽略‘边数=结点数-1'这个基本定理。选项A就是典型的二叉树结论（n+1）推广错了，选项B则是把分支结点数当成叶结点数去凑，选项C看起来很像但系数搞反了。只有D才是真正从边数推导出来的。

拿到题先想什么

1. 先画个图：n个分支结点，每个分支结点下面挂k条边，指向k个子结点。 2. 数边：总边数 = n × k。 3. 用树的性质：边数 = 总结点数 - 1。 4. 总结点数 = 分支结点数 + 叶结点数 = n + L。 5. 列方程：n × k = (n + L) - 1。 6. 解出L：L = n × k + 1 - n = (k - 1)n + 1。

一步步推（含计算）

设叶结点数为L。

• 每个分支结点贡献k条出边，总边数 = n·k。
• 树中边数 = 总结点数 - 1，总结点数 = n + L。
• 所以：n·k = (n + L) - 1。
• 移项：L = n·k + 1 - n = (k - 1)n + 1。

这就是答案D。

避坑提醒

• 别把‘边数=结点数-1'记成‘边数=结点数+1'，那样会直接算出nk+1（选项A）。
• 别把分支结点数n当成叶结点数去代入，那样会得到nk-1（选项B）。
• 别把系数搞反成k+1，那样会算出(k+1)n-1（选项C）。
• 特殊值检验：k=2时公式给出n+1，符合二叉树性质；n=1时给出k，也符合只有一个分支结点的情况。

考频与趋势

二叉树基础是树形结构的入门，题库共考过220题，覆盖8个考试级别（2008-2026）。逐年分布：2008年2题、2009年2题、2010年4题、2011年3题、2012年1题、2013年3题、2014年1题、2015年4题、2016年3题、2019年3题、2020年1题、2021年4题、2022年2题、2023年20题、2024年60题、2025年67题、2026年28题、null年12题。分赛事：GESP六级100题、GESP七级56题、GESP八级19题、NOIP普及组初赛14题、NOIP提高组初赛9题、CSP提高级8题、CSP入门级8题、GESP五级6题。可见二叉树相关概念在近年（2023-2026）考频显著上升，尤其是2024年和2025年分别达到60题和67题，说明这类基础题型仍是高频考点。

预测

基于给定数据，二叉树基础在2023-2026年考频持续走高，未来仍可能保持较高频率出现，尤其在NOIP提高组初赛和CSP相关考试中。暂无足够依据预测具体年份或题型变化，但可以肯定：只要树的基本性质（边与结点关系、满k叉树定义）掌握扎实，这类题目就不会再成为拦路虎。