首页 > 试题广场 >

一个完全二叉树节点数为200，则其叶子结点个数为？

[单选题]
一个完全二叉树节点数为200，则其叶子结点个数为？ 
  • 98
  • 99
  • 100
  • 101
查看正确选项
添加回答
神思者之梦头像 神思者之梦
7层满二叉树有 2的7次方-1=127个节点。
8层满二叉树有 2的8次方-1=255个节点。
因此200个节点树有8层，前7层是满的。

第i层有2的(i-1)次方个节点，
因此第7层有64个节点，
第8层有 200-127=73个节点(均为叶子节点)
第七层中有孩子的节点则为73/2向上取整37个节点(度为2或1)
第七层的叶子节点数为64-37=27个

叶子节点一共有73+27=100个
-------------------------------------------------------------------------------------------------------------------------
网上查到的另一种解法： 
完全二叉树除最后一层，其他层都是满结点的。
所以这里总结点200个，这里是偶数，可以判断度为1的结点是1个。
根据二叉树性质n0 = n2 + 1;叶子结点数量等于度为2的结点数+1
n0 + n1 + n2 = 200 
n0 + n1 + n0 -1 =200;
2n0 = 201-n1 = 200  （完全二叉树度为1的结点个数要么1，要么0. 叶子结点数为整数，这里也可以推断出度为1的结点个数是1）
n0 = 100 叶子结点数是100.

编辑于 2018-06-01 15:15:21 回复(2)
hey,20180424头像 hey,20180424

这个考查完全二叉树的特点 就是每行的节点数如果完整 都是2的整数次方

比如 1 2 4 8 16 32 64 128 所以要看到哪一层之前的节点数之和小于且最靠近200

1+2+4+8+16+32+64=127 也就是说 最后一层的叶子节点有 200-127=73个

那么上一层的叶子节点有多少个？

最后一层的叶子节点73用了上一层的73/2+1=37个，因为单独的那个叶子节点的父节点已经不是叶子了，被占用了。所以上一层只剩下64-37=27个

27+73=100个

发表于 2018-10-13 22:18:01 回复(0)
CET-6头像 CET-6
2^6 = 64
2^7 = 128 = 2^6+2^5+2^4+2^3+2^2+2^1+2^0 + 1
2^8 = 256 
200 节点表示 树有 7 层，前 6 层是满的 有64个节点，第 7 层有 72个节点
72 + （64 - 72/2）= 100
发表于 2018-05-31 22:06:52 回复(0)
ζั͡އ๓尐星繁♪头像 ζั͡އ๓尐星繁♪
完全二叉树，叶子结点数n/2向上取整
发表于 2018-06-01 16:00:18 回复(0)
莫俭铭头像 莫俭铭

n = n0 + n1 + n2    ①

n - 1 = 0*n0 + 1*n1 + 2*n2   ②

①代入②得：n0 = n2 + 1       ③

③代入①得：(n-1-n1)/2 = n2 ④

∴④代入③得：n0 = (n-1-n1)/2 + 1 ⑤

又因为完全二叉树的性质，n1只能是1或者0

③代入①得：n = 2n2 + n1 + 1

 

当n1 = 1时，节点数必为偶数

当n1 = 0时，节点数必为奇数

∴n0 = [n-1-(n+1)%2]/2 + 1 //已知节点数求叶子结点数

编辑于 2021-03-10 13:43:21 回复(0)
AnimateDeng头像 AnimateDeng
// Answer: 100
/* 解析 */
首先，回顾一下二叉树的几个性质：
1. 在二叉树的第 i 层至多有 2^(i - 1)个结点 (i>=1)。
2. 深度为 k 的二叉树至多有 2^k - 1个结点 (k>=1)。
3. 对任何一棵二叉树 T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则 n0＝n2＋1。
4. 具有 n (n>=0) 个结点的完全二叉树的深度为log2^n ＋1 
5. 如将一棵有n个结点的完全二叉树自顶向下，同层自左向右连续为结点编号0,1, …, n-1，则有： 
    1）若i = 0, 则 i 无双亲, 若i > 0, 则 i 的双亲为：(i - 1) / 2
    2）若2*i+1 < n, 则i 的左子女为 2*i+1，若2*i+2 < n, 则 i 的右子女为2*i+2
    3）若结点编号i为偶数，且i != 0,则左兄弟结点i-1.
    4）若结点编号i为奇数，且i != n-1,则右兄弟结点为i+1.
    5）结点 i 所在层次为: log2^(i+1)

第7层共有 2^6 = 64 节点
第8层共有 200 - 2^7 + 1 = 73 节点
所以第7层有非叶子节点 73 / 2 = 37（向上取整） 节点
故共有叶子节点 64-37+73 = 100
发表于 2018-09-08 10:24:30 回复(0)
Mr-WangXZ头像 Mr-WangXZ
发表于 2018-07-20 13:37:46 回复(0)
提交观点

问题信息

C++工程师 网易 2018
上传者：小小
难度：
7条回答 11553浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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