Здесь мы обсудим алгоритм реализации поиска в глубину.
Мы должны указать узел, который будет содержать значение и ссылку на левого и правого дочерних элементов, чтобы создать дерево.
Для определения дерева первым узлом является корневой узел (т. е. a).
Левый или правый дочерний элемент может быть узлом, поддеревом или нулевым значением.
Если узел не содержит ни левого, ни правого дочернего элемента, он называется конечным узлом (т. е. d, e, f, g).
Чтобы определить узел, мы будем использовать класс JavaScript.
При определении узла хранится только значение. левый и правый потомки равны нулю.
Здесь мы создали отдельные узлы.
Здесь мы создали дерево, как показано на Рис. 1.
Итак, мы создали дерево и теперь перейдем к алгоритму.
Таким образом, существует два основных метода определения алгоритма DFS:
- Итерационный метод
- Рекурсивный метод
Итеративный метод
В итеративном методе в качестве структуры данных используется стек, поскольку он работает по принципу LIFO.
LIFO – это сокращение от слова последним пришел, первым ушел. Это метод обработки структур данных, при котором первый элемент обрабатывается последним, а последний элемент обрабатывается первым.
- Мы начнем с предоставления корневого узла, с которого начинается обход.
- Стек проверяется до тех пор, пока он не станет полностью пустым.
- Пометить последний добавленный узел как текущий узел и поместить значение в массив результатов.
- Если у текущего есть правильный потомок, то будет пройдено правое поддерево.
- Если у текущего есть левый дочерний элемент, то будет пройдено левое поддерево.
Примечание. Хотя вывод может измениться, если сначала вызвать левое поддерево, а затем правое поддерево, оба варианта останутся действительными.
например. Вывод с текущим подходом: [a, b, d, e, c, f, g]
если мы изменим порядок: [a, c, g, f, b, e, d]
Рекурсивный метод
- Базовое условие, когда узел не имеет левого и правого дочерних элементов.
- Мы инициализируем его пустым массивом, просматриваем левое и правое поддерево и добавляем результат в массив.
- В результате значение узла, левый подмассив и правый подмассив будут объединены.
Ознакомьтесь с частью 1, чтобы лучше понять DFS.
