使用一个长度最大为150的队列,对满二叉树进行广度优先遍历时_远景笔试题

凌梦初辰

注意到题目中是广度优先遍历，出去一个进入其子节点，最大是最后一层，即2^（n-1）那么多个节点。

2^(n-1)<=150,n=7,所以最大是n+1=8层

发表于 2017-09-06 09:05:45 回复(0)

牛客768117412号

算的是某一层的结点数是否≤150

发表于 2022-04-29 15:27:07 回复(0)

丷柠檬

满二叉树：一棵深度为k且有（2^k）-1个结点的二叉树

如果该题问的是完全二叉树，则有9层

发表于 2016-07-03 13:15:28 回复(2)

xncode

本题要注意队列保存的不光是本层的那一排节点，还有上一层遗留下的未访问的节点：

（1）--1

（2）--2

（3）--4+1（2层1个）

（4）--8+3+1（3 2）

（k+1）--（2^1-1+2^2-1+2^3-1+...2^[k-1]-1+2^k)

2+2^2+2^3+...2^k-(k-1)

2^(k+1)-2-(k-1)

2^(k+1)-3-k<150

max(k)=6

所以最多k+1层即7层

发表于 2015-12-12 22:07:33 回复(1)

yyyuqirong

为什么是7层，我觉得应该是8层啊

发表于 2015-12-05 14:13:30 回复(0)

tonny

A 1 + 2 + 4 + 8 + 16 + 32 + 64 + 23 = 150 共8层

发表于 2015-11-26 21:57:37 回复(5)

crisy1991

满二叉树每一层的结点个数为（第一层深度为1）第n层的节点数：2^(n-1),如果使用150的队列进行广度优先遍历，

则每一层的节点数不大于150，2^(n-1)≤150，2^7=128,2^8=256，n-1最多为7，所以最大深度n=8.

发表于 2016-06-20 11:18:06 回复(0)

DiWei

广度优先遍历满二叉树，队列中最多会容纳满二叉树的最后一层即2^(n-1)个。2^7=128,所以是8层。

发表于 2015-11-27 10:57:37 回复(4)

爱吃青菜皮卷面的byr

广度优先遍历二叉树。

广度优先周游二叉树(层序遍历)是用队列来实现的，从二叉树的第一层（根结点）开始，自上至下逐层遍历；在同一层中，按照从左到右的顺序对结点逐一访问。

按照从根结点至叶结点、从左子树至右子树的次序访问二叉树的结点。算法：

1初始化一个队列，并把根结点入列队；

2当队列为非空时，循环执行步骤3到步骤5，否则执行6；

3出队列取得一个结点，访问该结点；

4若该结点的左子树为非空，则将该结点的左子树入队列；

5若该结点的右子树为非空，则将该结点的右子树入队列；

6结束。

发表于 2017-02-15 22:33:41 回复(0)

mini-micky

我查了下字典，“容纳”是:包容，包含，包括，容得下。等意思，所以虽然可以有第八层的元素，但是只能容得下第七层的所有元素，所以应该是第七层

发表于 2016-08-13 14:52:14 回复(0)

学术废物

注意是队列有出有进节点不是一直待在里面的出入队之后只剩下某一层的元素只用看下层最多能有多少个元素即可此题为150也就是下层的元素不可超过150 又是满二叉树那么即为128 上层的64个元素出一个进两个子元素最后队列内有128个元素即为第八层的元素

发表于 2022-03-11 09:10:30 回复(0)

牛客76165061号

第八层不是爆了吗

编辑于 2024-03-09 18:47:46 回复(0)

simon_free

如果有9层，会爆仓，如果是8层，则有一点空隙

发表于 2023-11-11 18:17:15 回复(0)

逼格数据

按照答案，这里容纳的意思是，遍历的时候能够装入1个也算

发表于 2023-08-21 18:16:07 回复(0)

coding_more

注意看是满二叉树，不是完全二叉树😐

发表于 2023-07-04 12:45:37 回复(0)

纠结的哈士奇在笔试

满二叉树中第7层的结点个数为128个，满二叉树的树的深度计算：h = 2^n-1，此时n - 1 = 7，故答案选8

发表于 2023-05-15 19:43:25 回复(0)

秋招冲冲冲123321

队列最多只存储一层的结点，所以满二叉树第八层 128，符合要求

发表于 2022-03-15 19:36:33 回复(0)

卖萌小伙张三

使用广度优先搜索，则队列中存的是某一层的所有节点，所以树中的任意一层的节点数都不能大于150。而满二叉树的某一层的节点数为：

_，所以易得 $n$ 的最大值是8。

发表于 2021-03-09 14:16:40 回复(0)

逆袭的黑马

满二叉树第n层的节点数为 2^（n-1）

发表于 2020-12-27 17:02:03 回复(0)

安.22

log2（n+1）向上取整。

发表于 2020-09-12 14:10:34 回复(0)

使用一个长度最大为150的队列,对满二叉树进行广度优先遍历时

问题信息

热门推荐

相关试题