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

Question

对于二叉树，广度优先搜索遍历（BFS）是否与预序遍历相同？我对这两种不同类型的遍历有点困惑。任何人都可以向我解释一下吗？此外，预序遍历与深度优先搜索遍历(DFS) 相比如何？

非常感谢！

Answer 1

DFS类型有前序、中序、后序；

DFS 就像 - 首先寻找我的后代（孙子-孙子），然后我会看到我的兄弟姐妹的后代。BFS 就像 - 首先去找我的兄弟姐妹，然后是他们的孩子，然后是他们的孩子，依此类推。

前序DFS技术一般用在图的遍历中。

仅在二叉树中进行中序遍历。（树是一种特殊的图）

BFS是树的情况下的层序遍历。

这四种是不同的遍历技术，结果也不同。有时它们的结果可能是相同的，所以不要感到困惑，检查不同的树，你会发现差异。

Answer 2

不，前序遍历实际上是深度优先搜索 (DFS) 遍历的一种形式。DFS有三种不同的形式，即：

1. 预购
2. 为了
3. 下单

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

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

二叉树- 元素最多有 2 个孩子的树称为二叉树。请注意，没有提到子项的排序。

好的现在到反例，采用以下简单的二叉树：

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

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

BFS: [1,2,3,4]

注意：前序遍历不同于 BFS 遍历。

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

希望，这有帮助！