首页 > 试题广场 >

一个包含 n 个分支结点(非叶结点)的非空满 k 叉树,k

[单选题]
一个包含 n 个分支结点(非叶结点)的非空满 k 叉树,k>=1,它的叶结点数目为:
  • nk + 1
  • nk-1
  • (k+1)n-1
  • (k-1)n+1

其实尝试 的情况后,会发现无论 等于几答案都是 ,那么只有 选项满足

发表于 2019-10-18 16:24:20 回复(0)
设非空满k叉树有m层,那么一共应该有:1+k+k2+ · · ·  +km-1个结点,即(km-1)/(k-1)个结点,其中n个是分支结点。
那么最外层的结点个数(叶子结点)应该满足:
(km-1)/(k-1)-n = km-1
解得:n =(km-1-1)/(k-1)
带入解得:km-1 = n(k-1)+1;
即 非空 满 k叉树叶子结点数:n(k-1)+1
发表于 2020-11-22 09:37:59 回复(0)