Euler Tour算法與Pre-Order traversal基本相同嗎？

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 

顯然，在歐拉，你的路徑有每個節點的值至少兩次，但是這僅僅是由於算法的遞歸特性當你編程時。如果你願意，你可以做與歐拉巡迴賽一樣的計算...與預購，對不對？

如果有人可以幫助解釋歐拉巡迴賽，以及它爲什麼用於其他遍歷，那將非常感激。謝謝。

Answer 1

通過歐拉之旅，您可以從結果中獲得更多信息。

例如，您可以查看節點是否爲葉。如果節點的前任者和後繼者是相同的，就會出現這種情況。

此外，您可以通過向計數器對每個前向腿添加+1併爲每個後向腿減去1來計算節點的深度。

在處理算法中的樹時，這些信息通常很有用。