首页 > 试题广场 >

一棵有12个节点的完全二叉树，其深度是多少？

[不定项选择题]
一棵有12个节点的完全二叉树，其深度是（） 
  • 4
  • 5
  • 3
  • 6
添加回答
推荐
牛客787908号头像 牛客787908号
A
本题目是完全二叉树，首先要了解完全二叉树的概念；
完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树；
根据第一层是2^0、2^1、2^2........
设二叉树的深度为n，那么树的节点总数最多为（2^n-1），
那么2^n-1>=12,可以得出n为4

此题目主要考察二叉树深度与节点数之间的关系


编辑于 2016-01-07 19:55:43 回复(2)
爱吃青菜皮卷面的byr头像 爱吃青菜皮卷面的byr
具有n个结点的完全二叉树（包括满二叉树）的高度为【log2 n】+1 或者（【log2 （n+1 ）】）
证明：设所求完全二叉树的深度为k，由完全二叉树的定义知道，其前 k-1 层 是深度为 k-1 的满二叉树，一共有2^(k-1) -1 个结点。由于完全二叉树深度为k，故第k层上还有若干上结点，因此，该完全二叉树的结点个数为n>2^(k-1) -1 。 再者，由性质2 知道n<= 2^k  -1,即
2^(k-1) -1 < n <=2 ^k  -1  。 由此推导得2^(k-1) -1 < n <= 2^k -1 
由此推导得2^(k-1) <= n <2^k ,取对数后有：
k-1<= log2 n <k
因为k为整数，所以有k-1=[log2 n],即可得k = [log2 n] +1。


发表于 2017-02-15 22:08:50 回复(1)
huixieqingchun头像 huixieqingchun
要注意题目中是完全二叉树，所以只有一种情况的。
发表于 2016-05-10 11:17:48 回复(0)
牛客321509759号头像 牛客321509759号
这个题有点二，显示多选，结果单选
发表于 2023-05-27 21:25:02 回复(0)
等一下，我的offer呢？头像 等一下，我的offer呢？

要看从 depth 从几开始数，反正 n 层 perfect binary tree 的 node 个数为 ，即可，这里即是 ，故 n 为 4,即 4 层。

这里 root 是第 1 层。

那么 depth 和 层数的关系是什么呢？就是要 root 的 depth 为几，如果为 1,那么 depth 为几就是几层，如果 depth 为 0,那么 depth 为几，层数就要减 1.

发表于 2020-09-22 18:50:17 回复(0)
茶树菇100头像 茶树菇100
2^n-1>=12 2^（n-1）-1<12 可以得出n为4
发表于 2019-08-19 22:05:56 回复(0)
爱。在心口难开头像 爱。在心口难开
题中没说深度从1开始吧，那如果根节点深度是0呢？
发表于 2018-07-05 00:15:43 回复(0)
千寻者头像 千寻者
深度d(从根节点，深度为1开始)、结点个数n，它俩关系:log2(n+1)(上取整)≤d＜log2(n+1)(上取整)+1
发表于 2017-07-12 11:01:43 回复(0)
已注销头像 已注销
居然是不定项选择，有点瘆得慌，不敢肯定....o(╯□╰)o
发表于 2017-06-27 22:34:26 回复(0)
springx11头像 springx11
假设树的高度为h 则满二叉树的节点个数是2^h-1个  因为2^4-1=15>12 所以选A
发表于 2016-01-07 19:38:38 回复(1)
XYRITD头像 XYRITD
A  
深度为n的满二叉树有2n-1个节点，深度为n的完全二叉树节点个数肯定不大于深度为n的 满二叉树的节点个数，大于深度为n-1的满二叉树的节点个数
因此2n-1-1 <12<= 2 n -1,得 log213 =< n < log213+1,因此n=4
发表于 2016-01-07 09:40:41 回复(2)
hah头像 hah
A  [log2(n)]  取得下界
发表于 2015-01-04 16:54:04 回复(0)
提交观点

问题信息

树 腾讯
上传者：公主受
难度：
12条回答 20650浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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