Является ли алгоритм 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 и почему он используется по сравнению с другими обходами, это было бы очень признательно. Спасибо.


data-structures tree graph-traversal tree-traversal preorder
person Bob    schedule 06.10.2016    source источник

Ответы (2)


arrow_upward
0
arrow_downward

С помощью эйлерова тура вы можете получить дополнительную информацию из результата.

Например, вы можете увидеть, является ли узел листом. Это было бы так, если бы предшественник и преемник узла были одинаковыми.

Кроме того, вы сможете рассчитать глубину узла, добавляя +1 к счетчику для каждой прямой ноги и вычитая 1 для каждой обратной ноги.

Эта информация часто бывает полезна при работе с деревьями в ваших алгоритмах.

person Lima Romeo    schedule 08.10.2017

arrow_upward
-1
arrow_downward

Обратите внимание, что информация о почтовом заказе также присутствует в вашем туре Эйлера. Если просто перечислить каждый узел в последний раз, когда он указан, мы получим

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

К сожалению, мы не можем получить симметричный порядок из тура. В вашем примере это ясно из взгляда на узел E и его дочерний элемент F, мы никак не можем увидеть, является ли дочерний элемент левым или правым.

Метод обхода Эйлера можно немного расширить, включив в него три рекурсивных порядка дерева (до-в-пост-). Следуйте контуру дерева и посещайте каждый узел три раза, прежде чем войти в левый дочерний элемент, между левым и правым дочерними элементами и после правого дочернего элемента. Если ребенок пропал, посещайте его последовательно.

Мы можем расширить ваш пример следующим образом, добавив числа к вашему предыдущему туру:

A1 -> B1 -> C123 -> B2 -> D123 -> B3 -> A2 -> E12 -> F123 -> E2 -> A3
person Hendrik Jan    schedule 26.04.2020