首页 > 试题广场 >

若完全二叉树的节点个数为2N-1，则叶节点个数为多少个？

[单选题]
若深度（根节点为1）为N的完全二叉树的节点个数为2N -1，则叶节点个数为多少个？ 
  • N-1
  • 2×N
  • 2的N-1次
  • 2的N次
查看正确选项
添加回答
大闲人柴毛毛头像 大闲人柴毛毛
  1. 完全二叉树的节点为2^n-1说明它是一棵满二叉树，叶子节点全在最后一层；
  2. 又因为，完全二叉树的倒数第二层及以上为满二叉树，所以除了最后一层共有节点2^(n-1)-1；
  3. 那么叶子节点个数为二者之差。
发表于 2017-03-25 10:12:13 回复(0)
lex头像 lex
完全二叉树的节点个数是2 n次方 - 1，则这是满二叉树，深度为n，第n层有2的n-1次方个节点为叶子节点
发表于 2015-09-14 00:15:01 回复(1)
明歌头像 明歌
完全二叉树：除最后一层外，每一层上的 节点 数均达到最大值；在最后一层上只缺少右边的若干 结点 。
二叉树的度 即 结点的分支。用n0,n1,n2分别表示度为0(即叶节点）,度为1和度为2的节点个数。
则 节点总数2^N-1 = n0 + n1 + n2。
由完全二叉树性质知：n0 = n2 + 1;且n1=0 或者n1 = 1;
也即 2^N - 1 = 2*n0 + n1 -1;可知 只有n1=0方有整数解。可解得n0 = 2^(N-1)
发表于 2015-05-28 20:45:58 回复(0)
InGodWeTrust头像 InGodWeTrust
由题知此完全二叉树为满二叉树，满二叉树叶子节点为2的N-1方
发表于 2017-04-09 16:02:07 回复(0)
太平婆婆头像 太平婆婆
对于一个深度为k的完全二叉树，1~k-1层含有2k-1-1个节点，第k层最多含有2k-1个节点，也就是最多有2k-1个叶节点，完全二叉树最多含有2 k -1个节点。
所以对有2N-1个节点的完全二叉树，有2N-1个叶节点
发表于 2017-01-24 21:05:26 回复(0)
testestest头像 testestest
完全二叉树的个数 为 2n0-1+n1
要想 2n0-1+n1=2N-1 且n0为整数，则n1=0，得出n0=2N-1
发表于 2016-04-07 09:24:24 回复(0)
wyfive头像 wyfive
感觉这种问题的最好方法是直接画图，代入特殊值计算
发表于 2015-09-04 17:57:19 回复(0)
风意头像 风意
C
完全二叉树叶子节点比非叶子节点多一个
(2^N-1+1)/2=2^(N-1)

编辑于 2015-04-07 23:19:10 回复(0)
anicy头像 anicy
既然是完全二叉树，则结点的度要么是0要么是2，叶子结点为第N层，所以叶子结点的个数为：2*N

答案为  B
发表于 2015-01-04 20:08:29 回复(0)
提交观点

问题信息

树 腾讯
上传者：summering
难度：
9条回答 15260浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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