Алгоритмы с нуля
Обходы дерева
Вы знаете, как ходить влево и вправо по дереву, следуя указателям. Но в каком порядке вы посещаете узлы? Смотрите на узел в первую очередь, или исследуете его детей сначала? Разные порядки отвечают на разные вопросы. Посетите узел раньше его детей — и вы сможете построить копию сверху вниз. Посетите узел после его левого ребёнка в двоичном дереве поиска — и вы получите отсортированный порядок. Посетите его после обоих детей — и вы сможете вычислить результаты поддерева снизу вверх. Этот урок учит три канонических порядка и почему вы выбрали бы каждый.
После этого урока вы сможете написать три обхода в глубину (прямой, симметричный и обратный порядки) как рекурсивные функции, проследить каждый на конкретном дереве, чтобы предсказать порядок посещения, объяснить, когда и почему используется каждый, и распознать, когда задача требует определённого порядка обхода.
Что такое обход?
Обход — это систематическое посещение каждого узла в дереве. Порядок, в котором вы посещаете узлы, имеет значение, потому что он определяет, какая информация доступна при обработке каждого узла.
Существует много порядков обхода, но три наиболее распространённых — это обходы в глубину, которые посещают корень раньше, чем исследуют всех его потомков. Они различаются когда корень посещается относительно его детей:
- Прямой порядок: посетить корень, потом левое поддерево, потом правое. (Узел, Левое, Правое)
- Симметричный порядок: посетить левое поддерево, потом корень, потом правое. (Левое, Узел, Правое)
- Обратный порядок: посетить левое поддерево, потом правое, потом корень. (Левое, Правое, Узел)
Все три — рекурсивные: чтобы обойти дерево, обработайте корень согласно порядку, потом рекурсивно обойдите левое и правое поддеревья.
Почему три разных порядка?
Каждый порядок — это инструмент для разных задач. Прямой порядок обрабатывает родителя раньше его детей (полезно для копирования дерева или отметки расстояния от корня). Симметричный порядок в двоичном дереве поиска даёт отсортированный порядок — значение узла выводится между всеми меньшими значениями (в левом поддереве) и всеми большими значениями (в правом поддереве). Обратный порядок обрабатывает родителя после обоих детей (полезно для удаления дерева или вычисления высот поддеревьев). Выбор зависит от того, нужна ли вам информация от предков, отсортированный вывод или результаты от потомков.
Прямой порядок: обработка корня в первую очередь
В прямом порядке посетите текущий узел, потом рекурсивно обойдите его левое поддерево, потом его правое поддерево.
1
function preOrder(node) {
2
if (node === null) return;
3
4
// Посетить (обработать) узел
5
console.log(node.value);
6
7
// Обойти левое поддерево
8
preOrder(node.left);
9
10
// Обойти правое поддерево
11
preOrder(node.right);
12
}
- L1 Рекурсивная функция: принимает узел (или null для пустого поддерева).
- L2 Базовый случай: если узел null, нечего посещать.
- L5 Посетить текущий узел (здесь вывести его значение).
- L8 Рекурсивно обойти левое поддерево.
- L11 Рекурсивно обойти правое поддерево.
Пример: Для дерева:
1
/ \
2 3
/
4Прямой порядок посещает в этом порядке: 1 → 2 → 4 → 3.
Симметричный порядок: посещение узла между его детьми
1
function inOrder(node) {
2
if (node === null) return;
3
4
// Обойти левое поддерево
5
inOrder(node.left);
6
7
// Посетить (обработать) узел
8
console.log(node.value);
9
10
// Обойти правое поддерево
11
inOrder(node.right);
12
}
- L1 Рекурсивная функция: принимает узел (или null для пустого поддерева).
- L2 Базовый случай: если узел null, нечего посещать.
- L5 Рекурсивно обойти левое поддерево в первую очередь.
- L8 Посетить текущий узел после его левого поддерева.
- L11 Рекурсивно обойти правое поддерево.
Пример: Для того же дерева:
1
/ \
2 3
/
4Симметричный порядок посещает в этом порядке: 4 → 2 → 1 → 3.
Обратный порядок: посещение узла после обоих детей
1
function postOrder(node) {
2
if (node === null) return;
3
4
// Обойти левое поддерево
5
postOrder(node.left);
6
7
// Обойти правое поддерево
8
postOrder(node.right);
9
10
// Посетить (обработать) узел
11
console.log(node.value);
12
}
- L1 Рекурсивная функция: принимает узел (или null для пустого поддерева).
- L2 Базовый случай: если узел null, нечего посещать.
- L5 Рекурсивно обойти левое поддерево.
- L8 Рекурсивно обойти правое поддерево.
- L11 Посетить текущий узел после обоих поддеревьев.
Пример: Для того же дерева:
1
/ \
2 3
/
4Обратный порядок посещает в этом порядке: 4 → 2 → 3 → 1.
Запуск всех трёх на конкретном дереве
1
let root = new Node(1, new Node(2, new Node(4)), new Node(3));
2
preOrder(root);
1
let root = new Node(1, new Node(2, new Node(4)), new Node(3));
2
inOrder(root);
1
let root = new Node(1, new Node(2, new Node(4)), new Node(3));
2
postOrder(root);
Сложность по времени
Каждый из трёх обходов посещает каждый узел в дереве ровно один раз. Если дерево имеет n узлов, мы делаем n посещений плюс рекурсивные вызовы для достижения этих узлов. Каждый узел обрабатывается один раз, поэтому время O(n) для всех трёх обходов.
Сложность по памяти
Используемая память — это глубина стека вызовов. Когда рекурсия идёт вниз по дереву, каждый рекурсивный вызов остаётся в стеке вызовов до его возврата. Максимальная глубина стека вызовов равна высоте дерева, h.
- Лучший случай (сбалансированное дерево): O(log n) памяти для высоты log n.
- Худший случай (цепь): O(n) памяти для высоты n (если каждый узел имеет только одного ребёнка).
В типичных сбалансированных деревьях O(log n) памяти. В искривлённых деревьях O(n) памяти.
Для дерева: 2 / \ 1 3 Какой из этих это прямой порядок?
Для того же дерева, какой из этих это симметричный порядок?
Для того же дерева, какой из этих это обратный порядок?
Когда вы обходите двоичное дерево поиска симметричным порядком, какое свойство имеет вывод?
Прямой порядок наиболее полезен для какой задачи?
lesson.inset.undefined
Не путайте названия порядков. Pre- означает «раньше» (посетить узел раньше детей). Post- означает «после» (посетить после детей). In- означает «между» (посетить между левым и правым детьми). Мнемоника: Pre (PREсентировать корень), In (In между), Post (POST-датировано, прибывает последним).
lesson.inset.undefined
Проследите сами. Нарисуйте двоичное дерево с 5 узлами. Для каждого обхода (прямой, симметричный, обратный) проследите порядок посещения вручную. Запишите последовательность. Это самый быстрый способ закрепить различия в порядках.
lesson.inset.undefined
Пустые деревья и одиночные узлы. Если дерево пусто (null), обход ничего не делает. Если дерево состоит из одного узла без детей, все три обхода посещают только этот узел. Граничные случаи делают хорошие тестовые входы.
Почему нам нужны три разных порядка обхода вместо одного?
Обход — это систематическое посещение каждого узла в дереве. Три обхода в глубину различаются когда они посещают узел относительно его детей. Прямой порядок посещает узел в первую очередь, потом левое, потом правое (полезно для копирования, обработки сверху вниз). Симметричный порядок посещает левое, узел, правое (даёт отсортированный порядок в дереве поиска). Обратный порядок посещает левое, правое, узел (полезно для удаления, вычисления результатов поддерева снизу вверх). Все три рекурсивны: обработайте корень согласно порядку, потом рекурсивно обойдите поддеревья. Все три работают в O(n) времени (посетите каждый узел один раз) и O(h) памяти (глубина рекурсии равна высоте дерева). Следующий урок охватывает обход уровень за уровнем (поиск в ширину), который использует очередь вместо рекурсии.