data-structures - Euler Tour算法和前序遍历本质上是一样的吗？

Question

我正在尝试了解 Euler Tour 算法以及为什么它在树遍历中很受欢迎。但是，我看不出 Euler Tour 和树的预序遍历之间的区别。

假设你有一棵树:

     A
    / \
   B   E
  / \   \
 C   D   F

如果您执行欧拉游览算法，它将是:

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

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

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

显然，在 Euler Tour 中，每个节点值在路径中至少出现两次，但这只是由于编程时算法的递归性质所致。如果您愿意，您可以进行与 Euler Tour 相同的计算...通过预订，对吗？

如果有人可以帮助解释 Euler Tour 以及为什么使用它而不是其他遍历，我们将非常感激。谢谢。

Answer 1

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

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

此外，您还可以通过为每个前向支路的计数器加 +1 并为每个后向支路减去 1 来计算节点的深度。

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