Если вы не читали двоичное дерево, вы можете сначала прочитать приведенное ниже.
Теперь, когда мы немного знаем о деревьях или, по крайней мере, бинарных деревьях, следующая тема - обход дерева. Обход дерева означает просто посещение каждого узла. Наиболее распространенными способами перемещения по дереву являются поиск в ширину и поиск в глубину. Мы будем называть их BFS и DFS.
BFS - это горизонтальный поиск, а DFS - вертикальный. У DFS есть три способа реализации: упорядоченная DFS; предварительный заказ DFS; пост-заказ DFS. Это помогает думать об обходе как о печати значений узла в определенном порядке, основанном на типе обхода, который мы выбираем. В этой статье мы обратимся к BFS.
Чтобы реализовать этот метод в JavaScript, мы будем использовать структуру данных, называемую очередью. Очередь - это не более чем простая линия. Мы встаем в очередь, чтобы заплатить за наши товары, когда делаем покупки в магазине, мы встаем в очередь, чтобы войти в кинотеатр, чтобы посмотреть наши фильмы. Единственные свойства линии или очереди, которые нас интересуют, - это способ входа в линию и выхода из нее.
При реализации нашей очереди в JavaScript мы будем использовать массив. Чтобы войти в этот массив, мы используем метод push, чтобы выйти из строки, мы используем метод shift. Эти методы соответствуют ограничениям нашей простой линии: выход спереди, вход сзади.
Случаи, которые мы должны учитывать при реализации нашей BFS, следующие: Во-первых, если отсутствует корень, это означает, что у нас есть пустая структура, поэтому мы вернем null; во-вторых, если у нас есть узел, есть ли у нас узел слева или справа от этого узла, если нет, мы посетили каждый узел, если есть, мы должны посетить этот узел. Чтобы выполнить эту логику, мы должны:
- Следите за нашей очередью
- Следите за нашими посещенными узлами
Мы будем использовать другой массив для отслеживания посещенных узлов, но вместо того, чтобы сохранять узел, мы просто сохраним значения этого узла, чтобы вернуть «распечатанный» список узлов, присутствующих в нашем дереве.
Логика следующая. Мы начинаем с корня, берем этот узел и добавляем его в нашу очередь. Пока у нас есть что-то в нашей очереди, мы будем следовать этим шагам, чтобы убедиться, что мы посетили все узлы и успешно завершили нашу BFS. Как было сказано ранее, в нашей очереди находится только корень. Мы удалим его из очереди и назовем текущим. Это наш текущий узел.
Мы возьмем текущий узел и посмотрим, есть ли у него левый узел, если есть, мы возьмем этот левый узел и добавим его в нашу очередь. Затем мы посмотрим, есть ли у него правильный узел, если он есть, мы добавим его в нашу очередь. Затем мы возьмем текущее значение и поместим его в посещенный массив. Добавив в этот массив, мы сохранили наше первое значение «print». Мы делаем это повторно, пока не исчерпаем нашу очередь. Процесс заканчивается, когда у нас больше нет правых или левых дочерних элементов для размещения в нашей очереди, к этому времени в нашем посещенном массиве есть все «напечатанные» значения, которые мы можем вернуть для завершения нашей BFS.
Ниже представлена реализация, вы можете попробовать ее в своем любимом редакторе.
