14.4 Бинарные деревья¶

Что такое бинарное дерево¶

Бинарное дерево — это корневое дерево, у каждой вершины которого может быть не более двух потомков:

• левый сын;
• правый сын.

При этом у вершины может не быть детей совсем, может быть только один ребёнок, а может быть два.

Это важное отличие от произвольного дерева, где число детей ничем не ограничено.

Пример бинарного дерева:

flowchart TD
    A[1] --> B[2]
    A --> C[3]
    B --> D[4]
    B --> E[5]
    E --> F[6]
    C --> G[7]

Здесь:

• у вершины 1 левый сын — 2, правый — 3;
• у вершины 2 левый сын — 4, правый — 5;
• у вершины 5 есть только один ребёнок 6;
• у вершины 3 есть только один ребёнок 7.

Почему бинарные деревья так важны¶

Бинарные деревья встречаются очень часто:

• binary search tree — двоичное дерево поиска;
• segment tree — дерево отрезков;
• heap — куча;
• деревья выражений в задачах на арифметические формулы;
• рекурсивные структуры в динамике и разборе выражений.

Во многих задачах нужно уметь:

• обходить дерево в нужном порядке;
• восстанавливать дерево по порядкам обхода;
• понимать, какую информацию несёт каждый обход.

Три естественных обхода бинарного дерева¶

У бинарного дерева есть три классических способа рекурсивного обхода:

1. pre-order — сначала корень, потом левое поддерево, потом правое;
2. in-order — сначала левое поддерево, потом корень, потом правое;
3. post-order — сначала левое поддерево, потом правое, потом корень.

Это не просто три похожих определения. У каждого обхода свой смысл.

1. Pre-order¶

Порядок действий:

1. обработать текущую вершину;
2. рекурсивно пройти левое поддерево;
3. рекурсивно пройти правое поддерево.

Идея: корень встречается раньше своих потомков.

2. In-order¶

Порядок действий:

1. рекурсивно пройти левое поддерево;
2. обработать текущую вершину;
3. рекурсивно пройти правое поддерево.

Идея: корень находится между левым и правым поддеревом.

Для двоичного дерева поиска именно такой обход выдаёт вершины в отсортированном порядке.

3. Post-order¶

Порядок действий:

1. рекурсивно пройти левое поддерево;
2. рекурсивно пройти правое поддерево;
3. обработать текущую вершину.

Идея: вершина обрабатывается только после детей.

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

Пример обходов¶

Возьмём такое дерево:

flowchart TD
    A[1] --> B[2]
    A --> C[3]
    B --> D[4]
    B --> E[5]
    E --> F[6]
    C --> G[7]

Pre-order¶

Идём так:

• сначала 1;
• затем левое поддерево вершины 1: 2, 4, 5, 6;
• затем правое поддерево вершины 1: 3, 7.

Получаем:

[1, 2, 4, 5, 6, 3, 7]

In-order¶

Идём так:

• левое поддерево вершины 1: 4, 2, 6, 5;
• затем 1;
• затем правое поддерево: 3, 7.

Получаем:

[4, 2, 6, 5, 1, 3, 7]

Post-order¶

Идём так:

• сначала левое поддерево: 4, 6, 5, 2;
• затем правое поддерево: 7, 3;
• затем корень 1.

Получаем:

[4, 6, 5, 2, 7, 3, 1]

Рекурсивная реализация обходов на C++¶

Пусть у нас есть структура вершины:

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int value;
    Node* left;
    Node* right;

    Node(int v) : value(v), left(nullptr), right(nullptr) {}
};

Pre-order¶

void preorder(Node* node) {
    if (node == nullptr) return;

    cout << node->value << ' ';
    preorder(node->left);
    preorder(node->right);
}

In-order¶

void inorder(Node* node) {
    if (node == nullptr) return;

    inorder(node->left);
    cout << node->value << ' ';
    inorder(node->right);
}

Post-order¶

void postorder(Node* node) {
    if (node == nullptr) return;

    postorder(node->left);
    postorder(node->right);
    cout << node->value << ' ';
}

Пример использования¶

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->left->right->left = new Node(6);
    root->right->right = new Node(7);

    preorder(root);
    cout << '\n';

    inorder(root);
    cout << '\n';

    postorder(root);
    cout << '\n';
}

Вывод:

1 2 4 5 6 3 7
4 2 6 5 1 3 7
4 6 5 2 7 3 1

Как мыслить про эти обходы¶

Полезная интуиция такая:

• pre-order: вершина появляется до своих детей;
• in-order: вершина появляется между левым и правым поддеревом;
• post-order: вершина появляется после детей.

Это удобно запомнить даже по названиям:

• pre = до;
• in = внутри;
• post = после.

Восстановление дерева по pre-order и in-order¶

Один из самых важных фактов: если известны

• pre-order,
• in-order,

то структуру бинарного дерева можно восстановить однозначно.

Почему это работает¶

В pre-order самый первый элемент — это корень дерева.

После того как мы узнали корень, в in-order можно найти его позицию:

• всё, что слева от него, относится к левому поддереву;
• всё, что справа, относится к правому поддереву.

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

Пример¶

Пусть:

• pre-order = [1, 2, 4, 5, 6, 3, 7]
• in-order = [4, 2, 6, 5, 1, 3, 7]

Разберём шаги.

Шаг 1¶

Первый элемент pre-order — это 1. Значит, корень — 1.

В in-order элемент 1 делит массив на:

• левое поддерево: [4, 2, 6, 5]
• правое поддерево: [3, 7]

Значит, следующие 4 элемента в pre-order относятся к левому поддереву, а оставшиеся — к правому:

• левое pre-order: [2, 4, 5, 6]
• правое pre-order: [3, 7]

Шаг 2: левое поддерево¶

Для левого поддерева первый элемент pre-order — 2, это корень левого поддерева.

В его in-order:

[4, 2, 6, 5]

элемент 2 делит массив на:

• левую часть: [4]
• правую часть: [6, 5]

Шаг 3: правое поддерево вершины 2¶

Для части [6, 5] в pre-order идёт [5, 6], значит корень здесь — 5.

В in-order:

[6, 5]

слева от 5 стоит 6, справа ничего нет. Значит, у 5 есть левый ребёнок 6.

Шаг 4: правое поддерево корня 1¶

Остались:

• pre-order: [3, 7]
• in-order: [3, 7]

Корень — 3, справа от него стоит 7, то есть 7 — правый ребёнок 3.

В итоге получаем исходное дерево.

Реализация восстановления по pre-order и in-order на C++¶

Ниже — классическая реализация за O(n), если заранее построить позиции элементов в in-order.

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int value;
    Node* left;
    Node* right;

    Node(int v) : value(v), left(nullptr), right(nullptr) {}
};

Node* build(
    const vector<int>& pre,
    int pl, int pr,
    const vector<int>& in,
    int il, int ir,
    unordered_map<int,int>& pos
) {
    if (pl > pr || il > ir) return nullptr;

    int rootValue = pre[pl];
    Node* root = new Node(rootValue);

    int k = pos[rootValue];
    int leftSize = k - il;

    root->left = build(pre, pl + 1, pl + leftSize, in, il, k - 1, pos);
    root->right = build(pre, pl + leftSize + 1, pr, in, k + 1, ir, pos);

    return root;
}

void preorder(Node* node) {
    if (!node) return;
    cout << node->value << ' ';
    preorder(node->left);
    preorder(node->right);
}

int main() {
    vector<int> pre = {1, 2, 4, 5, 6, 3, 7};
    vector<int> in = {4, 2, 6, 5, 1, 3, 7};

    unordered_map<int,int> pos;
    for (int i = 0; i < (int)in.size(); i++) {
        pos[in[i]] = i;
    }

    Node* root = build(pre, 0, (int)pre.size() - 1, in, 0, (int)in.size() - 1, pos);

    preorder(root);
    cout << '\n';
}

Почему это работает быстро¶

Каждая вершина создаётся один раз.

Если бы мы каждый раз искали корень в массиве in-order линейным поиском, получилось бы O(n^2). Но если сохранить позиции в unordered_map, то поиск позиции корня занимает в среднем O(1), и общая сложность становится O(n).

Восстановление по post-order и in-order¶

Аналогично, если известны:

• post-order,
• in-order,

то дерево тоже восстанавливается однозначно.

Разница только в том, что в post-order корень находится в конце, а не в начале.

То есть логика такая:

• последний элемент post-order — корень;
• в in-order по нему делим дерево на левое и правое поддеревья;
• рекурсивно восстанавливаем их.

Это полностью симметрично предыдущему случаю.

Почему только pre-order и post-order недостаточно¶

Если известны только:

• pre-order,
• post-order,

то дерево может восстанавливаться неоднозначно.

Простейший пример:

1. у вершины 1 есть левый ребёнок 2;
2. у вершины 1 есть правый ребёнок 2.

У обоих деревьев:

• pre-order = [1, 2]
• post-order = [2, 1]

Но структуры разные.

Главная причина¶

Если у вершины только один ребёнок, то по pre-order и post-order нельзя понять, это левый сын или правый.

Именно поэтому для однозначного восстановления нужна информация типа in-order, которая фиксирует положение корня между левым и правым поддеревом.

Где это встречается в задачах¶

Типичные применения:

1. Вычисления по дереву выражений¶

В post-order удобно вычислять арифметические выражения, потому что сначала считаются значения детей, а потом применяется операция в текущей вершине.

2. Проверка корректности структуры¶

Иногда в задаче даны два обхода, и нужно:

• восстановить дерево;
• проверить, может ли такое дерево существовать;
• вывести другой обход.

3. Работа с binary search tree¶

В бинарном дереве поиска in-order выдаёт ключи в отсортированном порядке.

Это очень важное свойство и его часто используют в задачах.

Ещё один полезный пример¶

Пусть задано бинарное дерево:

flowchart TD
    A[10] --> B[4]
    A --> C[15]
    B --> D[2]
    B --> E[7]
    C --> F[12]
    C --> G[20]

Тогда:

• pre-order: [10, 4, 2, 7, 15, 12, 20]
• in-order: [2, 4, 7, 10, 12, 15, 20]
• post-order: [2, 7, 4, 12, 20, 15, 10]

Обрати внимание: in-order здесь уже отсортирован, потому что это пример бинарного дерева поиска.

Итоги¶

Бинарное дерево — это дерево, у каждой вершины которого не более двух детей: левого и правого.

Для бинарного дерева особенно важны три обхода:

• pre-order: корень, левое поддерево, правое поддерево;
• in-order: левое поддерево, корень, правое поддерво;
• post-order: левое поддерево, правое поддерево, корень.

Ключевые факты:

• по pre-order + in-order дерево восстанавливается однозначно;
• по post-order + in-order дерево тоже восстанавливается однозначно;
• только по pre-order + post-order восстановить дерево однозначно нельзя.

Эти идеи часто встречаются в задачах на рекурсию, деревья, структуры данных и разбор выражений.

Короткие вопросы для самопроверки¶

1. Почему обход in-order особенно важен для бинарного дерева поиска?
2. Почему из pre-order сразу виден корень дерева?
3. Почему без in-order нельзя однозначно различить левого и правого единственного ребёнка?
4. Какую асимптотику имеет восстановление дерева по pre-order и in-order при использовании хеш-таблицы позиций?