Что такое поиск в ширину
При работе с двоичным деревом поиска в качестве программиста вас попросят или потребуют пройти через узлы. Одна концепция, которую вы хотите иметь в своем арсенале, - это метод «поиска в ширину». Основной метод для этого - начать с корневого узла и добавить все дополнительные узлы справа или слева в очередь. После добавления в очередь он может быть помещен в последний массив. Этот метод используется для поиска кратчайшего пути в графе.
Как это работает
Чтобы запустить этот метод, нам нужно отработать двоичное дерево. Создайте переменную и установите ее равной корневому узлу. Вот как это выглядит ниже.
BFS(){ let currentNode = this.root }
Кроме того, мы создадим еще две переменные и установим обе в пустые массивы. Причина этого, как объяснялось ранее, мы добавим узлы в очередь, которые затем будут добавлены в массив результатов. Кроме того, мы начнем с помещения корневого узла в очередь. Вот наглядный пример ниже.
BFS(){ let currentNode = this.root let queue = [] let result = [] queue.push(currentNode) }
На этом конкретном шаге мы инициируем обход, перебирая очередь. Создайте цикл while, который принимает аргумент queue.length. Если очередь пуста, цикл не запустится.
BFS(){ let currentNode = this.root let queue = [] let result = [] queue.push(currentNode) while(queue.length){ } }
Как только цикл будет запущен, мы установим переменную, которая была у нас ранее для текущего узла, на queue.shift, что удалит узел в очереди.
BFS(){ let currentNode = this.root let queue = [] let result = [] queue.push(currentNode) while(queue.length){ currentNode = queue.shift() } }
Мы добавим это текущее значение узла к результату. Вот лучший пример ниже.
BFS(){ let currentNode = this.root let queue = [] let result = [] queue.push(currentNode) while(queue.length){ currentNode = queue.shift() result.push(currentNode.value) } }
Последние шаги - добавить условие как для левого, так и для правого узлов. Если условие выполнено, оно будет добавлено в очередь. Кроме того, последний шаг - вернуть окончательный / результирующий массив.
BFS(){ let currentNode = this.root let queue = [] let result = [] queue.push(currentNode) while(queue.length){ currentNode = queue.shift() result.push(currentNode.value) if(currentNode.left) queue.push(currentNode.left) if(currentNode.right) queue.push(currentNode.right) } return result }
Большое спасибо за чтение, следите за новостями о поиске в глубину.