Алгоритмы обхода двоичных деревьев

Модуль "Деревья" • урок 8 из 11 • ~8 минут

Алгоритмы обхода двоичных деревьев в глубину (DFS)

Так как каждый узел дерева состоит из трех логических частей (сам Корень, Левое поддерево, Правое поддерево), существует 3 главных способа рекурсивного обхода. Они отличаются лишь моментом, когда обрабатывается (печатается или читается) сам Корень по отношению к своим детям.

1. Прямой (префиксный / Pre-order) обход: КЛП

Порядок: Корень (К) → Левое поддерево (Л) → Правое поддерево (П).
Применение: Создание точной копии (клонирования) дерева, сериализация дерева в файл для последующего восстановления.

2. Симметричный (инфиксный / In-order) обход: ЛКП

Порядок: Левое поддерево (Л) → Корень (К) → Правое поддерево (П).
Применение: Для "Деревьев поиска" именно этот обход выдает все элементы строго в отсортированном по возрастанию порядке.

3. Обратный (постфиксный / Post-order) обход: ЛПК

Порядок: Левое поддерево (Л) → Правое поддерево (П) → Корень (К).
Применение: Уничтожение (освобождение памяти) дерева, так как корень удаляется только после того, как гарантированно и безопасно удалены все его потомки. Также применяется для вычисления математических выражений в деревьях разбора.

Обход в ширину (BFS)

Дерево обходится "слоями" по уровням: сначала корень, затем все дети корня (2-й уровень слева направо), затем внуки (3-й уровень) и так далее.

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

Реализация на языке C (три обхода в глубину)

Обратите внимание, как элегантно и просто выглядит рекурсивный код. Три алгоритма отличаются ровно одной строчкой - тем местом, где происходит обработка узла (Process).

#include <stdio.h>

typedef struct Node {
    int data; 
    struct Node *left, *right; 
} Node;

// Функция полезной нагрузки (обработки) узла
void Process(Node* n) { 
    printf("%d ", n->data); 
}

// 1. Прямой обход (КЛП)
void PreOrder(Node* root) {
    if (root == NULL) return;
    Process(root);         // Сначала Корень (К)
    PreOrder(root->left);  // Затем Левое поддерево (Л)
    PreOrder(root->right); // Затем Правое поддерево (П)
}

// 2. Симметричный обход (ЛКП)
void InOrder(Node* root) {
    if (root == NULL) return;
    InOrder(root->left);   // Л
    Process(root);         // К
    InOrder(root->right);  // П
}

// 3. Обратный обход (ЛПК)
void PostOrder(Node* root) {
    if (root == NULL) return;
    PostOrder(root->left);  // Л
    PostOrder(root->right); // П
    Process(root);          // К
}