Поиск сначала дыханием против поиска в глубину

Дерево - это нелинейная структура данных - совокупность узлов, соединенных направленными (или неориентированными) ребрами. Каждый узел содержит значение, а соединение между узлами называется ребрами. Самый верхний узел называется корневым, узел без дочерних узлов - листовым узлом. Узлы с одним и тем же родителем называются братьями и сестрами. Глубина узла - это количество ребер от корня до узла, а высота узла - это количество ребер от узла до самого глубокого листа.

Как мы можем посетить каждый узел в дереве? Распространенными алгоритмами обхода дерева являются поиск в ширину (BFS) и поиск в глубину (DFS).

Поиск в ширину

С помощью BFS мы посещаем узлы поэтапно. Мы исследуем ширину, то есть полную ширину дерева на заданном уровне, прежде чем углубиться.

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

Поиск в глубину

Алгоритм начинается с корневого узла и исследует, насколько это возможно, каждую ветвь перед обратным отслеживанием.

Есть три распространенных способа:

  • По порядку (слева, корень, справа): A, D, F, H, J, K, Z.
  • Предварительный заказ (корень, слева, справа): J, F, A, D, H, K, Z
  • Пост-заказ (слева, справа, корень): D, A, H, F, Z, K, J

В DFS мы используем рекурсию для реализации.

В порядке:

Предварительный заказ:

Пост-заказ:

Как мы решаем, какой из них использовать? Ответ прост: это зависит от дерева. Рассмотрев структуру дерева, временную и пространственную сложность, мы можем выбрать одно. Например, для длинного и одностороннего одностороннего дерева лучше всего использовать DFS, потому что мы просто храним узлы в соответствии с глубиной, а не шириной; Если у нас много уровней, братьев и сестер, которые нужно отслеживать, BFS работает лучше.

Обход дерева может быть сложной задачей, надеюсь, эта статья может помочь 😉

Ссылки:



Древовидная структура данных
Существует множество базовых структур данных, которые можно использовать для решения проблем приложений. Массив - хорошие статические данные… www.cs.cmu.edu





Мастер-класс по алгоритмам JavaScript (JS) и структурам данных
Привет! Я Кольт. Я разработчик с серьезной любовью к преподаванию. Последние несколько лет я учил людей… www.udemy.com





Структура данных и алгоритмы - обход дерева
Обход - это процесс посещения всех узлов дерева и может также распечатать их значения. Потому что все узлы… www.tutorialspoint.com



JavaScript на простом английском языке

Понравилась эта статья? Если да, то получите больше похожего контента, подписавшись на наш канал на YouTube в Decoded!