NOIP 普及组初赛 · NOIP 2013 普及组初赛试题 第 9 题

已知一棵二叉树有 $10$ 个节点，则其中至多有（ ）个节点有 $2$ 个子节点。

这题核心就是利用二叉树里双孩节点和叶子节点的固定关系。拿到10个节点，先想满二叉树的结构：双孩节点越多，叶子就越少。直接套用公式 n = 2x + 1，把10代进去算x的最大整数值，就能秒杀答案。

学生最容易犯两个错：一是死记硬背公式但记反了，以为叶子数等于双孩节点数，或者把公式写成 n = x + 1，导致算出5个；二是没考虑到节点总数是固定的，只想着“尽量多”，结果在满二叉树基础上硬加节点，误以为可以再加一个双孩节点凑够10个，其实加进去的那个节点只能当单孩或者叶子，根本撑不起新的双孩结构。

这道题考查的是二叉树中节点度与数量的关系，属于数据结构基础里的必考概念。命题人特别喜欢拿具体的节点数（比如10个）来挖坑，让你去推最大可能的双孩节点数，而不是问你最小值或者平均值。

拿到这种题，思考心法很简单：先想极端情况。要让有2个子节点的节点最多，那这棵树就得尽可能“丰满”，也就是接近满二叉树。在满二叉树里，所有非叶子节点都有2个孩子，叶子节点都在最底层。

这里有个关键概念必须搞清楚：在二叉树中，叶子节点数（度为0）等于度为2的节点数加1。设度为2的节点数为x，那么叶子数就是x+1。整棵树的节点总数n就等于：度为2的节点数 + 度为1的节点数 + 度为0的节点数。为了让x最大，我们得让度为1的节点数为0（因为度为1的节点既消耗了父节点名额，又没贡献两个孩子，纯属“浪费”）。这样树就是满二叉树结构。

于是公式就出来了：n = x + 0 + (x + 1) = 2x + 1。

现在代入题目给的n=10：10 = 2x + 1，解得2x = 9，x = 4.5。因为节点数必须是整数，所以x最大只能取4。

验证一下：如果有4个双孩节点，根据公式叶子数=4+1=5。总节点数=4（双孩）+5（叶子）=9。哎，还差1个节点。这剩下的1个节点放哪？只能挂在某个双孩节点下面，把它变成度为1的节点，或者单独挂成度为1的节点。一旦有了度为1的节点，原来的平衡就被打破了，叶子数还是等于双孩节点数加1，总节点数变成2x+1+1=2x+2。这时候x还是4，总节点数变成10，但双孩节点数没变。所以增加那个节点并不能增加双孩节点的数量。

易错点提醒：很多学生会算出4.5然后四舍五入成5，或者觉得“满二叉树7个双孩节点”（那是15个节点的情况），混淆了层数和节点数。还有的学生会误以为公式是n = 2x，忘了加1，导致算出5。记住，叶子数永远比双孩节点数多1，这是二叉树的铁律。

关于考频与趋势：二叉树基础在题库里共考过220题，覆盖8个考试级别。从逐年分布看，2023年考了20题，2024年飙升到60题，2025年更是达到了67题，2026年也有28题，说明这类基础概念题依然是高频考点，命题人非常看重学生对二叉树基本性质的掌握。分赛事来看，GESP六级考了100题，七级56题，八级19题，NOIP普及组初赛14题，NOIP提高组初赛9题。可以看出，GESP六级和NOIP普及组初赛是二叉树考点的重灾区，而提高组初赛相对少一些，可能更偏向复杂操作或应用。

预测未来：基于2023-2026年连续四年的高频数据（20, 60, 67, 28），二叉树基础概念题在未来几年依然会是必考内容，尤其是满二叉树、完全二叉树的性质计算。命题人可能会继续用类似的“给定节点数求最大/最小双孩节点数”或“给定叶子数求节点总数”这种形式来考查，难度不会太大，但会反复出现，要求考生必须熟练掌握那个2x+1的关系式，不能只靠死记硬背。

综上，这道题答案就是A（4）。