首页 > 试题广场 >

设完全二叉树的第5层上有10个叶子结点，则二叉树最少有（）个

[单选题]
设完全二叉树的第5层上有10个叶子结点，则二叉树最少有（）个结点 
  • 20
  • 32
  • 50
  • 25
查看正确选项
添加回答
方法的方式为嘚瑟的头像 方法的方式为嘚瑟的
二叉树第5层上有10个叶子结点，结点最少时只有5层，即前四层为满二叉树，有24-1=15个结点，前四层结点加上第五层结点共15+10=25个结点。
结点最多时二叉树有6层，第5层有10个叶子结点，剩余结点为分支结点，第5层最多有25-1=16个结点，分支结点个数为16-10=6个，即第6层有2*6=12个叶子结点，前5层结点加上第6层结点共25-1+12=31+12=43个结点
第六层可以有一个结点只生一个孩子，所以应该是：25-1+12=31+11=42个结点
最后答案就是：25 42 43 这是多选题的话
发表于 2019-02-13 13:56:32 回复(4)
乐壹波呀头像 乐壹波呀

做这这题目应该要先了解清楚最少和最多的情况，这题是问最少有多少个节点，所以这里是总共5层，这是一个完全二叉树结点数最少的情况，所以前4层是一个满二叉树2^4-1=15个结点，前四层结点加上第五层的叶子结点共15+10=25个结点。

而最多的情况下，是第5层为倒数第二层，即1~5层构成一个满二叉树，第5层有(2^5)-1=31个结点，因为第5层有10个叶子结点，而2^(5-1)=16,第5层最多结点的时候是16个，现在有10个叶子结点，也就是还有6个非叶子结点，这个非叶子结点在第6层有12个叶子结点，所以最多的时候就是31+12=43

发表于 2020-04-30 18:07:35 回复(0)
black__t头像 black__t
深度为k的二叉树最多有2^k-1个结点，本题要求结点数最少，那么第五层应该全为叶子结点，则前四层的结点数为2^4-1=15,因此总结点数最少为10+15=25
发表于 2019-02-19 15:52:18 回复(0)
轩辕涵婉头像 轩辕涵婉
完全二叉树第n层上至少有2^(n-1)个节点，则第一层有1个节点；第二层有2个节点；第三层有4个节点；第四层有8个节点；第5层依题意可知有10个节点，故至少有25个节点。
发表于 2017-08-11 10:42:00 回复(3)
人要学会珍惜头像 人要学会珍惜
5层少，不清楚就直接画图
发表于 2023-09-03 16:05:22 回复(0)
牛客321509759号头像 牛客321509759号
看成第 5层上5个结点
发表于 2023-05-28 10:06:10 回复(0)
啊这，名字都被用完了头像 啊这，名字都被用完了
最少的话，只有五层，第五层为10个叶子节点，上面四层的节点个数为2的4次方－1等于15 所以一共25个结点
发表于 2022-08-01 13:06:55 回复(0)
__Joy__头像 __Joy__
完全二叉树最后一层叶子结点没有填满的情况下，只有一种结果。
发表于 2019-11-23 22:32:41 回复(0)
YoJay头像 YoJay
二叉树第5层上有10个叶子结点，结点最少时只有5层，即前四层为满二叉树，有24-1=15个结点，前四层结点加上第五层结点共15+10=25个结点。
结点最多时二叉树有6层，第5层有10个叶子结点，剩余结点为分支结点，第5层最多有25-1=16个结点，分支结点个数为16-10=6个，即第6层有2*6=12个叶子结点，前5层结点加上第6层结点共25-1+12=31+12=43个结点
编辑于 2018-08-13 21:01:03 回复(0)
提交观点

问题信息

树
来自：乐视2017秋招开发工...
上传者：牛100
难度：
9条回答 16264浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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