Question

数据结构与算法 2-3树是一种特殊的树，它满足两个条件

2-3树是一种特殊的树，它满足两个条件
（1）每个内部结点有两个或三个子结点；（2）所有的叶结点到根的路径长度相同；
如果一棵2-3树有9个叶结点，那么它可能有_________个非叶结点。 (多项)

Answer 1

设 h 为树的高度，也就是根到叶子的边数。
如果所有内部结点都有 2 个子结点，那么叶子数是：2^h
如果所有内部结点都有 3 个子结点，那么叶子数是：3^h
现在有 9 个叶子，也就是：2^h <= 9 <= 3^h
所以：h=3 或 2

当 h=2 时，所有的内部结点都有 3 个子结点。
每层的结点数分别为：1、3、9。所以内部结点数是：1+3 = 4

当 h=3 时，叶子数是 9，比所有内部结点都有 2 个子结点（满二叉树）的多了 1 个。
满二叉树每层的结点数是：1、2、4、8
满二叉树每层的结点数，是任意 2-3 树每层结点的最小数目。
设我们 9 个叶结点的 2-3 树每层结点数为：1、a、b、9
显然，b <= 4，否则就有一个结点的子结点数 <=1 了。
所以，b = 4，因为满二叉树规定了第 2 层最小结点数是：2^2 = 4。
同理，a <= 2，否则又会有一个结点的子结点数 <=1。
所以，a = 2，因为满二叉树规定了第 1 层最小结点数是：2^1 = 2。
所以我们 9 个叶结点的 2-3 数每层结点数为：1、2、4、9
所以内部结点数是：1+2+4 = 7

所以答案是：4 或 7

Answer 2

应该是4到7个。

Answer 3

简单。晚上高速你，现在忙。