algorithm - 二叉树上的预序遍历与深度优先搜索相同吗？

Question

在我看来，Pre-order traversal 和 DFS 与我们以深度方式遍历到叶节点的两种情况相同。如果我错了，有人可以纠正我吗？

提前致谢！

Answer 1

预购是 DFS 的一种。

深度优先遍历分为三种类型：前序、中序和后序。

在这里查看更多信息。

Answer 2

不会的。预购具有访问左节点然后访问右节点的严格方式。但对于 DFS，它可以是任何一种，因为没有严格的时尚。因此，根据您压入堆栈的内容，存在不止一个遍历。

Answer 3

这可能取决于深度优先算法的定义和实现。Java Swing 的 JTree 组件的DefaultMutableTreeNode类具有以下用于树遍历的枚举方法：

• depthFirstEnumeration()
• postorderEnumeration()
• preorderEnumeration()
• 广度优先枚举（）

在 Java Swing 的实现中depthFirstEnumeration，与postOrderEnumeration. 我的测试和官方文档 证实了这一点。

其他人可以定义深度优先的不同含义。例如，维基百科上的一篇文章指出，前序和后序遍历是深度优先遍历的特定类型。这意味着深度优先遍历不是具体的遍历算法。

Answer 4

直观地说，由于我们在大多数实现中使用递归（即利用隐式堆栈数据结构）应用 DFS 算法的方式，它们的感觉是相同的。在大多数情况下（或全部），结果与预购遍历相同。

DFS的想法是选择一个分支并深入其中，彻底探索它。然而，选择分支和向下的方式取决于您正在实施的 DFS 类型。只是为了完成，在BFS 算法中，我们逐层遍历。

请记住，预购只是DFS 的一种。我们还有其他方法，如下所示。

图片来源：Base CS

为了更好地理解，请参阅此博客甚至此博客。