首页 > 试题广场 >

题目来源于王道论坛 已知一棵完全二叉树的第6层（设根为

[单选题]
题目来源于王道论坛
已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是()。 
  • 39
  • 52
  • 111
  • 119
查看答案及解析
添加回答
推荐
林呼头像 林呼

解析：

完全二叉树比满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层有叶结点。第6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了8×2=16个叶结点，故完全二叉树的结点个数最多为(27-1)-16=111个结点。

发表于 2018-09-03 20:50:59 回复(1)
一个锤子头像 一个锤子
两种情况：第六层或者第七层是最后一层
第七层是最后一层时完全二叉树的结点个数最多
此时 第六层总26-1 =32个结点中有8个是叶子节点
则第六层中另外24个结点都有孩子 而满足结点数最多 则第七层共有24*2=48个结点
总结点数就是63+48=111
发表于 2019-02-26 19:06:58 回复(1)
菲尼克斯弗兰克头像 菲尼克斯弗兰克
前六层是满的 第六层可以有2^5 = 32个结点 8个叶子结点 24个非叶子结点 
第七层最多再放24*2 = 48 个，明显结点数最多，且能保证为完全二叉树
n = （2^6-1）+ 48 = 63 + 48 = 111.
发表于 2018-10-29 10:17:43 回复(0)
牛客367212304号头像 牛客367212304号
谨记！！！完全二叉树最后两层都可能有叶结点
发表于 2020-04-23 14:34:36 回复(1)
unique3831头像 unique3831
第六层，25=32，有8个叶子节点，则32-8=24个非叶子，要想节点数目最多，则需要24个非叶子上长出24*2=48个叶子节点，所以总数为1+2+4+8+16+32+48=111.
发表于 2023-07-29 20:00:09 回复(0)
牛客90237887号头像 牛客90237887号
可以用满二叉树减掉 缺少的叶结点数 也可以 用最后一层叶结点加上其他层总结点数
发表于 2022-09-28 21:36:45 回复(0)
大大大🍍头像 大大大🍍
第六层有8个节点，而不是在第六层上有8个节点，，，
发表于 2022-09-10 11:21:09 回复(0)
牛客697589369号头像 牛客697589369号
最多节点：
第6层有8个叶子，第6层总共节点数：2^5=32个，除去8个叶子节点，有 24个非叶子节点
所以在第7层的叶子结点有:24*2=48;
6层满+7层叶子节点 = 2^6-1+48 = 111
发表于 2022-02-17 18:07:06 回复(0)
pech头像 pech
最多，不是最少，还有一层
发表于 2021-07-27 09:05:32 回复(0)
望云鸽头像 望云鸽
好题
发表于 2019-11-23 22:15:01 回复(0)
提交观点

问题信息

树
上传者：林呼
难度：
10条回答 4938浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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