返回主页
[数据结构 P2078] 如果一棵非空 k(k≥2) 叉树 T 中每个非叶结点都有 k 个孩子，则称 T 为正则 k 叉树。请
未通过
如果一棵非空 k(k≥2) 叉树 T 中每个非叶结点都有 k 个孩子，则称 T 为正则 k 叉树。请回答下列问题并给出推导过程。
⑴ 若 T 有 m 个非叶结点，则 T 中的叶结点有多少个？
⑵ 若 T 的高度为 h （单结点的树 h=1 ），则 T 的结点数最多为多少个？最少为多少个？
加入错题本
个人笔记
一棵树中，点数 = 边数 + 1。...
用户登录可进行刷题及查看答案
一棵树中，点数 = 边数 + 1。设度为 i 的结点数量为 ni ，则：
解得：
则 T 中的叶结点有 (k−1)m+1 个。
采用贪心策略。
T 的高度为 h 结点数最多时 T 为一棵满 k 叉树，结点数总计：
T 的高度为 h 结点数最少时，每层（除最下面一层）都只有一个结点有子树。
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案
暂无评论，来抢沙发