Ширина при первом поиске Обход по предварительному заказу VS Глубина при первом поиске

Question

Для бинарного дерева Обход поиска в ширину (BFS) совпадает с Обход предзаказа ?Я немного смущен этими двумя типами обходов.Может кто-нибудь, пожалуйста, объясните мне это?Кроме того, как Обход предварительного заказа сравнивается с Обход первого поиска в глубину (DFS)?

Большое вам спасибо!

Answer 1

Нет, обход предварительного заказа на самом деле является формой обхода в глубину при первом поиске (DFS) . Существует три различных формы DFS, а именно:

1. Предзаказ
2. В порядке
3. после заказа

Чтобы доказать, что обратный поиск по ширине (BFS) не совпадает с обходом по предварительному заказу Я покажу контрпример ниже:

Для ясности, двоичное дерево не совпадает с двоичным деревом поиска , а именно двоичное дерево может быть определено как:

Двоичное дерево - Дерево, элементы которого имеют не более 2 дочерних элементов, называется двоичным деревом. Обратите внимание, что нет упоминания о порядке детей.

Хорошо, теперь к контрпримеру возьмем следующее простое двоичное дерево:

Для обхода предварительного заказа узлы посещаются в следующем порядке: Предварительный заказ: [1,2,4,3]

теперь для обхода поиска в ширину узлы посещаются в следующем порядке:

BFS: [1,2,3,4]

Примечание: обход предварительного заказа отличается от обхода BFS.

Для получения дополнительной информации о различных обходах деревьев, перейдите по этой ссылке

Надеюсь, это поможет!