先序遍历二叉树和深度优先搜索是否相同？

Question

我认为Pre-order遍历和DFS在许多情况下都是相同的，因为两种遍历方式都会按深度优先的方式一直遍历到叶子节点。如果我有错误，请有人纠正一下吗？

提前感谢！

- Srikanth Kandalam

---

http://en.wikipedia.org/wiki/Tree_traversal#Depth-first - Walter Tross

Answer 1

Pre-order（前序遍历）是 DFS 的一种类型。

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

更多信息请查看这里。

- herohuyongtao

---

我觉得这个问题并不需要高级的答案，我认为他正在寻找预订DFS，这在普通计算机专业学生中被称为“DFS”作为一个简称。 - Khaled.K

我认为他只是观察到，当所讨论的图也是一棵树，并且DFS的初始顶点是树的根时，DFS和先序遍历是等价的。对于k叉树（其中k>2），中序遍历没有意义。 - Dave

即使该图是一棵二叉树，前序遍历的输出也不太可能与前驱子图的遍历结果相同，除非顶点邻接列表以与它们在树中作为节点“子代”时一致的顺序进行枚举。也就是说，图的表示没有“左”和“右”子节点的概念。 - Dave

实际上，在二叉树上有六种深度优先遍历方式——前序遍历、后序遍历、中序遍历、反向前序遍历、反向后序遍历和反向中序遍历。这对应于三个操作（3！的六个排列）的六种排列，其中操作是“向左走”、“向右走”和“处理节点”。 - user755921

Answer 2

不会。预订具有严格的方式来访问左节点和右节点，但对于深度优先搜索（DFS），可以是任何顺序，因为没有严格的方式。因此，根据您在堆栈上推送的内容，可能存在多个遍历。

- lu5er

Answer 3

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

DFS的思想是选择一个分支并深入探索，完全探索它。而选择分支并向下走的方式取决于你正在实现哪种DFS。仅为完成而言，在BFS算法中，我们按层遍历。

记住，先序遍历只是DFS的一种类型。我们还有其他方法，如下所示。

图片来源：Base CS

为了更好的理解，请参考这篇博客或者甚至是这篇。

- Amitrajit Bose

Answer 4

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

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

在Java Swing的实现中，depthFirstEnumeration与postOrderEnumeration相同。我的测试和官方文档证实了这一点。 其他人可以以不同的方式定义深度优先。例如，维基百科上的一篇文章指出，前序遍历和后序遍历是深度优先遍历的特定类型。这意味着深度优先遍历不是一种具体的遍历算法。

- Jan Bodnar

Answer 5

前序遍历是深度优先搜索中的一种类型 在深度优先搜索中，共有3种遍历类型：

- 中序遍历 - 前序遍历 - 后序遍历

- KARTHIK TARAKA SAI BOLLA

---

你的回答可以通过提供更多支持性的信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的回答是否正确。你可以在帮助中心找到关于如何撰写好回答的更多信息。 - undefined