欧拉巡回赛算法本质上是否与前序遍历相同？

Question

我正在尝试了解Euler巡回赛算法，以及为什么它在树遍历中很流行。然而，我没有看到欧拉之旅和树的预定遍历之间的区别。

假设你拥有这棵树：

     A
    / \
   B   E
  / \   \
 C   D   F

如果执行欧拉巡回算法，则如下所示：

A -> B -> C -> B -> D -> B -> A -> E -> F -> E -> A

但这样做的目的是什么？它看起来就像递归预顺序的完全相同的版本：

A -> B -> C -> D -> E -> F

显然，在Euler旅游中，每个节点值在路径中至少有两次，但这只是因为算法在编程时的递归性质。如果你愿意的话，你可以做和欧拉巡回赛一样的计算。提前订购，对吧？

如果有人能帮助解释欧拉之旅，以及为什么它被用于其他横渡，那将是非常感谢的。谢谢。

Answer 1

通过欧拉之旅，您可以从结果中获得更多信息。

例如，您可以查看节点是否是叶。如果节点的前身和后继节点是相同的，就会出现这种情况。

此外，您还可以计算节点的深度，方法是将+1添加到每个前腿的计数器中，并对每个后向腿减去1。

在处理算法中的树时，这些信息通常是有用的。

Answer 2

请注意，Euler之旅中也显示了postorder信息。如果只列出最后一次列出的每个节点，我们就会得到

C -> D -> B -> F -> E -> A

不幸的是，我们无法从巡演中获得无序(对称顺序)。在您的示例中，从节点E及其子F可以清楚地看出这一点，我们不可能实际看到该子节点是左还是右。

Euler遍历方法可以稍微扩展，以包含树的三个递归顺序(后置前)。按照树的轮廓，访问每个节点三次，然后进入左子节点、左子节点和右子节点以及右子节点。如果儿童失踪，请连续探视。

我们可以通过以下方式扩展您的示例，将数字添加到您之前的游中：

A1 -> B1 -> C123 -> B2 -> D123 -> B3 -> A2 -> E12 -> F123 -> E2 -> A3