Алгоритмы с нуля

Поуровневый обход (BFS)

Суть Посещение узлов слой за слоем, сверху вниз, слева направо, с помощью очереди. Альтернатива обходу в глубину, основанная на поиске в ширину. Почему очереди производят поуровневый обход, основной цикл и ключевой вариант: отслеживание размера очереди в начале каждого уровня.

◷ 22 min

Вы знаете три способа рекурсивно ходить по дереву — прямой, симметричный, обратный — все исследуют глубоко один ветвь, прежде чем вернуться. Но что если вам нужно увидеть все узлы на глубине 2 перед любым на глубине 3? Что если вам нужны узлы сгруппированы по слоям? Обходы в глубину не могут на это ответить. Вам нужен поиск в ширину: обход на основе очереди, который посещает узлы слой за слоем, слева направо, от корня вниз. Это поуровневый обход, и он раскрывает задачи, где позиция и глубина каждого узла имеют значение.

Цель

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

Идея

Что такое поуровневый обход?

Поуровневый обход (также называемый поиск в ширину или BFS) посещает каждый узел в дереве слой за слоем, сверху вниз, слева направо. В отличие от рекурсивных обходов в глубину, которые вы видели в последнем уроке, поуровневый обход использует очередь — контейнер первый вход, первый выход — для управления порядком посещения.

Почему очередь производит поуровневый порядок

Магия поуровневого обхода — это свойство FIFO очереди. Когда вы обрабатываете узел и добавляете его детей в очередь, дети идут в конец очереди. Все узлы на текущем уровне ещё в очереди, впереди их детей. Поэтому вы обрабатываете все узлы на уровне 1, потом все на уровне 2, и так далее — вы никогда не пропускаете вперёд на более глубокий уровень, пока текущий уровень не исчерпан.

Контраст с рекурсией: когда вы вызываете preOrder(node.left), вы сразу же ныряете глубоко в левое поддерево перед тем, как вообще увидеть правого ребёнка. Рекурсия — это обход в глубину. Очередь — это поиск в ширину.

Основной поуровневый цикл

Создайте очередь и добавьте корень.
Пока очередь не пуста:
- Извлеките узел из очереди.
- Обработайте его (запишите его значение).
- Поместите в очередь его левого ребёнка (если он существует).
- Поместите в очередь его правого ребёнка (если он существует).
Готово.

Обработка одного уровня за раз

Часто вам хочется сгруппировать узлы по уровню — все узлы уровня 1 вместе, все узлы уровня 2 вместе. Хитрость: в начале каждого уровня запишите размер очереди. Это число говорит вам ровно, сколько узлов на текущем уровне. Повторите это число раз, извлекая и помещая в очередь детей. Когда вы повторили size раз, все дети (следующий уровень) находятся в очереди, и вы циклируете снова.

Этот вариант необходим для задач, таких как «вернуть поуровневый обход как список списков» или «найти ширину каждого уровня».

Код

Базовый поуровневый обход

Простейшая форма: поместите корень в очередь, потом извлекайте, обрабатывайте и помещайте в очередь детей до тех пор, пока очередь не пуста.


      1
      function levelOrder(root) {
    

      2
      if (root === null) return [];
    

      3
       
    

      4
      const result = [];
    

      5
      const queue = [root]; // Начните с корня
    

      6
       
    

      7
      while (queue.length > 0) {
    

      8
        const node = queue.shift(); // Извлеките из начала
    

      9
        
    

      10
        // Обработайте узел
    

      11
        result.push(node.value);
    

      12
        
    

      13
        // Поместите в очередь детей
    

      14
        if (node.left !== null) queue.push(node.left);
    

      15
        if (node.right !== null) queue.push(node.right);
    

      16
      }
    

      17
       
    

      18
      return result;
    

      19
      }

L1 Функция принимает корень дерева.
L2 Если дерево пусто (null корень), верните пустой результат.
L5 Используйте массив в качестве очереди. Начните с корня.
L7 Циклируйте, пока очередь не пуста.
L8 Извлеките (удалите) узел из начала.
L11 Обработайте узел: запишите его значение.
L14 Поместите в очередь левого ребёнка, если он существует.
L15 Поместите в очередь правого ребёнка, если он существует.
L18 Верните результат: узлы в поуровневом порядке.

Пример: Для дерева:

Поуровневый обход посещает в этом порядке: 1 → 2 → 3 → 4.

Поуровневый обход с группировкой (один уровень за раз)

Чтобы вернуть узлы, сгруппированные по уровню, запишите размер очереди в начале каждой итерации. Этот размер — это количество узлов на текущем уровне.


      1
      function levelOrderByLevel(root) {
    

      2
      if (root === null) return [];
    

      3
       
    

      4
      const result = [];
    

      5
      const queue = [root];
    

      6
       
    

      7
      while (queue.length > 0) {
    

      8
        const levelSize = queue.length; // Сколько узлов на этом уровне
    

      9
        const currentLevel = []; // Узлы этого уровня
    

      10
        
    

      11
        // Обработайте все узлы на текущем уровне
    

      12
        for (let i = 0; i < levelSize; i++) {
    

      13
          const node = queue.shift(); // Извлеките из начала
    

      14
          currentLevel.push(node.value); // Запишите значение узла
    

      15
          
    

      16
          // Поместите в очередь детей для следующего уровня
    

      17
          if (node.left !== null) queue.push(node.left);
    

      18
          if (node.right !== null) queue.push(node.right);
    

      19
        }
    

      20
        
    

      21
        // После обработки levelSize узлов, очередь теперь содержит только следующий уровень
    

      22
        result.push(currentLevel);
    

      23
      }
    

      24
       
    

      25
      return result;
    

      26
      }

L1 Функция возвращает список списков: каждый внутренний список — это один уровень.
L2 Если дерево пусто, верните пустой результат.
L5 Используйте массив в качестве очереди. Начните с корня.
L7 Циклируйте, пока очередь не пуста.
L8 Запишите размер очереди — это количество узлов на текущем уровне.
L11 Цикл от 0 до levelSize: обработайте ровно столько узлов.
L12 Извлеките узел из начала.
L13 Запишите его значение в список текущего уровня.
L16 Поместите в очередь его детей; они будут обработаны в следующей итерации.
L20 После цикла for добавьте узлы текущего уровня в результат.

Пример: Для того же дерева:

Результат: [[1], [2, 3], [4]] — каждый уровень как отдельный список.

Запуск обоих на конкретном дереве

class Node {
constructor(value, left = null, right = null) {
  this.value = value;
  this.left = left;
  this.right = right;
}
}

function levelOrder(root) {
if (root === null) return [];

const result = [];
const queue = [root];

while (queue.length > 0) {
  const node = queue.shift();
  result.push(node.value);
  
  if (node.left !== null) queue.push(node.left);
  if (node.right !== null) queue.push(node.right);
}

return result;
}

function levelOrderByLevel(root) {
if (root === null) return [];

const result = [];
const queue = [root];

while (queue.length > 0) {
  const levelSize = queue.length;
  const currentLevel = [];
  
  for (let i = 0; i < levelSize; i++) {
    const node = queue.shift();
    currentLevel.push(node.value);
    
    if (node.left !== null) queue.push(node.left);
    if (node.right !== null) queue.push(node.right);
  }
  
  result.push(currentLevel);
}

return result;
}

// Построим дерево:
//      1
//     / \
//    2   3
//   /
//  4

let node4 = new Node(4);
let node2 = new Node(2, node4);
let node3 = new Node(3);
let root = new Node(1, node2, node3);

console.log("Простой поуровневый обход:");
console.log(levelOrder(root));

console.log("\nПоуровневый обход по уровням:");
console.log(levelOrderByLevel(root));

Output

Пошаговый разбор


      1
      let root = new Node(1, new Node(2, new Node(4)), new Node(3));
    

      2
      levelOrder(root);


      1
      let root = new Node(1, new Node(2, new Node(4)), new Node(3));
    

      2
      levelOrderByLevel(root);

Сложность

Сложность по времени

Поуровневый обход посещает каждый узел в дереве ровно один раз. Каждый узел извлекается один раз и помещается в очередь один раз. Вся работа, проделанная на узел (обработка, проверки детей), — O(1). Поэтому для дерева с n узлами время O(n).

Сложность по памяти

Место, используемое очередью, — это основной фактор. В любой момент очередь содержит узлы из не более чем двух последовательных уровней. В худшем случае максимальная ширина дерева — наибольшее число узлов на любом отдельном уровне — определяет максимальный размер очереди.

Для дерева с максимальной шириной w сложность пространства — O(w).

В сбалансированном двоичном дереве w — это примерно n / 2 (последний уровень имеет много узлов), поэтому O(w) всё ещё лучше, чем O(n) пространства рекурсии в худшем случае. В искривлённом дереве (где каждый узел имеет только одного ребёнка) w = 1, поэтому поуровневый обход использует O(1) памяти — намного лучше, чем стек рекурсии O(n).

Практика 0 / 5

Для дерева: 5 / \ 3 7 / \ 2 4 Какой поуровневый обход?

Почему очередь производит поуровневый порядок, а рекурсия производит обход в глубину?

В варианте поуровневого обхода 'по уровням', что представляет levelSize?

После обработки levelSize узлов и помещения в очередь всех их детей, что содержит очередь?

Для дерева с максимальной шириной w (самым большим количеством узлов на любом уровне), какова сложность по памяти поуровневого обхода?

lesson.inset.undefined

Почему не рекурсия? Рекурсия исследует в глубину: она идёт полностью вниз по левому поддереву перед исследованием правого. Если вам нужно узнать уровень каждого узла или сгруппировать узлы по глубине, рекурсия скрывает эту структуру. Очередь делает структуру уровня явной: извлеките уровень k, поместите в очередь уровень k+1.

lesson.inset.undefined

Проследите вариант ‘по уровням’ сами. Нарисуйте дерево с 3 уровнями. Для поуровневого обхода ‘по уровням’, нарисуйте состояние очереди после обработки каждого уровня. Смотрите, как levelSize = queue.length запишет количество текущего уровня. Это главная идея.

lesson.inset.undefined

Пустые деревья и одиночные узлы. Если корень null, верните немедленно (пустой результат). Если дерево — одиночный узел, очередь содержит только этот узел, цикл запускается один раз, и готово. Оба случая обработаны алгоритмом без специального кода.

Проверь себя

Викторина

Почему поуровневый обход полезен, даже хотя он и обходы в глубину оба посещают все узлы?

Итог

Поуровневый обход (BFS) посещает узлы слой за слоем, сверху вниз, слева направо, используя свойство FIFO очереди. В отличие от рекурсивных обходов в глубину, поуровневый обход делает структуру слоя дерева явной. Базовый алгоритм: поместите в очередь корень, циклируйте, пока очередь не пуста, извлеките и обработайте узел, потом поместите в очередь его детей. Чтобы сгруппировать узлы по уровню, запишите размер очереди в начале каждой итерации — это число точно говорит вам, сколько узлов на текущем уровне. Сложность по времени O(n) (посетите каждый узел один раз). Сложность по памяти O(w), где w — максимальная ширина дерева — лучше, чем O(n) пространства рекурсии во многих случаях. Следующий урок охватывает рекурсию на деревьях: решение задач на деревьях путём объединения результатов, возвращённых из поддеревьев.

Продолжить восхождение ↑Рекурсия на деревьях