数据结构
2016-42
如果一棵非空 k（k≥2）叉树 T 中每个非叶结点都有 k 个孩子，则称 T 为正则 k 叉树。请回答下列问题并给出推导过程。
（1）若 T 有 m 个非叶结点，则 T 中的叶结点有多少个？
（2）若 T 的高度为 h（单结点的树 h = 1），则 T 的结点数最多为多少个？最少为多少个？
答案
(1) 叶结点数为 (k-1)m+1。
(2) 最多结点数为 ∑j=1hkj-1=(kh-1)/(k-1)；最少结点数为 1+(h-1)k。