Euler Tour算法本质上和Pre-order遍历一样吗？
Is the Euler Tour algorithm essentially the same as Pre-order traversal?
我正在尝试了解 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 以及为什么它用于其他遍历，我们将不胜感激。谢谢
通过欧拉导览，您可以从结果中获得更多信息。
例如，您可以查看节点是否为叶子。如果节点的前驱和后继相同，就会出现这种情况。
此外，您还可以通过为每个前向腿向计数器加 1 并为每个向后腿减去 1 来计算节点的深度。
在您的算法中处理树时，这些信息通常很有用。
请注意，post订单信息也出现在您的 Euler 游览中。如果只列出每个节点的 last 时间，我们得到
C -> D -> B -> F -> E -> A
很遗憾，我们无法从巡演中获得inorder（对称顺序）。在您的示例中，通过查看节点 E 及其 child F 可以清楚地看出这一点，我们无法真正看到 child 是左还是右。
欧拉遍历方法可以稍微扩展一下以包括树的三个递归顺序（pre-in-post-）。按照树的轮廓，访问每个节点三次，分别是进入左边child之前、左右之间child、右边之后child。如果缺少 child，请连续访问。
我们可以通过以下方式扩展您的示例，为您之前的游览添加数字：
A1 -> B1 -> C123 -> B2 -> D123 -> B3 -> A2 -> E12 -> F123 -> E2 -> A3
我正在尝试了解 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 以及为什么它用于其他遍历，我们将不胜感激。谢谢
通过欧拉导览，您可以从结果中获得更多信息。
例如，您可以查看节点是否为叶子。如果节点的前驱和后继相同，就会出现这种情况。
此外，您还可以通过为每个前向腿向计数器加 1 并为每个向后腿减去 1 来计算节点的深度。
在您的算法中处理树时，这些信息通常很有用。
请注意，post订单信息也出现在您的 Euler 游览中。如果只列出每个节点的 last 时间，我们得到
C -> D -> B -> F -> E -> A
很遗憾，我们无法从巡演中获得inorder（对称顺序）。在您的示例中，通过查看节点 E 及其 child F 可以清楚地看出这一点，我们无法真正看到 child 是左还是右。
欧拉遍历方法可以稍微扩展一下以包括树的三个递归顺序（pre-in-post-）。按照树的轮廓，访问每个节点三次，分别是进入左边child之前、左右之间child、右边之后child。如果缺少 child，请连续访问。
我们可以通过以下方式扩展您的示例，为您之前的游览添加数字：
A1 -> B1 -> C123 -> B2 -> D123 -> B3 -> A2 -> E12 -> F123 -> E2 -> A3