试题-对一棵二叉树进行层次遍历时,应借助于一个栈()

题目

对一棵二叉树进行层次遍历时,应借助于一个栈()

A.对

B.错

解答

正确答案是 B

错。

应该借助队列。举个例子

1369

层次遍历为：5281369

遍历过程：

1.先把root放入队列

2.队列非空，取出top打印，检查是否存在左右子节点

3.若存在，则同时放入【2和8】后，执行2

如果使用栈，按2，8顺序入栈，那么取top应该是8，和正确顺序不同。

那如果是队列，按2，8顺序入队，取2，发现2存在子节点，再次加入【8，1，3】

取8，加入8的子节点，队列【1，3，6，9】

然后取1，但1没子节点，后面3，6，9同理。

C 5条回复评论

地瓜土到掉渣

学到了，点赞支持，一起加油

发表于 2021-09-11 15:15:00

凡人多烦事

大佬，能转载下吗？

发表于 2021-09-08 16:50:01

咸鱼王

由层次遍历的定义可知，在进行层次遍历时，对一层的结点访问完后，在按照他们的访问次序依次对各个节点的左右孩子顺序访问，这样一层一层的进行，先遇到的结点先访问，这与队列的操作原则比较吻合，因此在进行层次遍历时，可设置一个队列结构，遍历从二叉树的根节点开始，首先将根节点指针入队列，依次执行下面操作：

1）队列不空，出队列，去队头元素

2）访问该元素所指结点

3）若该元素所指结点的左右孩子结点非空，则该元素所指结点的左孩子指针和右孩子指针顺序入队。

发表于 2018-11-01 15:37:45

冬季恋歌

应该借助于队列，二叉树的先序，后序，中序的非递归遍历才需要栈

发表于 2018-11-01 15:37:28

繁星知晓

广度（层次遍历）优先遍历用队列，深度优先遍历用栈

发表于 2018-11-01 15:37:19