为什么队列适用于二叉树的关卡顺序遍历？

Question

我不确定这样的问题是否被接受，如果不被接受，我会很乐意删除/编辑它，但我认为这不仅仅是一个讨论问题，其答案取决于观点和解决方案背后的事实。

所以我读到了二叉树的层次顺序遍历，当我们使用队列数据结构时，存在一个< code>O(n)解决方案。

算法是这样的

1)创建一个空队列q

2） temp_node = 根

3） 在temp_node不为空时循环

a) print temp_node->data.
b) Enqueue temp_node’s children (first left then right children) to q
c) Dequeue a node from q and assign it’s value to temp_node

我理解算法，但我不能理解的是，如果一个人事先不知道，他怎么会想出这个解决方案。换句话说，队列的什么属性（可能是二叉树）使其成为本例中使用的正确DS。在这里使用队列进行二叉树的级别顺序遍历的想法是什么？谢谢

上面树的级序遍历是1 2 3 4 5

Answer 1

通常，当我们在按顺序遍历期间访问一个节点（比如N）时，我们首先将其左子节点推送到队列中，然后将右子节点推送到队列中的下一个元素（假设两者都存在）并继续移动到队列中的下一个元素。

现在，下一个元素将是先前访问的节点n的右元素。

基本上递归结合队列的FIFO属性允许你做有序遍历。

Answer 2

我想如果你多研究一下BFS，你会自动得到你的答案。

队列具有特殊属性，您可以从一端推送并从另一端弹出。
为了他们穿越

就像级别顺序遍历一样，我们标记访问过的节点并弹出它们，从另一端我们推送要标记访问过的元素，这就是级别顺序遍历所做的。

仔细观察这两个操作，这两个操作是相互独立的。这种操作隔离是由队列提供的。

Answer 3

当你先遍历树的宽度，宽度会变得越来越宽。您需要一个队列来跟踪下一步要更深入访问的子树的根，就像“待办事项”列表一样。