#data-structures #tree #tree-traversal #graph-traversal #preorder
#структуры данных #дерево #обход дерева #обход графика #предварительный заказ
Вопрос:
Я пытаюсь узнать об алгоритме обхода Эйлера и почему он популярен для обхода дерева. Однако я не вижу разницы между обходом Эйлера и обходом по предварительному заказу дерева.
Допустим, у вас есть дерево:
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 к счетчику для каждого переднего отрезка и вычитая 1 для каждого обратного отрезка.
Эта информация часто полезна при работе с деревьями в ваших алгоритмах.
Ответ №2:
Обратите внимание, что информация о последующем заказе также присутствует в вашем туре Эйлера. Если просто перечислить каждый узел в последний раз, когда он указан, мы получим
C -> D -> B -> F -> E -> A
К сожалению, мы не можем получить inorder (симметричный порядок) из тура. В вашем примере это ясно из рассмотрения узла E и его дочернего F элемента, мы никак не можем увидеть, является ли дочерний элемент левым или правым.
Метод обхода Эйлера можно немного расширить, включив в него три рекурсивных порядка дерева (pre- in- post-). Следуйте контуру дерева и посетите каждый узел три раза, перед вводом левого дочернего элемента, между левым и правым дочерними элементами и после правого дочернего элемента. Если дочерний элемент отсутствует, выполните последовательные посещения.
Мы можем расширить ваш пример следующим образом, добавив числа к вашему предыдущему туру:
A1 -> B1 -> C123 -> B2 -> D123 -> B3 -> A2 -> E12 -> F123 -> E2 -> A3