42.（8分）如果一棵非空k（k>2）叉树T中每个非叶结点都有k个孩子，则称T为正则后k树。请回答下列问题并给出推导过程。 （1）若T有m个非叶结点，则T中的叶结点有多少个? （2）若T的高度为h（单结点的树h=1），则T的结点数最多为多少个?最少为多少个?
【参考答案及解析】
（1）根据定义，正则k叉树中仅含有两类结点∶叶结点（个数记为 no）和度为k的分支结点（个数记为nk）。树T中的结点总数n=no+nk=no+m0。树中所含的边数e=n-1，这些边均为m个度为k的结点发出的，即 e=m×k。整理得∶no+m=m×k+1，故no=（k-1）×m+1。（3分） （2）高度为h的正则k 叉树T中，含最多结点的树形为∶除第h 层外，第1到第h-1层的结点都是度为k的分支结点，而第h层均为叶结点，即树是"满"树。此时第 j（1≤j≤h）层结点数为kj-1，结点总数 M1为： 含最少结点的正则k叉树的树形为∶第1层只有根结点，第 2到第h-1层仅含1个分支结点和k-1个叶结点，第h 层有k个叶结点。即除根外第2到第h层中每层的结点数均为k，故T中所含结点总数M2为∶M2=1+（h-1）×k 【评分说明】M2=1+（h-1）×k（2 分）参考答案仅给出一种推导过程，若考生采用其他推导方法且正确，同样给分。若考生仅给出结果，但没有推导过程，则（1）、（2）的最高得分分别是2分和 3分。若推导过程或答案不完全正确，酌情给分。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！
（1）根据定义，正则k叉树中仅含有两类结点∶叶结点（个数记为 no）和度为k的分支结点（个数记为nk）。树T中的结点总数n=no+nk=no+m0。树中所含的边数e=n-1，这些边均为m个度为k的结点发出的，即 e=m×k。整理得∶no+m=m×k+1，故no=（k-1）×m+1。（3分） （2）高度为h的正则k 叉树T中，含最多结点的树形为∶除第h 层外，第1到第h-1层的结点都是度为k的分支结点，而第h层均为叶结点，即树是"满"树。此时第 j（1≤j≤h）层结点数为kj-1，结点总数 M1为： 含最少结点的正则k叉树的树形为∶第1层只有根结点，第 2到第h-1层仅含1个分支结点和k-1个叶结点，第h 层有k个叶结点。即除根外第2到第h层中每层的结点数均为k，故T中所含结点总数M2为∶M2=1+（h-1）×k 【评分说明】M2=1+（h-1）×k（2 分）参考答案仅给出一种推导过程，若考生采用其他推导方法且正确，同样给分。若考生仅给出结果，但没有推导过程，则（1）、（2）的最高得分分别是2分和 3分。若推导过程或答案不完全正确，酌情给分。
正在整理中,欢迎在文下评论区提供答案解析,谢谢！