首页 > 试题广场 >

设一棵完全二叉树中有65个结点，则该完全二叉树的深度为(

[单选题]
设一棵完全二叉树中有65个结点，则该完全二叉树的深度为(     )。 
  • 8
  • 7
  • 6
  • 5
查看正确选项
添加回答
白起丶头像 白起丶
假设二叉树的深度为k，则该二叉树最多有2^k - 1个节点，若k为6，则最多有2^6 - 1 = 63个节点，小于65。故该二叉树的深度为7，选B。
发表于 2020-07-07 20:01:32 回复(0)
xxxxxxxxxxxxxxxa头像 xxxxxxxxxxxxxxxa
2^k <66<2^(k+1)  k=6，所以深度为6，但是有的树深度的定义包含root，所以可能答案是7。

至少我在牛客网做的选择题，都是将层数定义为高度的或者深度的。
而在DSAA中，是将路径定义为高度或者深度的。这值得注意。


那我该这么办呢，对编程上来说，不是问题。但是做这些题的时候，还有问题。以后求深度或者高度，我就在原有的基础上+1，
编辑于 2018-05-22 14:50:08 回复(0)
meigumi头像 meigumi
65=1+2+4+8+16+32+2，总共7层
发表于 2019-10-18 12:54:20 回复(0)
牛客446215022号头像 牛客446215022号
2^(k-1)<65<2^k-1
该树深度为k，那么满二叉树的节点数（就是深度k的二叉树的最大节点数）就是2^k-1，所以这是上限
根据完全二叉树的定义，深度k，n个节点的完全二叉树，和深度k的满二叉树的1~n编号节点一致，所以这个完全二叉树的次底层也可以看做是满二叉树，所以如果深度是k，那么完全二叉树至少有2^(k-1)-1+1个节点
发表于 2022-08-19 16:58:51 回复(0)
浪子亭头像 浪子亭
向下取整不大于的最大整数
发表于 2018-04-12 20:16:08 回复(0)
zurp头像 zurp
log(2n)=1+logn，此处log都是对2的，还有就是不特别说明的话，这类型的式子都是向下取整
发表于 2018-04-05 20:16:30 回复(0)
凡尘的光头像 凡尘的光
B

编辑于 2024-04-03 17:11:19 回复(0)
XiaoJie头像 XiaoJie
答案为什么不是6？
发表于 2018-06-23 22:02:48 回复(1)
天涯追梦的航帆头像 天涯追梦的航帆
| log2n | +1
 
发表于 2017-06-23 14:52:48 回复(0)
提交观点

问题信息

树
上传者：呼呼L
难度：
9条回答 4297浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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