Обход дерева: как прочитать всё, что в нём есть

Если ты знаешь три обхода в глубину (inorder/preorder/postorder), для чего каждый нужен, и что обход в ширину идёт по уровням через очередь, листай до «Теперь сам».

Как думаешь, в каком порядке перечислять узлы дерева

У массива всё ясно: слева направо. У дерева - развилка на каждом узле, и «перечислить все» можно по-разному. Спуститься сначала в левую ветку до дна, потом вернуться? Или пройти по уровням, как читают строки? И главное - КОГДА обрабатывать сам узел: до того как уйти к детям, между детьми или после? Оказывается, этот выбор («когда трогать узел») - не мелочь: от него зависит, в каком порядке выйдут данные, а значит и для чего обход годится. Один порядок даёт отсортированный список, другой - готовый «слепок» дерева для копии, третий - безопасное разрушение. Разберём, какой когда.

На что это похоже

Обход комнат в доме. Можно идти в ГЛУБИНУ: зашёл в комнату, сразу нырнул в дальнюю дверь, до упора, потом назад и в следующую - так обходят лабиринт, держась одной стены. А можно в ШИРИНУ: сначала все комнаты первого этажа, потом все второго - как пожарный проверяет здание по этажам. И в глубину есть выбор: отметить комнату галочкой на ВХОДЕ, или только когда осмотрел все внутренние, на ВЫХОДЕ. От этого зависит, в каком порядке появится твой список комнат - и, скажем, разбирать дом (сносить) надо с дальних комнат к выходу, а составлять опись - можно с порога.

Механизм: три DFS и один BFS

Обходы в глубину (DFS) - рекурсия по поддеревьям; различаются МЕСТОМ, где «посещаем» узел:

симметричный(узел):   # inorder - левое, УЗЕЛ, правое
    если узел пуст: выход
    симметричный(узел.лево); посетить(узел); симметричный(узел.право)

прямой(узел):         # preorder - УЗЕЛ, левое, правое
    если узел пуст: выход
    посетить(узел); прямой(узел.лево); прямой(узел.право)

обратный(узел):       # postorder - левое, правое, УЗЕЛ
    если узел пуст: выход
    обратный(узел.лево); обратный(узел.право); посетить(узел)

Обход в ширину (BFS) - по уровням, без рекурсии, через ОЧЕРЕДЬ:

в_ширину(корень):
    очередь = [корень]
    пока очередь не пуста:
        узел = взять из начала очереди
        посетить(узел)
        добавить в очередь узел.лево и узел.право (непустые)

Каждый узел посещается ровно один раз - любой обход Θ(n). Глубина рекурсии DFS - до O(h) (стек вызовов), BFS хранит в очереди до целого уровня (O(n) в худшем).

Правило

Обход перечисляет все узлы дерева за Θ(n). Три обхода в ГЛУБИНУ различаются местом посещения узла: СИММЕТРИЧНЫЙ (левое-узел-правое) для BST даёт ключи по возрастанию; ПРЯМОЙ (узел-левое-правое) годится для копирования/сохранения структуры; ОБРАТНЫЙ (левое-правое-узел) - для безопасного удаления (сначала дети). Обход в ШИРИНУ (BFS) идёт по уровням через очередь. DFS тратит O(h) на стек рекурсии, BFS - до O(n) на очередь (целый уровень).

Разбор: почему симметричный обход BST выдаёт возрастание, а прямой - нет

Секрет - в инварианте BST и в том, КОГДА выписывается узел. Симметричный: сначала ВСЁ левое поддерево (а оно всё меньше узла), потом узел, потом ВСЁ правое (оно всё больше). Значит для любого узла меньшие выходят раньше, большие - позже, и так рекурсивно - выходит полный порядок по возрастанию. Прямой обход выписывает УЗЕЛ ПЕРВЫМ, до поддеревьев: корень 8 окажется в начале списка (8 3 1 6 10), хотя это не наименьший элемент, - порядок не отсортированный. Зато у прямого своё достоинство: он выписывает узел РАНЬШЕ детей, поэтому, читая такой список, можно воссоздать дерево сверху вниз (сначала родитель, под него дети) - удобно для сохранения и восстановления структуры. Один и тот же обход-каркас, а «когда трогаем узел» решает, порядок это или структура.

Разбор: почему для удаления дерева нужен именно обратный обход

Удаляя (освобождая память) целое дерево, нельзя сначала удалить узел, а потом лезть к его детям - ссылка на детей пропадёт вместе с узлом, и они «утекут» (потеряются, оставшись в памяти без ссылок). Обратный обход (postorder) решает это: он посещает узел ПОСЛЕДНИМ, уже обойдя и освободив оба поддерева. То есть к моменту удаления узла его детей уже нет - удалять безопасно, ничего не теряется. Тот же принцип «сначала дети, потом родитель» работает везде, где узел зависит от результата детей: посчитать размер поддерева, высоту, сумму - всё это обратный обход (значение узла складывается из уже посчитанных детей). Симметричный - для порядка, прямой - для структуры сверху вниз, обратный - для «свести детей в родителя». Выбор обхода - это выбор, в каком направлении течёт информация.

Что ломается без этого

Первая ошибка - ждать отсортированного вывода от ЛЮБОГО обхода: только симметричный (inorder) и только на BST даёт возрастание; прямой и обратный - нет. Вторая - удалять дерево прямым или симметричным обходом: освободишь узел раньше детей - потеряешь поддерево (утечка). Для удаления и для «свёртки снизу вверх» - обратный. Третья - делать BFS без очереди (например, рекурсией): не выйдет обход по уровням, нужна именно очередь FIFO. Четвёртая - забыть про глубину рекурсии: на вырожденном дереве (h = n) DFS-рекурсия может переполнить стек - иногда её пишут циклом с явным стеком.

Зачем это в работе

Обходы - это то, как вообще «работают со всем деревом». Симметричный обход BST - штатный способ получить все элементы упорядоченного множества по порядку (перечислить std::map - это он) и основа диапазонных запросов «все ключи от a до b». Прямой обход сериализует дерево (сохранить в файл, передать по сети) и копирует его. Обратный - освобождает память (в языках без сборщика мусора) и вычисляет «свёрточные» характеристики: размер поддерева, высоту, суммы - на них стоят дополненные деревья (глава дальше в этом разделе). Обход в ширину - основа поиска кратчайшего пути в невзвешенном графе (раздел про графы) и построения дерева «по уровням». Знать четыре обхода и их назначение - значит уметь выбрать правильный порядок под задачу, а не перебирать наугад: направление, в котором течёт информация (сверху вниз или снизу вверх), и диктует обход.

Теперь сам

Дерево: корень 5, левый ребёнок 2 (у него правый ребёнок 4), правый ребёнок 7. Выпиши симметричный и обратный обходы. Почему симметричный дал возрастание, а обратный - нет?