首页 > 试题广场 >

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

[单选题]
一个完全二叉树节点数为200,则其叶子结点个数为?
  • 98
  • 99
  • 100
  • 101
首先大致计算出这完全二叉树一共有几层,由于其的节点数是200,其在127和255之前,也就是2^7-1和2^8-1之间,叶子节点有两部分,一部分是第8层暴露出来了,一部分是第7层没有子节点的那一部分,暴露出来的是200-127=73个,而73个节点从(73+1)/2=37个节点引出来的,那么第7层剩下的节点是2^(7-1)=64,那么7层剩下的叶子节点是64-37=27 
27 + 73 = 100
发表于 2018-06-22 21:13:10 回复(1)

完全二叉树:
如果二叉树的深度为k,则除第k层外其余所有层节点的度都为2,且叶子节点从左到右依次存在。也即是,将满二叉树的最后一层从左到右依次删除若干节点就得到完全二叉树。满二叉树是一棵特殊的完全二叉树,但完全二叉树不一定是满二叉树。

假设一个二叉树有n个节点:

度为0的节点个数是n0
度为1的节点个数是n1
度为2的节点个数是n2

则有如下公式成立:

n0 = n2 + 1      (1)
n0 = (n +1) / 2  (2)(完全二叉树)

n = n0 + n1 +n2
因为 n0 = n2 + 1
所以 n = 2 * n0 + n1 - 1

因为是完全二叉树,所以 n1 只能等于0或1
所以 n = 2 n0 - 1 或 n = 2 n0
也就是n0 = (n + 1) / 2

发表于 2018-06-22 17:32:57 回复(0)
最后一层是73个,占用了上一层64个中的37个,上一层剩下27个,最后27+73
发表于 2019-08-02 19:17:36 回复(0)