首页 > 试题广场 >

设一课完全二叉树共有999个结点，则在该二叉树中的叶节点个数

[单选题]
设一课完全二叉树共有999个结点，则在该二叉树中的叶节点个数是？ 
  • 499
  • 500
  • 501
  • 不唯一
查看正确选项
添加回答
duanhua头像 duanhua
完全二叉树中叶子节点的数目总比不是叶子节点的节点数目多1.
发表于 2015-09-23 17:04:03 回复(0)
陋室头像 陋室
其实完全二叉树有这个性质，最后一个节点/2就得到他的父节点了，而此时的父节点必然是最后一个父节点，也就是说他之后的结点都是叶子节点了所以叶子节点为，999-999/2 = 500.要懂得运用性质，不然题目的完全二叉树是干啥的。
发表于 2015-09-16 21:44:55 回复(11)
smilepoint头像 smilepoint
选500
29-1<999<210-1，所以二叉树有10层，其中前9层有29-1个结点，第十层有999-（29-1）=488个结点，所以第9层的244个结点有孩子结点，12个结点没孩子结点，所以叶结点有488+12=500个
发表于 2015-09-16 21:01:13 回复(1)
七分熟头像 七分熟
n0+n1+n2=999,n2=n0-1,2*n0-1+n1=999,因为为完全二叉树n1只可能为1或者0，若为1，n0不是整数，则只可能为0，求得n0=500
发表于 2015-09-16 09:41:52 回复(5)
牛客823870号头像 牛客823870号

根据二叉树第k层上的节点数 最多有 2 k-1 (k≥1) ； 深度为m的二叉树的节点数最多有 2 m -1;

m=10共10层；

前9层是满二叉树，总的节点数是：511

则第10层的叶子节点数目是：999-511=488

第九层的非叶子节点数目是：488/2=244;

第九层的节点数目是：256

则第九层的叶子节点数目是：256-244=12

则总的叶子节点数目是：12+488=500

发表于 2015-09-16 21:09:28 回复(0)
striving_qi头像 striving_qi
对于完全二叉树，如果总结点数是奇数，则叶结点数是[总结点数/2](向上取整),同时度为1的结点数为0，相反，如果总结点数是偶数，则叶结点数是：总结点数/2,同时度为1的结点数为1
发表于 2017-08-10 09:27:22 回复(0)
是盈也要赢头像 是盈也要赢
根据非空完全二叉树的特点，当结点总数n为奇数时，n1=0，当结点总数n为偶数时，n1=1。所以n0+n2=999，n2=n0-1，2n0=1000，所以n0=500
发表于 2022-05-03 21:04:14 回复(0)
zhaoying头像 zhaoying
来源于百度百科：
如果一棵具有n个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1~n的结点一一对应，这棵二叉树称为完全二叉树。
可以根据公式进行推导，假设n0是度为0的结点总数（即叶子结点数），n1 是度为1的结点总数，n2是度为2的结点总数，由二叉树的性质可知：n0=n2+1，则n= n0+n1+n2（其中n为完全二叉树的结点总数），由上述公式把n2消去得：n= 2n0+n1-1，由于完全二叉树中度为1的结点数只有两种可能0或1，由此得到n0=(n+1)/2或n0=n/2。
总结起来，就是 n0=[n/2]，其中[]表示上取整。可根据完全二叉树的结点总数计算出叶子结点数。
答案：叶子节点数：n0=(999+1)/2=500
发表于 2016-04-12 11:29:33 回复(0)
pedro.z头像 pedro.z
完全二叉树具有该性质：1度节点数为0或1，且当总结点数为偶数时，有1个1度节点，为奇数时，没有1度节点。
二叉树的性质：0度节点=2度节点+1
因此，n0+n1+n2=2*n2+1=999 =>n2=499，n0=500
发表于 2018-08-15 22:45:11 回复(0)
Ray12345头像 Ray12345
完全二叉树最后一个非叶节点一定是节点数除2取下界，999除2取下界得499,故叶子节点数为999-499=500
发表于 2017-10-24 21:06:34 回复(0)
紫旋头像 紫旋
设完全二叉树有n个结点，已知n0=n2+1
当n为奇数是，表示完全二叉树中只有度为0与度为2的结点，此时n0+n2=n，可以求得n0=(n+1)/2;
当n为偶数是，表示完全二叉树中除度为0与度为2的结点，还包括1个度为1的结点，此时n0+n2+1=n，可以求得n0=n/2。
发表于 2017-06-26 22:40:36 回复(0)
余尧语头像 余尧语
太难了，根本不会
发表于 2025-03-22 13:52:54 回复(1)
張三同学头像 張三同学
发表于 2023-02-22 16:58:41 回复(0)
Oliver_Zhao头像 Oliver_Zhao
如果是偶数个节点，叶节点等于总节点除以2，即N%2==0，n=N/2如果是奇数个节点，叶节点等于总节点+1再除以2，即N%2==1，n=（N+1）/2
发表于 2021-09-19 18:45:44 回复(0)
不仰望，自己就是信仰头像 不仰望，自己就是信仰
减去根节点1，999-1=998，为偶数，说明没有度为1的节点，度为2的节点和度为0的节点相差一，即：n0=n2+1,那么自然就是500=499+1，n0=500
发表于 2018-05-19 20:31:36 回复(0)
轩辕楼阁头像 轩辕楼阁
若完全二叉树有N个结点，则其叶子结点的个数应为（N/2）或（N+1/2
）
发表于 2017-09-04 15:40:21 回复(0)
JackGreen头像 JackGreen
如果设有n个结点 那么最后一个父节点的个数为(n-1)/2;那么之后都是叶子节点
999-（999-1）/2=500
发表于 2017-06-07 17:47:47 回复(0)
1慢慢1头像 1慢慢1
第一：首先说本题目的答案解析
        完全二叉树中，编号为i的结点，其父节点为 [i/2] （向下取整）。
        那么编号为999的结点的父结点，就是最后一个分支结点。[999/2] = 499。
        所以，叶子结点的个数 999 - 499 = 500。
第二：关于完全二叉树中 编号为i的结点，有如下四个性质（1=<i <= n，n为结点个数）
     （1）判断 编号为i的结点，是叶子结点，还是分支结点。
           若2*i <= n，则 结点i 为分支结点。否则为叶子结点。
      （2）分支结点的左右孩子情况，以及最大分支结点编号。
          若n为奇数，则所有分支结点，都有左右孩子。
          若n为偶数，则编号为[n/2]（向下取整） 的结点，只有左孩子，没有右孩子。其余分支结点左右孩子都有。
          最大分支结点编号都是[n/2]（向下取整）。
       （3）编号为i的结点，左右孩子结点的编号。
          若编号为i的结点，有左孩子，则左孩子编号为2*i；如果有右孩子，则右孩子的编号为2*(i+1)
        （4）编号为I的结点，父结点的编号。
          编号为i的结点的父结点编号为[i/2](向下取整)。（根节点除外）
注意：以上的四条性质，都可以通过数学归纳法证明。这里不再赘述。记住会用就行。
发表于 2016-10-05 14:20:06 回复(0)
开到荼蘼913头像 开到荼蘼913
根据结点个数999，可以得到一共有10层，前9层共有511个结点，可以得到最后一层结点个数为488，如果最后一层全部铺满为512,512-488 =24，说明上一层有12个结点没有孩子结点，所有共有488 + 12 个叶子结点
发表于 2016-09-05 15:59:57 回复(0)
番茄妹头像 番茄妹
性质：非空二叉树上叶子节点数等于度为2的节点数加1，即N 0 =N 2 +1；
完全二叉树999节点( N 1 +N 2 +N 0 =999 )，为奇数，根据性质知：N 1 =0；(为偶数时，N1=1)
可以求出N0，N1，N2
发表于 2016-09-05 15:44:00 回复(0)
提交观点

问题信息

树 哔哩哔哩 2021
来自：京东2014研发工程师...
难度：
28条回答 17954浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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