Для двоичного дерева, является ли обход поиска в ширину (BFS) тем же самым, что и обход предварительного заказа? Меня немного смущают эти два разных типа обходов. Может ли кто-нибудь объяснить мне это? Кроме того, как обход предварительного заказа сравнивается с обходом поиска в глубину (DFS)?
Большое спасибо!
Нет, обход предварительного заказа на самом деле является формой обхода поиска в глубину (DFS). Существует три различных формы DFS, а именно:
Чтобы доказать, что обход поиска в ширину (BFS) - это не то же самое, что обход предварительного заказа , я покажу встречный пример ниже:
Чтобы было ясно, двоичное дерево - это не то же самое, что двоичное дерево поиска, а именно двоичное дерево может быть определено как:
Двоичное дерево. Дерево, элементы которого имеют не более двух дочерних элементов, называется двоичным деревом. Обратите внимание, что порядок расположения детей не упоминается.
Хорошо, теперь к контрпримеру, возьмем следующее простое двоичное дерево:
Для предварительного заказа узлы посещаются в следующем порядке: Предварительный заказ: [1,2,4,3]
теперь для обхода поиска в ширину узлы посещаются в следующем порядке:
BFS: [1,2,3,4]
Примечание. Обход предварительного заказа отличается от обхода BFS.
Дополнительную информацию о различных обходах дерева можно найти по этой ссылке.
Надеюсь, это поможет!
Результаты предварительного заказа и BFS одинаковы в двоичном дереве поиска, но не в простом двоичном дереве.
