综合题 如果一棵非空k(k≥2)叉树T中每个非叶结点都有k个孩子,则称T为正则后k树。请回答下列问题并给出推导过程。
问答题     若T有m个非叶结点,则T中的叶结点有多少个?
 
【正确答案】根据定义,正则k叉树中仅含有两类结点:叶结点(个数记为n0)和度为k的分支结点(个数记为nk)。树T中的结点总数n=n0+nk=n0+m。树中所含的边数e=n-1,这些边均为m个度为k的结点发出的,即e=m×k。整理得:n0+m=m×k+1,故n0=(k-1)×m+1。
【答案解析】
问答题     若T的高度为h(单结点的树h=1),则T的结点数最多为多少个?最少为多少个?
 
【正确答案】高度为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
【答案解析】