我要招人

去企业版

首页 > 试题广场 >

一个完全二叉树有870个节点其叶子节点个数为 [$##$]

[填空题]

一个完全二叉树有870个节点其叶子节点个数为 1

查看答案及解析

张学冇

直接除以2 再向上取整不就完事了

发表于 2019-09-02 14:18:32 回复(0)

百度内推官_Flyer

因为深度为k的二叉树至多有2^k-1个结点，可得该二叉树的结点数量在(2^9-1, 2^10-1)之间，所以可以推断该完全二叉树的深度为10，其结点的数量为：深度为9的满二叉树结点数量 + 第10层叶子的数量leaf_count：

可得：leaf_count + (2^9 - 1) = 870，得 x = 359

编辑于 2019-05-18 22:24:51 回复(2)

NAFU

设n0表示叶子节点数（没有孩子）， n1表示只有一个孩子的节点数，n2表示有两个孩子的节点数

有：n2 + n1 + n0 = 870

2 * n2 + n1 = 870 - 1

由完全二叉树的定义n1 = 0 或 n1 = 1，

n1 = 0 无解；n1=1，得n0=435

编辑于 2020-07-20 15:51:03 回复(0)

老苦瓜

加一或者不加，反正先变成偶数，然后除二即可。原因，先算出所有空指针，然后除以二即可

发表于 2019-09-10 17:34:33 回复(0)

summerrr

设度为2的节点数为n，则叶子节点数为n+1，又因为是完全二叉树，且总结点为偶数，则必然且只存在一个度为1的节点

2n+1+1=870 n=434。。。。。。。。。。。。。。。这样为什么不对

发表于 2019-05-07 10:42:33 回复(2)

JosephChen

参考答案错了，为了避免后来者被误导，我特意写一遍详细的解析：

答案：435

解析：（一种比较笨的解法）

1层满二叉树节点数=2^1-1；

2层满 2^2-1;

...

9层满 2^9-1=511

10 1023

所以870个节点是一个10层的完全二叉树，且它的

第十层有870-511=359个叶子节点；

第九层有256个节点

其中180个节点有孩子节点（下一层的359个叶子）

剩下256-180=76个节点

总计：76+359=435各节点

发表于 2019-06-26 21:55:06 回复(3)

仙女培

435

发表于 2020-03-27 21:25:00 回复(0)

千_百度

答案应该是435，n = n0 + n1 +n2 ，n0 = n2+1，　所以n = 2*n2 + n1 + 1 = 870。根据完全二叉树的性质，度为1的节点个数要么为１要么为０，由n = 2*n2 + n1 + 1 = 870得，n1是奇数，所以n1 = 1。那么把n1 = 1 代入得　n2 = 434。n1 = 434 +1 = 435。

发表于 2020-01-19 22:16:20 回复(0)

Nearme

结点有偶数个说明存在度为1的结点，这里可以先假设总结点数多了1个，此时总结点数为871，不存在度为1的结点，设原先叶子结点数为n，则现有（n+1）个叶子结点，度为2的结点数依然是n，有：(n+1)+n=871

发表于 2019-11-07 20:33:40 回复(0)

你电瓶车

435。

1。计算层数

2的10次方-1=1023,2的9次方-1=511.推断是9层。

2.第9层有多少个根。假设x.

870=511+2x或者870=511+2x-1（最后一个只有一个子节点），计算x=180。

3.叶子个数为第9层没有根的节点加第10层的节点。

256-180+180*2-1=435.

发表于 2019-07-13 21:48:46 回复(0)

提交观点

问题信息

C++工程师 iOS工程师安卓工程师运维工程师前端工程师算法工程师哔哩哔哩树测试工程师 2019 Java工程师

来自：哔哩哔哩2019秋招技...

上传者：小小

难度：

10条回答 36收藏 2809浏览

一个完全二叉树有870个节点其叶子节点个数为 [$##$]

问题信息

热门推荐

相关试题

一个完全二叉树有870个节点 其叶子节点个数为 [$##$]

问题信息

热门推荐

相关试题

一个完全二叉树有870个节点其叶子节点个数为 [$##$]