首页 > 试题广场 > 一个完全二叉树节点数为200,则其叶子结点个数为?
[单选题]
一个完全二叉树节点数为200,则其叶子结点个数为?
  • 98
  • 99
  • 100
  • 101
完全二叉树,叶子结点数n/2向上取整
发表于 2018-06-01 16:00:18 回复(0)
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)

这个考查完全二叉树的特点 就是每行的节点数如果完整 都是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)
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)
// 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)
发表于 2018-07-20 13:37:46 回复(0)