是否在深度优先搜索的二叉树上进行预排序遍历？

Question

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

提前致谢!

Answer 1

预订是一种DFS.

深度优先遍历有三种类型:预订,按顺序和后订购.

点击这里了解更多信息.

Answer 2

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

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

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

图片来源：Base CS

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

Answer 3

它可能取决于深度优先算法的定义和实现.在DefaultMutableTreeNode类的Java Swing的JTree组件都有用于树遍历以下列举的方法:

• depthFirstEnumeration()
• postorderEnumeration()
• preorderEnumeration()
• breadthFirstEnumeration()

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

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

Answer 4

它不会.预订有严格的方式访问Left节点,然后访问Right节点.但对于DFS来说,它可以是没有严格的时尚.因此,基于您在堆栈上推送的内容,存在多个遍历.