首页 > 试题广场 >

一棵完全二叉树第六层有9个叶结点（根为第一层），则结点个数最

[单选题]
一棵完全二叉树第六层有9个叶结点（根为第一层），则结点个数最多有（） 
  • 112
  • 111
  • 107
  • 109
查看答案及解析
添加回答
韵阳月流头像 韵阳月流
总结点数=七层总结点数-第六层叶子结点数*2=(2^7-1)-9*2=109个
发表于 2020-08-19 21:59:25 回复(0)
康斯坦丁_s头像 康斯坦丁_s
方法一:

根据二叉树的性质,第i层上的结点数最多为2^i(i >= 0,所以第一层为i=0)个,所以第六层的结点数最多为2^5=32个,根据题意第六层有9个叶子结点,推测出还有第七层,所以第六层结点数减去9个叶子结点,剩下的23个结点都有左右子树,故第七层有23*2=46个结点,总的结点数=2^0+2^1+2^2+2^3+2^4+2^5+46=109个

方法二:

总结点数=七层总结点数-第六层叶子结点数*2=(2^7-1)-9*2=109个
发表于 2020-08-21 11:02:10 回复(0)
会编程的椰子头像 会编程的椰子

完全二叉树是由满二叉树而引出来的，若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数(即1~h-1层为一个满二叉树)，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。这里说明一下，为什么还有第七层。大佬  请略过。

第二层最多有2^1=2个结点。如果题目告诉我们，已知第二层有一个叶子结点。叶子结点数小于第二层总结点数，那么，另外还有一个节点，这 就个另外的节点它不是叶子结点，不是叶子结点，说明它有子结点，所以还有第三层。
发表于 2022-11-06 20:06:52 回复(0)
提交观点

问题信息

C++工程师 声网 2020
来自：声网2020校招-通用...
上传者：小小
难度：
3条回答 1398浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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