Обход бинарного дерева: inorder, preorder и postorder

Введение

Бинарные деревья — одна из самых распространённых структур данных. Бинарное дерево поиска (BST) хранит узлы так, что левый ребёнок меньше родителя, а правый — больше. Это свойство даёт эффективный доступ и простые алгоритмы обхода.

Определение: обход — посещение каждого узла дерева ровно один раз в некотором порядке.

В этой статье подробно разберём три способа обхода BST: inorder, preorder и postorder. Покажем алгоритмы, визуализации, пример на Python, сложности по времени и памяти, а также полезные приёмы, альтернативы и тесты.

Important: если дерево не сбалансировано, характеристики памяти/времени могут деградировать до худших случаев — это обсуждается в разделе о крайних ситуациях.

Основные понятия

• Узел: структура с полями left, right и value.
• Корень: верхний узел дерева.
• Высота дерева h: число рёбер от корня до наиболее удалённого листа.
• n: число узлов в дереве.

Inorder (симметричный) обход

Inorder — это рекурсивное посещение: сначала левое поддерево, затем корень, затем правое поддерево. Для BST результатом будет отсортированная последовательность значений по возрастанию.

Алгоритм

1. Рекурсивно обойти левое поддерево.
2. Посетить корень.
3. Рекурсивно обойти правое поддерево.

Визуализация

На рисунке корень 56. Порядок обхода: сначала поддерево 32 (28 -> 32 -> 44), затем 56, затем поддерево 62 (58 -> 62 -> 88). Итог: 28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88.

Применение

• Получение элементов BST в порядке возрастания.
• Вычисление инфиксной формы выражений в деревьях выражений.
• Используется при медианах, обходе диапазона (range queries): если нужно вывести значения в заданном интервале, можно обходить inorder и фильтровать.

Preorder обход

Preorder посещает сначала корень, затем левое и правое поддеревья.

Алгоритм

1. Посетить корень.
2. Рекурсивно обойти левое поддерево.
3. Рекурсивно обойти правое поддерево.

Визуализация

Для примера дерево обходит узлы в порядке: 56 -> 32 -> 28 -> 44 -> 62 -> 58 -> 88.

Применение

• Лёгкое восстановление/копирование структуры дерева: preorder + дополнительная информация о пустых детях позволяет реконструировать дерево.
• Используется в сериализации дерева для передачи по сети или сохранения на диск.

Postorder обход

Postorder посещает сначала левое поддерево, затем правое, и в конце корень.

Алгоритм

1. Рекурсивно обойти левое поддерево.
2. Рекурсивно обойти правое поддерево.
3. Посетить корень.

Визуализация

Порядок обхода для примера: 28 -> 44 -> 32 -> 58 -> 88 -> 62 -> 56.

Применение

• Удаление дерева от листьев к корню без утечек: постфиксный порядок гарантирует, что сначала удаляются дети, затем родитель.
• Получение постфиксной (польской обратной) записи выражений.

Итеративные и оптимизированные альтернативы

1. Итеративный обход с собственным стеком: подходит там, где глубина рекурсии ограничена или рекурсия нежелательна.
2. Morris traversal (inorder) — обход без рекурсии и без стека, использующий временные указатели; работает за O(n) времени и O(1) дополнительной памяти, но модифицирует дерево во время обхода и требует аккуратного восстановления.
3. Генераторы/потоки: ленивый импорт или yield в Python для выдачи последовательности элементов по мере обхода.

Когда использовать каждую альтернативу:

• Небольшие деревья: рекурсия проще и читабельнее.
• Ограниченная память или глубокие деревья: итеративный стек или Morris.
• Если нужно прерывать обход по условию (например, найти k-й элемент): итеративный или ленивый обход удобнее.

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

• Время для всех трёх вариантов: O(n), где n — число узлов.
• Память: O(h) для рекурсивного варианта и для итеративного со стеком, где h — высота дерева. В худшем случае (выраженная линейная цепочка) h = n и память — O(n). Morris traversal даёт O(1) дополнительной памяти, но требует временной модификации дерева.

Краткая таблица (качественно):

• Рекурсивный inorder/preorder/postorder: время O(n), память O(h).
• Итеративный с стеком: время O(n), память O(h).
• Morris (inorder): время O(n), память O(1), модификация дерева во время обхода.

Python: реализация всех трёх обходов

Ниже пример программы на Python, реализующий inorder, preorder и postorder. Комментарии приведены на русском.

# Класс Node для создания узлов BST
class Node:
    def __init__(self, element):
        self.left = None
        self.right = None
        self.value = element

# Обход inorder (лево, корень, право)
def inorder(root):
    if root:
        inorder(root.left)
        print(str(root.value) + ', ', end='')
        inorder(root.right)

# Обход postorder (лево, право, корень)
def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(str(root.value) + ', ', end='')

# Обход preorder (корень, лево, право)
def preorder(root):
    if root:
        print(str(root.value) + ', ', end='')
        preorder(root.left)
        preorder(root.right)

# Создание узлов примера
root = Node(56)
root.left = Node(32)
root.right = Node(62)
root.left.left = Node(28)
root.left.right = Node(44)
root.right.left = Node(58)
root.right.right = Node(88)

print('Inorder Traversal of BST:')
inorder(root)
print('\nPreorder Traversal of BST:')
preorder(root)
print('\nPostorder Traversal of BST:')
postorder(root)

Вывод программы соответствует примерам выше.

Крайние случаи и ошибки

• Пустое дерево: обход должен корректно обрабатывать root = None и ничего не печатать.
• Вырожденное дерево (список): если дерево напоминает связный список, высота h = n, и рекурсивный вызов может вызвать переполнение стека для больших n. Решение: итеративный обход или увеличить предел рекурсии (не рекомендуется в продакшене).
• Мутабельные обходы (Morris): некорректная реализация может оставить указатели изменёнными — всегда проверяйте восстановление структуры.
• Не-BST деревья: Inorder не будет давать отсортированную последовательность, если дерево не обладает свойством BST.

Тесты и критерии приёмки

Критерии приёмки для реализации обходов:

1. Функции возвращают или печатают элементы в ожидаемом порядке для корректного BST примера.
2. Пустое дерево не вызывает ошибок и возвращает пустую последовательность.
3. Для дерева из одного узла все три обхода возвращают последовательности, совместимые с определениями.
4. Итеративная версия даёт тот же порядок, что и рекурсивная, для нескольких случайных деревьев.
5. Morris (при использовании) не меняет структуру дерева после завершения обхода.

Минимальные тесты:

• Пустое дерево.
• Один узел.
• Сбалансированное дерево (пример в статье).
• Вырожденное дерево (все правые или все левые дети).
• Случайное дерево из 1000 узлов (проверка времени и стека).

Роль‑ориентированные чеклисты

Разработчик:

• Проверить корректность для пустого дерева и одиночного узла.
• Добавить unit‑тесты для сбалансированных и вырожденных деревьев.
• Выбрать итеративную или Morris версию при ограниченной памяти.

Интервьюер:

• Попросить объяснить, почему inorder даёт сортировку для BST.
• Попросить реализовать итеративный inorder с явным стеком.
• Попросить оптимизацию памяти (обсудить Morris).

Студент:

• Понять смысл каждого шага в алгоритме и прогнать пример на бумаге.
• Реализовать все три варианта и сравнить выводы.

Ментальные модели и эвристики

• “Левая ветвь означает меньше”: всегда ожидайте, что left < parent < right для BST.
• “Inorder — симметрия”: представьте, что вы заходите в узел после того, как исследовали всё слева.
• “Preorder — сериализация” и “Postorder — очистка”: связывайте порядок с реальной задачей — копирование vs удаление.

Когда обход не подходит и альтернативы

• Для поиска конкретного элемента используйте свойство BST и алгоритм поиска, а не полный обход.
• Для агрегаций (например, сумма значений) можно использовать специализированные структуры (Fenwick, сегментное дерево) если нужно много запросов диапазона.

Безопасность и приватность

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

Сводка

• Inorder даёт отсортированный список значений BST.
• Preorder полезен для копирования/сериализации дерева.
• Postorder помогает при удалении и при получении постфиксных выражений.
• Все три обхода работают за O(n) времени и O(h) памяти в рекурсивном виде.

Notes: если вам нужна экономия по памяти, рассмотрите Morris traversal или ленивые генераторы.

Список ключевых выводов:

• Три фундаментальных порядка обхода покрывают основные потребности работы с деревьями.
• Выбор реализации зависит от ограничений памяти и требований к изменению структуры дерева.
• Всегда тестируйте на пустых и вырожденных деревьях.