NOIP 提高 2018 第一轮 第 12 题：2-3树是一种特殊的树，它满足两个条件：

题目

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

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

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

答案

C、D

题解

考点定位

本题考「2-3 树结构计数（不定项）」,对应大纲 3.2.2 平衡树（难度【5】）。

解题过程

2-3 树：内部结点 2 或 3 个孩子、所有叶同深。设叶 L=10，自底向上：内部结点数取决于 2/3 度结点组合。穷举满足同深的结构：非叶结点可能 7 或 8 个（不同分层组合）。

答案：C、D。

易错提醒

① 自底向上逐层分配：底层叶 10 个，父层结点数 = ⌈10/3⌉..⌊10/2⌋=4..5，逐层累加；② 每层分配方案独立 ⇒ 多种非叶总数。