我要招人

去企业版

首页 > 试题广场 >

一个完全二叉树有770个节点，那么其叶子的个数为？

[填空题]

一个完全二叉树有770个节点，那么其叶子的个数为1个

推荐

香蕉牛奶

385

解释：

度为2的节点 = 度为0的节点 - 1

度为0的节点就是叶子节点

总结点数 = 度为0节点 + 度为1节点 + 度为2节点

完全二叉树度为1的节点有1个

所以：总结点数 = 度为0节点 + 1 + 度为0节点 - 1

所以：总结点数 = 叶子 * 2

叶子 = 770/2 = 385

编辑于 2015-02-09 17:21:04 回复(6)

编号2015

385

2^k-1<=770

k = 9(该二叉树的高度为k)

770-(2^9-1)=259（表示第k层有259个结点，PS：当时我算出来为159，小学数学没学好）

259/2 + 1 = 130（对应的第k-1层的130个父结点）

2^(k-1)-130 = 126(第k-1层总共有2^8=256个结点，减去非叶子结点130,得到第k-1的叶子结点)

总共叶子结点个数为259+126=385个

发表于 2015-02-02 11:02:38 回复(6)

crazychen

当n为偶数时，n1=1
又有n0=n2+1
所以2n0-1=n-1
解得n0=385

发表于 2015-04-02 18:15:06 回复(0)

lyq12

做大疆的机试题时总结出来的规律：一个完全二叉树的节点个数为整数N（不管N多么大），其叶子节点的个数均为[（N+1 ）/2]取整。

编辑于 2016-09-23 18:38:33 回复(0)

﹏雨煕〆

叶子结点分为最后一层的叶子结点，以及上一层的叶子结点。 1，最后一层的叶子结点:总共有770个结点，2^x-1<=770，x=9，，2^9-1=511，最后一层叶子结点个数为770-511=259 2，上一层的叶子节点:259/2=130，最后一层的叶子节点占用上一层130个父节点，上一层总共有2^(9-1)=256个结点，所以剩下256-130=126个叶子节点总共有259+126=385个叶子节点

发表于 2018-03-13 09:42:43 回复(0)

求一个大大的offer

770/2 乡下取整就是最后一个分支节点的序号。所以770/2 取整是385 770-385=385.

发表于 2015-01-13 22:54:53 回复(3)

求求求offerofferoffer

（2^n-1）=770，故n=10.所以最大深度为10,

深度为9，总叶子结点数为2^9-1=511，故深度为10的这一层，叶子结点数为770-511=259,

深度为9的这一层，叶子结点数为2^8=256,

259-256=3，每个结点产生两个分支，2^2=4>3故第9层有128-2=126个节点没有产生分支

故叶子结点有259+126=385

发表于 2018-09-20 10:35:52 回复(0)

126M

总共有770个节点(偶数个)说明最后一个节点为其父节点的左孩子(右孩子编号为奇数)，因此这棵完全二叉树度为1的节点只有一个，而度为0的节点为度为2节点个数加上1

发表于 2017-05-24 19:51:32 回复(0)

yachu15

树的性质
1、树中的节点数等于所有节点的度数加1.
2、度为m的数中第i层最多有m^(i-1)个节点（i≥1）。
3、高度为h的m次树至多有(m^h-1)/(m-1)个节点。
4、具有n个节点的m次树的最小高度为⌈log_m⁡(n(m-1)+1)⌉
解法一
用性质1求解该题
n=n0+n1+n2 ①
n=n1+2n2+1 ②
由以上二式可得n2=n0-1 ③
将式③代入①或②，770=2n0+n1-1
根据完全二叉树性质度为1的节点为1或0个,此处n1应为1，得n0=385
解法二
根据性质4
h=⌈log_m⁡(n(m-1)+1)⌉=10
根据性质3
770-(2^9-1)/1=259 得到高为10完全二叉树节点个数为259
这些树有⌈259/2⌉个父节点（非叶子节点）得130
根据性质2
第9层剩余节点为叶子节点2^8-130 得126
叶子结点数为第10层节点数+第9层叶子节点数259+126 得385
参考该题下部分参考答案，以及李春葆数据结构。

发表于 2016-12-31 02:29:35 回复(0)

coder_

2¹⁰-1=1024-1=1023>770；2⁹-1=512-1=511.

所以第10层满节点共有2⁹=512，有770-511=259个叶子节点。占用第9层130个节点。

叶子节点个数为：259+（2⁸-130）=259+（256-130）=385

发表于 2015-09-30 09:24:14 回复(0)

已注销

n 为奇数时，n = n0 + n2 ；

n 为偶数时，n = n0 + n2+ 1 。

-------------------------------------------------

n2 = n0 - 1;

2 * n0 - 1 = 770 -1;

n0 = 385。

发表于 2021-10-04 15:05:55 回复(0)

向宇の保温杯

方法一：

2⁹-1<770<2¹⁰-1

共10层

9层共有节点512-1=511，

第十层的叶子节点：770-（511）=259

第九层的父子节点：258/2+1=130

第九层的总节点：2^9-1=2⁸=256

第九层的叶子节点：256 -130 = 126

总叶子节点：第十层叶子节点+第九层叶子节点 = 259 + 126 = 385

*********************************************************************************

方法二：

完全二叉树

n1=1（偶数个节点）、0（奇数个节点）

n0 = n2 + 1

n = n0 + n1 + n2

770 = n0 + 1 + n0 - 1

770 = 2n0

n0 = 770/2 = 385

发表于 2017-09-18 16:17:19 回复(0)

wanlanwalan

n/2=770/2=385

发表于 2017-08-24 16:34:53 回复(0)

sunlight_run

解题要点：

1.完全二叉树n1为0或者1

2.n0=n2+1

3.n0+n1+n2=770

解得答案为385

发表于 2017-06-28 10:18:24 回复(0)

ZJ_Lavender

首先对于二叉树只有三种节点：度为2，度为1和度为0的叶子节点。那么完全二叉树更为特殊，度为1的节点只有两种情况：要么没有要么一个。二叉树中度为二的节点一定是比度为1的节点少一个。所以有n0-n2等于1；n1等于0或者1。n0+n1+n2等于770也就是2*n0+n1-1等于770 2n0是偶数，770是偶数，所以n1等于1。n0等于385。也就是叶子节点的个数

发表于 2016-11-20 15:12:18 回复(0)

kareni

！！！！！770除以2都算错了。。。。我可以去死了

发表于 2016-09-25 13:04:45 回复(0)

尐短腿

总节点数若为奇数则无度为1的节点。若为偶数只有一个度为1的节点、、、利用边加一等于总节点数。很好求啦、、

发表于 2016-06-02 09:59:03 回复(0)

huixieqingchun

叶子结点只可能在最后一层或者倒数第二层。

发表于 2016-05-07 21:53:09 回复(0)

小虎牙

答案：385

遇到这种类型的题目，只要是完全二叉树，那么其叶子节点的个数就为总结点的个数的一半，770/2=385

发表于 2016-01-08 10:01:50 回复(0)

yang.li

最快的方法是：共有770个节点因为是满二叉树因此满足父节点为i/2 向下取整

这个是满二叉树的性质

然后可以得到最后一个叶子节点的父亲编号为385

编号770之后没有节点了

可以确定编号385是最后一个父亲节点

因此编号385之后的全部是叶子节点

所有就有了770/2=385

发表于 2015-09-04 18:56:20 回复(1)

恬一点

385=（256-130）+（770-512-1）完全二叉树从满二叉树引申出来：若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

发表于 2014-10-25 00:26:03 回复(2)

提交观点

问题信息

C++工程师小米集团树 2014 Java工程师

来自：小米2014校招研发工...

难度：

25条回答 252收藏 15584浏览

一个完全二叉树有770个节点，那么其叶子的个数为？

问题信息

热门推荐

相关试题