Euler Tour 알고리즘은 Pre-order traversal과 본질적으로 동일합니까?

Question

나는 오일러 투어 알고리즘과 그것이 나무 순회 (traversal)에 인기있는 이유에 대해 배우려고합니다. 그러나, 나는 오일러 투어와 선주문 순회의 차이를 보지 못하고 있습니다. 당신은 오일러 투어 알고리즘을 수행 한 경우

 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을 빼서 노드의 깊이를 계산할 수 있습니다.

이러한 정보는 알고리즘에서 트리를 처리 할 때 종종 유용합니다.