Что такое поиск в ширину

При работе с двоичным деревом поиска в качестве программиста вас попросят или потребуют пройти через узлы. Одна концепция, которую вы хотите иметь в своем арсенале, - это метод «поиска в ширину». Основной метод для этого - начать с корневого узла и добавить все дополнительные узлы справа или слева в очередь. После добавления в очередь он может быть помещен в последний массив. Этот метод используется для поиска кратчайшего пути в графе.

Как это работает

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

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
}

Большое спасибо за чтение, следите за новостями о поиске в глубину.