algorithm - 树以级别优先顺序和深度优先顺序递归遍历

Question

是否有任何算法可以以一级优先顺序递归遍历树，而后序非递归遍历。非常感谢。

Answer 1

您可以通过使用堆栈而不是递归中使用的隐式调用堆栈来迭代地递归后序树。

Answer 2

要获得有效的递归广度优先搜索，您可以使用迭代加深深度优先搜索。这对于分支因子很高的情况特别有用，在这种情况下，常规的广度优先搜索往往会因过多的内存消耗而窒息。

编辑： Marcos Marin 已经提到过它，但为了完整起见，关于广度优先遍历的 Wikipedia 页面描述了该算法：

1. 将根节点排入队列。
2. 将节点出列并检查它。
   • 如果在该节点中找到了要查找的元素，则退出搜索并返回结果。
   • 否则，将尚未发现的任何后继节点（直接子节点）排入队列。
3. 如果队列为空，则图上的每个节点都已检查——退出搜索并返回“未找到”。
4. 从第 2 步开始重复。

注意：使用堆栈而不是队列会将这个算法变成深度优先搜索。

如果您想进行非递归深度优先遍历，那么最后一行显然对您来说很有趣。获得预购或后购只是修改步骤 2.b 中附加节点的方式。

Answer 3

维基百科说，

遍历

与链表和一维数组等只有一种逻辑遍历方式的线性数据结构相比，树结构可以通过多种不同的方式进行遍历。从二叉树的根开始，可以执行三个主要步骤，它们执行的顺序定义了遍历类型。

这些步骤（不分先后）是：在当前节点上执行一个动作（称为“访问”该节点）、遍历左子节点、遍历右子节点。因此，该过程最容易通过递归来描述。

要按前序遍历非空二叉树，请在每个节点处递归执行以下操作，从根节点开始：

1. 访问节点。
2. 遍历左子树。
3. 遍历右子树。（这也称为深度优先遍历。）

要按顺序遍历非空二叉树，请在每个节点处递归执行以下操作：

1. 遍历左子树。
2. 访问节点。
3. 遍历右子树。（这也称为对称遍历。）

要以后序遍历非空二叉树，请在每个节点处递归执行以下操作：

1. 遍历左子树。
2. 遍历右子树。
3. 访问节点。

最后，树也可以按级别顺序遍历，我们在到达较低级别之前访问级别上的每个节点。这也称为 广度优先遍历。