0

在这篇文章中，biziclop 插入了非递归深度优先搜索算法的伪代码。

如果我们想使用递归DFS 算法来检查节点的适当性，我们可以利用两种变体：前序（当一个节点在其子节点之前检查时）和后序（当子节点在其子节点之前检查时）节点），加上仅用于二叉树的第三个变体（按顺序：左子树，然后是节点，然后是右子树）。

由于我有兴趣尽可能拥有所有三个变体，因此我尝试修改 biziclop 的伪代码以获得 DFS 算法的所有三个变体。问题是，我陷入了这样一个事实，即节点在其子节点之前被添加到堆栈（并因此被检查）。任何想法？

4

1 回答 1

0

为什么“（并因此检查）”？在递归方法中，您选择首先检查当前节点或首先查看它的子节点，以同样的方式，您只看到节点，但何时检查它们？它在你身上。例如，如果您看到它的孩子并检查了它们，只需使用 flag to seen_its_children（不表示已检查）来处理 post_order 和 in_order 它是相同的，在 pre_order 中您按照您所说的去做就足够了.

于 2019-06-04T18:23:45.177 回答