广度优先搜索遍历 VS 先序遍历 VS 深度优先搜索遍历

Question

对于一棵二叉树，广度优先遍历（BFS）和先序遍历是否相同？我对这两种不同类型的遍历有点困惑。请问有人能给我解释一下吗？此外，先序遍历如何与深度优先遍历（DFS）相比较？

非常感谢！

- Liu

---

感谢您为了其他用户的利益修改我的问题所做出的努力！ - Liu

Answer 1

不，先序遍历实际上是深度优先搜索（DFS）遍历的一种形式。DFS有三种不同的形式，分别是：

1. 先序遍历
2. 中序遍历
3. 后序遍历

为了证明广度优先搜索（BFS）遍历与先序遍历不同，我将在下面展示一个反例：

需要明确的是，二叉树和二叉搜索树并不相同，即二叉树可以定义为：

二叉树 - 其元素最多有两个孩子的树称为二叉树。请注意，并没有提及子节点的顺序。

好了，现在来看看反例，取以下简单的二叉树：

对于先序遍历，节点按以下顺序访问：先序遍历：[1,2,4,3]

现在对于广度优先搜索遍历，节点按以下顺序访问：

BFS: [1,2,3,4]

注意：先序遍历和BFS遍历不同。

有关不同树遍历的更多信息，请查看此链接。

希望这可以帮助你！

- Nathan

---

非常好的回答。此外，有助于可视化区别的是，预先顺序搜索通常使用堆栈数据结构实现，而BFS通常使用队列。这是因为BFS优先考虑节点的邻居，而先序DFS优先考虑节点的子节点。 - ifiore

@ifiore 谢谢，是的，你说得对 :) DFS 使用栈，而 BFS 使用队列作为它们的底层实现。 - Nathan

谢谢！但是直到我看了你的回答，我才意识到我的问题是错误的。我的正确问题是DFT和先序遍历是否相同？ - Liu

是的，前序遍历是深度优先搜索的一种形式。我也在我的答案中提到了这一点。 - Nathan

Answer 2

DFS类型包括先序遍历、中序遍历和后序遍历；

DFS的方式是先访问我的后代（孙子、曾孙……），然后再看我的兄弟的后代。BFS的方式是先访问我的兄弟，然后是他们的孩子，以此类推。

先序遍历DFS技术通常用于图遍历。

中序遍历只在二叉树中使用。（树是特殊的图）

BFS在树的情况下是按层遍历。

这四种遍历方法不同，其结果也不同。有时它们的结果可能相同，所以不要被混淆，检查不同的树就会发现差异。

- UNREAL

---

我认为在上面的答案中，后序遍历是不正确的，正确的后序遍历应该是：4,5,2,6,7,3,1。 - pavan.vn101

是的，你说得对，我会进行更正。实际上，如果你按照右孩子、左孩子、然后打印的顺序遍历，它将显示7635421。 - UNREAL