首页 > 试题广场 >

一个包含 n 个分支结点（非叶结点）的非空满 k 叉树，k

[单选题]

一个包含 n 个分支结点（非叶结点）的非空满 k 叉树，k>=1，它的叶结点数目为：

查看正确选项

Ameiyo

其实尝试 $k = 1$ 的情况后，会发现无论 $n$ 等于几答案都是 $1$ ，那么只有 $D$ 选项满足

发表于 2019-10-18 16:24:20 回复(0)

欲寄彩笺兼尺素

设非空满k叉树有m层，那么一共应该有：1+k+k²+ · · · +k^m-1个结点，即（k^m-1）/（k-1）个结点，其中n个是分支结点。

那么最外层的结点个数（叶子结点）应该满足：

（k^m-1）/（k-1）-n = k^m-1；

解得：n =（k^m-1-1）/（k-1）

带入解得：k^m-1= n（k-1）+1；

即非空满 k叉树叶子结点数：n（k-1）+1

发表于 2020-11-22 09:37:59 回复(0)

提交观点

问题信息

提高 C++ Pascal OI常识二叉树选择题

来自：NOIP2009初赛普及组

上传者：牛客309901号

难度：

2条回答 1收藏 5639浏览

扫一扫，把题目装进口袋