Обходы деревьев: DFS и BFS

Цели урока

• Освоить три DFS обхода: inorder, preorder, postorder
• Понять когда использовать какой обход
• Реализовать BFS через очередь
• Научиться выбирать обход под задачу

Предварительные знания

• Введение в деревья
• Очереди

• Введение в деревья
• Очереди

У вас есть дерево с миллионом файлов. Как найти самый большой? Как скопировать всю структуру? Как удалить безопасно? Ответ - в правильном порядке обхода.

• Файловые системы - рекурсивный обход папок
• DOM - querySelector использует DFS
• React - reconciliation через preorder
• Git - обход дерева коммитов

Имена обходов и трюк O(1) памяти

Названия pre-order, in-order и post-order описывают, когда именно мы посещаем сам узел: до детей, между ними или после. Эту терминологию закрепил Дональд Кнут, привязав её к порядку, в котором рекурсия касается узла. Естественная запись обхода рекурсивна, но её можно переписать через явный стек, чтобы не зависеть от глубины вызовов. В 1979 году Джозеф Моррис показал ещё более экономный приём: его обход (Morris traversal) проходит дерево in-order, используя лишь O(1) дополнительной памяти за счёт временных нитей (threads) к преемнику, которые алгоритм аккуратно ставит и снимает. Это наглядный пример размена между памятью и простотой кода, который мы обсуждаем в уроке.

Зачем обходить дерево?

**Обход (traversal)** - посещение каждого узла дерева ровно один раз в определённом порядке.

**Задачи:**

• Напечатать все элементы
• Найти сумму/максимум
• Преобразовать дерево в массив
• Сериализация для хранения

**Два семейства обходов:**

• **DFS (Depth-First)** - идём вглубь: inorder, preorder, postorder
• **BFS (Breadth-First)** - по уровням слева направо

Inorder: Левый -> Корень -> Правый

**Inorder (симметричный):** сначала левое поддерево, потом корень, потом правое.

**Свойство:** для BST (Binary Search Tree) inorder даёт отсортированную последовательность.

Preorder: Корень -> Левый -> Правый

**Preorder (прямой):** сначала корень, потом левое, потом правое.

**Применения:**

• Копирование дерева
• Сериализация (легко восстановить)
• Вычисление выражений в префиксной нотации

Postorder: Левый -> Правый -> Корень

**Postorder (обратный):** сначала оба поддерева, потом корень.

**Применения:**

• Удаление дерева (сначала дети, потом родитель)
• Вычисление размера папок (сначала подпапки)
• Постфиксная нотация выражений

BFS: Обход по уровням

**BFS (Breadth-First Search):** посещаем все узлы уровня, прежде чем перейти к следующему.

**Реализация через очередь:**

**BFS использует очередь (FIFO)**, DFS использует стек (или рекурсию).

Шпаргалка по обходам

• **Inorder (L-Root-R):** отсортированный вывод BST
• **Preorder (Root-L-R):** копирование, сериализация
• **Postorder (L-R-Root):** удаление, подсчёт размеров
• **BFS:** обход по уровням, поиск кратчайшего пути

Следующие темы

Обходы освоены! Теперь BST - дерево для быстрого поиска.

• Binary Search Tree — Дерево для поиска O(log n)
• Сбалансированные деревья — Гарантированный O(log n)

Связанные уроки

• ds-09-trees-intro — Tree structure must be understood before traversal
• ds-11-bst — In-order traversal of BST yields sorted output
• ds-03-stacks — Iterative DFS traversal uses an explicit stack
• ds-04-queues — BFS level-order traversal uses a queue
• comp-20-semantic-passes