NOIP 提高组初赛 · NOIP 2018 提高组初赛试题 第 12 题

2-3 树是一种特殊的树，它满足两个条件：

1. 每个内部结点有两个或三个子结点； 2. 所有的叶结点到根的路径长度相同。

如果一棵 2-3 树有 $10$ 个叶结点，那么它可能有（ ）个非叶结点。

拿到题先别急着套公式，想想2-3树的性质：每层结点数是上一层的2~3倍。10个叶子，它的父结点层最多只能有5个（5×2=10），最少4个（4×3=12，但4个父结点带3个孩子就是12个叶子，带2个孩子就是8个，所以4个父结点只能带10个叶子吗？不对，4个父结点，每个带2.5个孩子？不可能。重新想：父结点层结点数设为k，则k×2≤10≤k×3，解得k只能是4或5。这就是突破口。

最容易栽跟头的地方是层数判断。很多学生看到10个叶子就以为树高是4层（因为2^3=8, 3^3=27，觉得叶子在第4层），然后算非叶结点时把根、第二层、第三层都算进去，结果多算了一层或者少算了一层。还有的学生直接用10除以2.5这种平均数去倒推父结点数，忽略了2-3树每个内部结点孩子数是整数这个硬性约束，导致算出非整数个父结点，最后强行凑选项，完全偏离了树的实际结构。

考点概念：2-3 树结构

2-3 树是一种平衡树，核心就两点：一是每个内部结点要么生2个孩子，要么生3个孩子；二是所有叶子结点都在同一层，树的高度是固定的。

命题视角：为什么考这个？

命题人想考的其实就是你对“层数与结点数倍数关系”的敏感度。2-3 树的叶子数范围很紧：如果树高是 h（根在第 1 层，叶子在第 h 层），那么叶子数最少是 2^{h-1}，最多是 3^{h-1}。题目给 10 个叶子，就是要你判断这 10 个叶子到底在哪一层。