21

Вопрос по algorithm, tree, binary-tree, depth-first-search, preorder – Является ли обход предварительного заказа в двоичном дереве таким же, как поиск в глубину?

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

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

en.wikipedia.org/wiki/Tree_traversal#Depth-first

от Walter Tross
3 ответа
44

Предварительный заказ - это один из типов DFS.

Существует три типа обхода в глубину: предварительный заказ, порядок и пост-заказ.

Проверять, выписыватьсяВот для получения дополнительной информации.

Я думаю, он просто заметил, что когда рассматриваемый граф также является деревом, а исходная вершина для DFS является корнем дерева, тогда DFS и обход предварительного порядка эквивалентны. Упорядоченный обход не имеет смысла для k-арных деревьев, где k> 2.

от Dave

На самом деле существует шесть типов обхода глубины в двоичном дереве - предварительный порядок, последующий порядок, порядок, обратный предварительный порядок, обратный порядок и обратный порядок. Это соответствует шести перестановкам трех операций (3!), В которых операции «идут влево», «идут вправо» и «узел процесса».

от user755921

Даже если бы граф был бинарным деревом, выход обхода дерева предварительного порядка вряд ли будет таким же, как обход предшественника-подграфа, если только списки смежности вершин не будут последовательно перечисляться в том же порядке, что и в виде узла " дети "на дереве. То есть представление графа не имеет понятия «левый» и «правый» потомки.

от Dave

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

от Khaled.K
5

Вероятно

это зависит от определения и реализации алгоритма глубины в первую очередь.DefaultMutableTreeNode Класс компонента Java Swing JTree имеет следующие методы перечисления, используемые для обхода дерева:

depthFirstEnumeration ()postorderEnumeration ()preorderEnumeration ()breadthFirstEnumeration ()

В реализации Java SwingdepthFirstEnumeration такой же, какpostOrderEnumeration, Мои тесты иофициальная документация подтверждает это.

Другие могут по-разному определять, что означает глубина. Например, статья оВикипедия утверждает, что предварительный и последующий обходы являются специфическими типами обхода в глубину. Это будет означать, что обход в глубину не является конкретным алгоритмом обхода.

5

Не будет Предварительный заказ имеет строгую форму посещения левого уз

ла, а затем правого узла. Но для DFS это может быть как, так как нет строгой моды. Таким образом, существует более одного обхода, основанного на том, что вы помещаете в стек.

Похожие вопросы