的结点数最多为多少个？最少为多少个？

9:T615f,

1）根据定义，正则 $k$ 叉树中仅含有两类结点；叶结点（个数记为 $n_{0}$ ）和度为 $k$ 的分支结点（个数记为 $n_{1}$ ）。树 $T$ 中的结点总数 $n = n_{0} + n_{k} = n_{0} + m$ 。树中所含的边数 $e = n - 1$ ，这些边均为 $m$ 个度为 $k$ 的结点发出的，即 $e = mk$ 。整理得 $n_{0} + m = m_{k} + 1$ ，故 $n_{0} = (k - 1) m + 1$ 。

2）高度为 $h$ 的正则 $k$ 叉树 $T$ 中，含最多结点的树形为：除第 $h$ 层外，第 $1$ 层到第 $h - 1$ 层的结点都是度为 $k$ 的分支结点；而第 $h$ 层均为叶结点，即树是“满”树。此时第 $j$ （ $1 \leq j \leq h$ ）层结点数为 $k^{j - 1}$ ，结点总数 $M_{1}$ 为

M_{1} = i = 0 \sum h k^{j - 1} = \frac{k ^{h} - 1}{k - 1}

含最少结点的正则 $K$ 叉树的树形为：第 $1$ 层只有根结点，第 $2$ 层到第 $h - 1$ 层仅含 $1$ 个分支结点和 $k - 1$ 个叶结点，第 $h$ 层有 $K$ 个叶结点。即除根外第 $2$ 层到第 $h$ 层中每层的结点数均为 $k$ ，故 $T$ 中所含结点总数 $M_{2}$ 为

M_{2} = 1 + (h - 1) k

【评分说明】①参考答案仅给出一种推导过程，若考生采用其他推导方法且正确，同样给分。

2016 年 408 数据结构 · 第 42 题