Обход предварительного заказа такой же, как поиск в глубину?

13

Мне кажется, что обход по предварительному заказу и DFS такие же, как и в обоих случаях, когда мы переходим от корня к левой ветви и обратно к корню, а затем рекурсивно к правой ветви. Может ли кто-нибудь исправить меня, если я ошибаюсь?

Заранее спасибо!

algorithms trees binary-tree graph-traversal Срикант Кандалам
источник

Ответы:

10

обход по предварительному заказу - это обход, он посещает каждый узел в двоичном дереве

Поиск в глубину - это поиск, он идет вокруг произвольного графа, ища определенный узел (что он лучше всего работает в нециклическом графе (он же дерево), не имеет значения)

одно это - большая разница, чтобы называть их разными именами

чокнутый урод
источник
1
+1, но я хотел бы добавить, что обходы до и после заказа - это просто особые случаи более общей стратегии DFS.
Фрэнк
1
Разве предварительный порядок обхода не означает просто обработку узлов перед их дочерними элементами? Где говорится, что узлы образуют двоичное дерево или даже дерево?
Килиан Фот
@KilianFoth Я бы ожидал, что использование узла, имеющего дочерние элементы (в отличие от соседей), подразумевает древовидную структуру, поскольку предполагает иерархию узлов. Вершина иерархии является корнем дерева. Но я могу себе представить, что обход до и после заказа имеет смысл для любого дерева, даже если оно не является двоичным.
YoungJohn
1

Да, но это должно быть наоборот: DFSпохоже на PreOrder.
Термин PreOrderбольше относится к двоичным деревьям и парсерам.
Он используется для сравнения с другими обходными заказами бинарного дерева: InOrder, PostOrderи PreOrder.
Топологическая сортировка аналогична обходу после заказа (вставка узла в стек после посещения всех смежных узлов).

user640554
источник
Мои мысли похожи на этот ответ. Более конкретно, предварительный заказ - это конкретная реализация родительской категории DFS. Детский обход предварительного заказа жестко влево, затем вправо; тогда как для универсальной (родительской) DFS порядок обхода детей не определен и может быть любым.
Джерред С.
-1

Чтобы пройти бинарное дерево в Preorder, выполняются следующие операции

  1. Посетить корень
  2. Пройдите через левое поддерево
  3. Пройдите правое поддерево

То есть на изображении ниже прохождение предварительного заказа будет 1,2,3,6,4,5,7,8,9,10,11,12

На этом же изображении 1,2,3,4,5,6,7,8,9,10,11,12 будет для DFS

Источник DFS: http://datastructuresnotes.blogspot.in/2009/02/binary-tree-traversal-preorder-inorder.html

Предзаказ Источник: Wiki

ДФС

Zedaiq
источник
9
Это не бинарное дерево. Это дерево, но не двоичное.
Manoj R
Что происходит, когда «6» имеет подузлы?
Марьян Венема
Вы просите DFS или предварительный заказ?
Zedaiq
@ManojR Получил от источника, упомянутого выше.
Zedaiq
Предварительный порядок на этом графике дает тот же ответ
Чарльз Чоу