首页 > 试题广场 >

⼀个完全⼆叉树中有743个节点, 则该⼆叉树中的叶子节点个数

[单选题]
⼀个完全⼆叉树中有743个节点, 则该⼆叉树中的叶子节点个数为？ 
  • 370
  • 371
  • 372
  • 以上都不对
查看正确选项
添加回答
敬爱头像 敬爱
笨一点的方法：1+2+4+8+16+32+64+128+256=511;743-511=232;232/2=116;256-116+232=372.
发表于 2018-08-30 11:12:46 回复(0)
JFF201806281030161头像 JFF201806281030161
假设节点从1开始编号，最后一个非叶子节点编号为743/2=371,叶子节点数为372个
编辑于 2018-09-07 22:25:00 回复(3)
胡萝卜须摇头玩头像 胡萝卜须摇头玩
为叶子节点数，n为节点数，则n0 = (n +1) / 2。
发表于 2018-09-07 17:14:14 回复(0)
helloworldli头像 helloworldli
n层树的满二叉树结点为：2^n-1
第n层满二叉树的结点为：2^(n-1)
512= 2^9<743<2^10
所以满的有9层，第九层有：(2^9-1)=256，第十层还有:743-(2^9-1)=232
232个叶子结点有116个根节点
所以树的叶子结点有：256-116+232=372

发表于 2019-02-21 22:36:24 回复(0)
牛客740118594号头像 牛客740118594号
完全二叉树 叶子数= （总节点数+1）/2
发表于 2021-05-24 22:16:02 回复(0)
这个ID没人用头像 这个ID没人用
一个不用记公式的方法。由于完全二叉树，所以节点数从上到下是1+2+4+8+16+32+64+128+256=511，算几步发现是有规律的，所以最后一层有743-511=232，叶子节点数=232+(256-232/2)=372个
发表于 2020-08-18 14:22:19 回复(0)
牛客837997003号头像 牛客837997003号
2^n-1=743
2^n=743+1=744
2^(n-1)=744/2=372
发表于 2020-07-31 21:32:19 回复(0)
超爱吃香菇的小姑娘头像 超爱吃香菇的小姑娘
根据n2与n0的关系：n0=n2+1
且完全二叉树中n1最多有一个.
所以：没有n1时：n2+1+n2 =743 算出 n2 = 371，所以：n0= 372.
           有n1时：n2+1+n2+1 =743 不符合题意(舍)
发表于 2019-08-19 15:57:54 回复(0)
想堆雪人的柠檬精在看面经头像 想堆雪人的柠檬精在看面经
对于任意一二叉树而言，若终端结点数为x,而其度数为2的结点数为y,则x=y+1.
发表于 2018-08-17 10:27:25 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 商汤科技 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 技术支持 数据挖掘工程师 2018 产品 C++ 运营 C 大数据开发工程师 Java工程师
上传者：小小
难度：
9条回答 6408浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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