题目

如果一棵非空 k（k ≥ 2）叉树 T 中每个非叶结点都有 k 个孩子，则称 T 为正则 k 叉树。请回答下列问题并给出推导过程。

(1) 若 T 有 m 个非叶结点，则 T 中的叶结点有多少个？

(2) 若 T 的高度为 h（单结点的树 h = 1），则 T 的结点数最多为多少个？最少为多少个？

解析

(1) 叶结点数

答案：。

推导——用「孩子总数 = 非根结点总数」这条关系：

• T 中每个非叶结点都有 个孩子，共 个非叶 → 孩子总数 = ；
• T 中除根以外的每个结点都恰好是某个非叶结点的孩子（一对一）→ 非根结点总数 = ；
• 设叶结点数为 ，则 T 的总结点数 = ，其中除根以外有 个非根结点。

因此

验证：k=2、m=3 的满二叉树，L = 3×1+1 = 4 ✓。

(2) 高度为 h 时结点数的极值

答案：最多 ；最少 。

最多——满 k 叉树（每层都填满）：

每层结点数 ，求和：

最少——每层只有 1 个非叶（"瘦削"的正则 k 叉树）：

正则 k 叉树要求"每个非叶都恰好 k 个孩子"，不能少。所以从根开始一路向下：

• 第 1 层：1 个根；
• 第 2 层：根的 k 个孩子（其中 1 个是非叶，其余 k−1 个是叶）；
• 第 3 层：上一层那 1 个非叶的 k 个孩子；
• ……
• 第 h 层：上一层那 1 个非叶的 k 个孩子（全是叶）。

第 1 层 1 个，第 2..h 层各 k 个，共 层有 k 个：

验证：

• h=1：单结点， ✓；
• h=2、k=2：（一个根 + 两个叶），，相等 ✓（高 2 的正则二叉树只能是这一种）；
• h=3、k=2：，。

编者注（生僻术语）：「正则 k 叉树（regular k-ary tree）」是"每个非叶都恰有 k 个孩子"的树。区分易混术语：满 k 叉树额外要求"所有叶子在同一层"——满 k 叉树一定正则，反之不然。本题叶数公式 在正则 k 叉树就够用，对满 k 叉树自然也对。