首页 > 试题广场 >

完全二叉树共有700结点，该二叉树有多少个叶子结点？

[单选题]
完全二叉树共有700结点，该二叉树有多少个叶子结点？ 
  • 349
  • 350
  • 351
  • 352
  • 353
添加回答
推荐
码农13头像 码农13
                                                               1
                                  2                                                    3
                      4                   5                                  6                  7
                 8        9      10           11               12
因为12/2等于6,等于父节点值，所以是最后一个带子节点的，拿总数减去6，即为叶子节点数，同理，所以700作为最后一个节点，他的父节点是350，所以序号350是最后一个非叶子节点，以下的都没有子节点，700-350 = 350 所以答案选B
编辑于 2015-09-04 09:35:46 回复(6)
稻草阳光头像 稻草阳光
其实涉及完全二叉树的叶子结点和非叶子结点个数这一类题，只用记住一个公式即可：
（结点总个数-2）/2即是最后一个非叶子结点，也就是说它之前的结点都是非叶子结点，它后面的结点都是叶子结点。
这是根据完全二叉树的性质推导出来的，这里就不赘述。
发表于 2016-07-27 22:18:11 回复(0)
Arison头像 Arison
B，就是用完全二叉树的性质 n2=n0-1, 而度为1的有一个或没有 。700个结点的话 2n0-1 +n1=700,n1肯定为1 ，要不然左边肯定不是偶数。所以n0=350.
发表于 2015-09-04 19:10:01 回复(1)
二货磁铁头像 二货磁铁
选择B 350，首先根据完全二叉树的定义，通过满二叉树计算得到该完全二叉树的深度n=10.
易得到第9层的节点个数为256，深度为9的满二叉树节点个数为511.
由700-511=189得到该完全二叉树第10层节点个数为189，对189除2得到94余1，可以知道第10层已经填满了第9层的94个节点，并在第95个节点下有一个左孩子。那么第9层贡献的叶子节点个数为256-95.
结果为res=256-95+189=350，即B选项
发表于 2015-09-04 03:37:32 回复(5)
icebreaker头像 icebreaker
答案：B
        叶子结点：度为0的结点就是叶子结点。最后一个结点为700，然后可以得到它的父节点是700/2=350，记为pointer，从这个pointer开始到最后一个结点所有结点都是叶子。所以700-350=350。
发表于 2015-09-04 15:13:17 回复(0)
GYshadows头像 GYshadows 
大佬已经各种快速解法已经给出了，这里提供一种计算的方法：
第一步，计算完全二叉树的有多少层：2^9-1<700<2^10-1，因此该完全二叉树有10层;
第二步：计算第10层的叶子节点个数：700-2^9+1=189;
第三步：计算第9层的叶子节点个数：2^8-(189/2向上取整=95）=161；
第四步：计算总共叶子节点个数：189+161=350；
结束。

发表于 2018-08-11 21:32:27 回复(0)
牛牛12315头像 牛牛12315
完全二叉树   它的度为1的结点数(n1) 要么只有1个 要么是0个(这跟它的定义性质有关，因为最后一层结点集中在左边，其它层是满的，所以不可能出现2个或以上的度1结点)  ok   接下来就容易了：
结点数 = n0 + n1 + n2
各结点度数和 = 1 * n1 + 2 * n2
各结点度数和 = 连线数 = 结点数 -1 = 699 =（上式） 所以 n1 (699-2*n2)不是0 只能是1 
故 n0 = 结点数 - n1 - n2 = 350
发表于 2015-09-04 20:22:12 回复(0)
toraoh头像 toraoh
答案：B

思考过程：
正常反应：构造一下这个完全二叉树。
去掉最底下的那些叶子节点，这个树就是满二叉树。
那么这个树，最少删除底层多少个节点以后，变成满二叉树？
n层的满二叉树，节点个数是2^n-1个
背一下2^n的表吧
（前略）,128,256,512,1024（后略）
512-1<700<1024-1
好，现在知道了，最底层还有700-511=189个叶子节点（更高一层的右边也有，等会再说）。
这189个叶子节点，会把由511个点构成的满二叉树中最底下的256个叶子节点中的一部分变成非叶子节点。那么有多少个原来是叶子节点的，在加上189个叶子节点后变成非叶子节点了呢？
（189+1）div 2=95（div表整除）
就是，94个原叶子节点有了2个孩子，1个只新增1个孩子。
所以，最后，700个点的完全二叉树的叶子节点数是：
256（最接近的满二叉树的叶子节点数）-95（其中变成非叶子节点的节点数）+189（还有这些要接在变成非叶子节点下的叶子节点）=350

顺带一提，之前牛客-007说的是：
完全二叉树的叶子节点比非叶子节点多一个
但是，选C就成了叶子节点比非叶子节点多了2个！明显错误！
这句话改改吧：
完全二叉树的叶子节点比非叶子节点多一个，或者一样多。
（大家可以自己草稿纸上画画图，一直满足这个规律的）
编辑于 2015-09-04 00:59:36 回复(0)
鑫空麋鹿头像 鑫空麋鹿
依题意，n=700，由于n为偶数，所以n1=1。又因为n=n0+n1+n2，由性质可得，n2=n0-1，所以n=2n0-1+n1，n0=（n-n1+1）/2=350。所以叶子节点为350个
发表于 2022-04-27 10:51:26 回复(0)
你永远得不到的祖奶奶头像 你永远得不到的祖奶奶
先假设其为满二叉树，有10层，满二叉树中，第九层为256各节点，第十层为512个节点，满二叉树总结点数为1023，完全二叉树为700个节点，不满的节点数为323个不满最后一层，512-323=189个，最后一层有189个叶子结点，189个叶子结点占用第九层父节点95个还剩下256-95=161个叶子结点，所以总的叶子节点为 161+189=350个。
发表于 2020-06-23 09:43:27 回复(0)
笑以头像 笑以
告诉大家一个我在另一题看到的一个解法：偶数时直接为一半，奇数时为一半的向上取整。
发表于 2018-11-24 16:00:28 回复(0)
zzoecode头像 zzoecode
完全二叉树 
度为0的节点（叶节点）个数为n0，度为1节点n1=0或1（完全二叉树特点，区别满二叉树），度为2节点n2
n2=n0-1
n0+n2=700
则n1=1，n0=350
发表于 2015-09-04 20:30:09 回复(0)
XQ头像 XQ
B
完全二叉树
节点数=N0+N1+N2=700 N2=N0-1
2N0+N1=701; N1最多有一个 所以N0=350 
发表于 2015-09-04 11:31:30 回复(0)
蹉跎觉悟的弱者头像 蹉跎觉悟的弱者
我有个简单的解决方法大家看一看哈：
1.二叉树节点个数n=n0+n1+n2；   
 n0=度为0的节点个数，n1=度为1的节点个数，n2=度为2的节点个数
2.二叉树性质n2=n0-1；
3.完全二叉树的性质：n为偶数时n1=0；n为奇数是n1=1；
4.由 1 2  3式得  n=n0+1=n0-1   即  2*n0=n ；本题叶子节点个数直接就算出来   350个
发表于 2024-11-05 19:53:51 回复(0)
有痕头像 有痕
根据非空完全二叉树的特点，当结点总数n为奇数时，n1=0，当结点总数n为偶数时，n1=1。所以n0+n1+n2=700，n2=n0-1，n0+n0–1+1=700，2n0=700，所以n0=350
发表于 2023-04-28 10:03:15 回复(0)
宁静致远green头像 宁静致远green
完全二叉树的叶节点数或者与非叶节点数相等，或者比非叶节点数多1
发表于 2015-09-04 09:26:28 回复(1)
lilcancy头像 lilcancy
由完全二叉树的一个性质，若最后一层的叶子结点的个数为奇数（偶数），则总结点的数量为偶数（奇数），意味着度为1的结点只有1个（0个），故1+n2+n0 = 700；又因为n0 = n2 +1，所以2*n0 = 700；n0 = 350。
发表于 2024-04-10 20:05:24 回复(0)
牛客130365080号头像 牛客130365080号
求完全二叉树的叶子节点公式:n/2 向上取整
发表于 2023-10-14 16:57:18 回复(0)
ninja88888头像 ninja88888
n/2向下取整
发表于 2023-07-26 14:29:43 回复(0)
找呀找呀找工作random头像 找呀找呀找工作random
满二叉树为例，叶＝双子+1 减一个叶，叶-1，双子-1，单子+1，结果为叶-1，非叶不变，叶=非叶。 再减一个叶，叶-1，双子不变，单子-1后转叶，结果，叶不变，非叶-1，也就是叶＝非叶+1。 再减就是重复的过程了。
发表于 2022-09-07 02:22:35 回复(0)
牛客4938kunn头像 牛客4938kunn
选择：B
根据现有结点数算出二叉树层数：[log700+1]做取整运算，为10层，
10层的满二叉树，总共有（2^10-1）=1023个结点，
最后一层结点数位2^(10-1)=512个结点，
1023-700=323个，满二叉树比现在二叉树多323个结点，根据二叉树结构可知，上一层少一个结点，则下一层少两个结点，323/2=161.5，既最后一层最右侧结点的父节点只有左子结点，
满二叉树最后一层 - 上一层少的结点-1（只有左孩子的结点）=512-161-1=350个结点，
关键之处：1.正确计算二叉树层数，2.二叉树少一个父节点，叶子结点实际只少了1个结点。
发表于 2021-01-11 14:54:52 回复(0)
提交观点

问题信息

网易 树
上传者：fordchen
难度：
35条回答 20384浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号