第 42 题
如果一棵非空k（k≥2） 叉树T中每个非叶结点都有k个孩子，则称T为正则k叉树。请回答下列问题并给出推导过程。
(1) 若T有m个非叶结点，则T中的叶结点有多少个？
(2) 若T的高度为h（单结点的树h=1），则T的结点数最多为多少个？最少为多少个？
1）根据定义，正则k叉树中仅含有两类结点；叶结点（个数记为n0）和度为k的分支结点（个数记为n1）。树T中的结点总数n=n0+nk=n0+m。树中所含的边数e=n−1，这些边均为m个度为k的结点发出的，即e=mk。整理得n0+m=mk+1，故n0=(k−1)m+1。
2）高度为h的正则k叉树T中，含最多结点的树形为：除第h层外，第1层到第h−1层的结点都是度为k的分支结点；而第h层均为叶结点，即树是“满”树。此时第j（1≤j≤h）层结点数为kj−1，结点总数M1为M1=i=0∑hkj−1=k−1kh−1含最少结点的正则K叉树的树形为：第1层只有根结点，第2层到第h−1层仅含1个分支结点和k−1个叶结点，第h层有K个叶结点。即除根外第2层到第h层中每层的结点数均为k，故T中所含结点总数M2为M2=1+(h−1)k【评分说明】①
[tag_link]
参考答案仅给出一种推导过程，若考生采用其他推导方法且正确，同样给分。②若考生仅给出结果，但没有推导过程，则 (1)、(2) 的最高得分分别是 2 分和 3 分。若推导过程或答案不完全正确，酌情给分。