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

Краткое содержание

Кратко: объясняю три классических способа обхода бинарного дерева — inorder, preorder, postorder — с алгоритмами, визуализациями, примерами на Python и практическими советами. Включены итеративные варианты, когда рекурсия не подходит, и чеклисты для инженеров и собеседований.

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

В этом материале подробно разобраны три способа обхода BST: inorder (симметричный), preorder (прямой) и postorder (обратный). Для каждого способа представлены определение, пошаговый алгоритм, визуализация, области применения, итеративные реализации, тесты и рекомендации.

Что такое обход дерева

Обход дерева — процесс посещения каждого узла структуры данных ровно один раз. Обычно обходы реализуют рекурсивно или итеративно (через стек). Термины:

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

Inorder

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

Алгоритм

1. Рекурсивно выполнить inorder для левогo поддерева.
2. Посетить текущий узел (обработать значение).
3. Рекурсивно выполнить inorder для правогo поддерева.

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

Рассмотрим дерево, где 56 — корень, левое поддерево с корнем 32 и правое поддерево с корнем 62. Порядок обхода: 28 -> 32 -> 44 -> 56 -> 58 -> 62 -> 88

Где применяется

• Получение отсортированного списка значений из BST.
• Построение инфиксной записи для выражений (expression tree).

Итеративная версия (через стек)

Используется, когда глубина рекурсии может превысить ограничения стека или нужен контроль порядка без рекурсии.

# Итеративный inorder с явным стеком
class Node:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value

def inorder_iter(root):
    stack = []
    current = root
    result = []
    while stack or current:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        result.append(current.value)
        current = current.right
    return result

Preorder

Preorder — прямой обход: сначала корень, затем левое поддерево, затем правое.

Алгоритм

1. Посетить текущий узел.
2. Рекурсивно выполнить preorder для левогo поддерева.
3. Рекурсивно выполнить preorder для правогo поддерева.

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

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

Где применяется

• Быстрое клонирование дерева: посетив корень до детей, можно восстанавливать структуру при сериализации/десериализации.
• Сохранение структуры дерева (вместе с маркерами null) для передачи или хранения.

Итеративная версия (через стек)

def preorder_iter(root):
    if not root:
        return []
    stack = [root]
    result = []
    while stack:
        node = stack.pop()
        result.append(node.value)
        # Сначала пушим правого, затем левого — чтобы левый обрабатывался первым
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    return result

Postorder

Postorder — обратный обход: сначала левое поддерево, затем правое, затем корень.

Алгоритм

1. Рекурсивно выполнить postorder для левогo поддерева.
2. Рекурсивно выполнить postorder для правогo поддерева.
3. Посетить текущий узел.

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

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

Где применяется

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

Итеративные подходы для postorder

Postorder итеративно сложнее: часто используют два стека или модифицируют порядок push/pop.

def postorder_iter(root):
    if not root:
        return []
    stack1 = [root]
    stack2 = []
    while stack1:
        node = stack1.pop()
        stack2.append(node.value)
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    # stack2 содержит обратный postorder, поэтому разворачиваем
    return stack2[::-1]

Встроенный пример на Python

Ниже — пример кода, который создаёт простое BST и выводит три обхода.

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

# Рекурсивные обходы
def inorder(root):
    if root:
        inorder(root.left)
        print(str(root.value) + ", ", end='')
        inorder(root.right)

def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(str(root.value) + ", ", end='')

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()
print("Preorder Traversal of BST: ")
preorder(root)
print()
print("Postorder Traversal of BST: ")
postorder(root)

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

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

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

Когда эти обходы не работают эффективно

• Несбалансированное дерево (почти линейная структура) делает операции поиска и обхода менее предсказуемыми в реальном времени, хотя асимптотика обхода остаётся O(n).
• Для больших данных и ограниченной памяти рекурсия может быть недопустима.
• Когда нужен быстрый поиск по диапазону в динамически меняющемся наборе — иногда лучше применять самобалансирующиеся деревья (AVL, Red-Black) или B-деревья для хранения на диске.

Альтернативные подходы

• Самобалансирующиеся деревья: AVL, Red-Black — гарантируют O(log n) для поиска/вставки/удаления.
• Хеш-таблицы: дают O(1) в среднем для поиска, но не поддерживают упорядоченные обходы.
• B-деревья: используются в СУБД и файловых системах для больших наборов данных на диске.

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

• Представляйте inorder как “лево, корень, право” — это сортировка по возрастанию на BST.
• Preorder — “архитектор дерева”: вы видите структуру сверху вниз.
• Postorder — “уборщик”: сначала убирает детей, затем родителя.

Фактбокс

• Число узлов: n
• Высота дерева: h
• Сложность времени обхода: O(n)
• Пространственная сложность: O(h) (рекурсия или стек)

Чеклист для ролей

• Студент:
  • Понять порядок посещения для каждого обхода.
  • Уметь вывести небольшой пример на бумаге.
• Инженер на задаче производительности:
  • Проверить высоту дерева и возможность переполнения стека.
  • Рассмотреть итеративные обходы при больших n.
• На собеседовании:
  • Уметь написать рекурсивный и итеративный вариант за 5–10 минут.
  • Объяснить сложность и случаи, когда обходы не подходят.

Критерии приёмки

• Код возвращает корректный порядок узлов для всех трёх обходов на тестовом дереве.
• Итеративные реализации проходят тесты при глубине > 1000 (если в языке ограничена глубина рекурсии).
• Производительность измерена при n в пределах ожидаемого для проекта.

Тесты и случаи проверки

• Пустое дерево: все обходы возвращают [] или ничего не печатают.
• Один узел: все обходы возвращают [root].
• Линейно вырожденное дерево (вставка по возрастанию): проверка на пересыпание стека.
• Большое сбалансированное дерево: сравнение времени и памяти рекурсивного и итеративного подходов.

Быстрая шпаргалка (cheat sheet)

• Inorder: левый, корень, правый — отсортированный порядок для BST.
• Preorder: корень, левый, правый — сериализация структуры.
• Postorder: левый, правый, корень — безопасное удаление.

Простое дерево и решение для выбора обхода

flowchart TD
    A[Нужно получить отсортированный список?] -->|Да| B[Использовать inorder]
    A -->|Нет| C[Нужно сохранить структуру или клонировать?]
    C -->|Да| D[Использовать preorder]
    C -->|Нет| E[Нужно удалить дерево или получить постфиксную форму?]
    E -->|Да| F[Использовать postorder]
    E -->|Нет| G[Подумать о других структурах данных]

Риски и варианты смягчения

• Риск: переполнение рекурсивного стека при h большой. Смягчение: итеративные реализации.
• Риск: медленная работа при несбалансированном дереве. Смягчение: использовать балансировку или другую структуру.

Короткое резюме

• Inorder возвращает элементы BST в возрастающем порядке и полезен для сортировки.
• Preorder полезен для сериализации и клонирования дерева.
• Postorder удобен при удалении дерева и для вычисления постфиксных выражений.
• Для глубоких деревьев выбирайте итеративные реализации с явным стеком или используйте самобалансирующиеся деревья.

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