Модель дерева и три порядка обхода

Для дерева с корнем 1 и детьми 2 и 3 preorder записывает корень до рекурсии и получает [1,2,3]; inorder дал бы [2,1,3], postorder — [2,3,1].

Словарь формы: от корня к поддереву

Корень — единственный узел без родителя. У каждого другого узла есть родитель и связь с ребёнком. Узел без детей называется листом. Все узлы, достижимые вниз от выбранного узла вместе с ним самим, образуют его поддерево.

Глубина узла — число рёбер от корня до него. Высота узла — длина самого длинного пути от него до листа; высота дерева равна высоте корня. В разных источниках высоту одного узла могут считать в рёбрах или узлах, поэтому перед формулой зафиксируйте соглашение.

Бинарное дерево ограничивает число детей двумя, обычно left и right, но ничего не говорит о порядке значений. Бинарное дерево поиска (BST) добавит такой инвариант позже; нельзя переносить его на произвольное дерево.

Представление повторяет рекурсивную структуру

Узел хранит значение и ссылки на детей. null/None означает пустое поддерево. В C++ учебная модель использует Node*, поэтому время жизни и владение узлами должны быть определены вызывающим кодом. В Python ссылки управляются средой, но отсутствие цикла и глубина рекурсии всё равно остаются частью контракта алгоритма.

Дерево не обязано храниться узлами. Полное или почти полное бинарное дерево удобно упаковать в массив — именно так устроена двоичная куча. Выбор представления следует из операций, а не из рисунка с кружками.

Три DFS-порядка отвечают на разные вопросы

• preorder (root-left-right) обрабатывает родителя до поддеревьев: удобно копировать структуру или передавать контекст вниз;
• inorder (left-root-right) в BST выдаёт ключи по возрастанию;
• postorder (left-right-root) сначала получает результаты детей: удобно вычислять высоту, размер или освобождать дерево.

Обход по уровням — уже BFS с очередью: он посещает узлы по возрастанию глубины, а не углубляется в одно поддерево.

Как порядок обработки корня меняет обход дерева?

Вернуть preorder бинарного дерева: корень, левое поддерево, правое поддерево.

Какие узлы пришлось бы перечислять вручную?

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

Почему ручная логика не масштабируется с высотой?

Пути дублируют общие префиксы и не соответствуют простой структуре «корень + два поддерева».

Поддерево имеет ту же форму задачи, что и дерево

Каждое непустое дерево однозначно состоит из корня и двух меньших деревьев, поэтому один и тот же код применим рекурсивно.

Что означает order после завершения вызова preorder?

Вызов preorder(node) добавляет ровно все вершины поддерева node в порядке root-left-right и не затрагивает другие поддеревья.

Корень, левое и правое поддерево в нужном порядке

Для null вернуться. Иначе добавить значение узла, рекурсивно обойти left, затем right. Для inorder обработка корня стоит между вызовами, для postorder — после.

Preorder на C++17 и Python 3

C++17

#include <cassert>
#include <vector>
using namespace std;

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

void preorder(Node* node, vector<int>& order) {
    if (node == nullptr) return;
    order.push_back(node->value);
    preorder(node->left, order);
    preorder(node->right, order);
}

int main() {
    Node left{2, nullptr, nullptr};
    Node right{3, nullptr, nullptr};
    Node root{1, &left, &right};
    vector<int> order;
    preorder(&root, order);
    assert((order == vector<int>{1, 2, 3}));
    order.clear();
    preorder(nullptr, order);
    assert(order.empty());
}

Python 3

class Node:
    def __init__(
        self,
        value: int,
        left: "Node | None" = None,
        right: "Node | None" = None,
    ) -> None:
        self.value = value
        self.left = left
        self.right = right


def preorder(node: Node | None, order: list[int]) -> None:
    if node is None:
        return
    order.append(node.value)
    preorder(node.left, order)
    preorder(node.right, order)


order: list[int] = []
preorder(Node(1, Node(2), Node(3)), order)
assert order == [1, 2, 3]
order.clear()
preorder(None, order)
assert order == []

Каждый узел посещается один раз, стек зависит от высоты

O(n) времени, потому что каждый узел посещается один раз; O(h) стека вызовов, где h — высота, до O(n) у вырожденного дерева.

Пустое дерево, один ребёнок и глубокая цепочка

Пустое дерево; один узел; только левое или правое поддерево; вырожденная цепочка и риск глубокой рекурсии.

Тесты, различающие preorder, inorder и postorder

Пустое -> []; один узел; дерево 1(2,3) -> [1,2,3]; несимметричное дерево.

Когда условие просит обойти каждое поддерево?

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

Когда рекурсию стоит заменить явным стеком?

Для очень глубокого дерева рекурсивный обход может переполнить стек; используйте явный stack.

Мини-проверка: где обрабатывается корень в inorder?

Вопрос: чем inorder отличается от preorder? Ответ: в inorder корень обрабатывается после левого поддерева, а не до него.

Мини-проверка: почему память бывает O(n)?

Вопрос: почему память не всегда O(log n)? Ответ: высота несбалансированного дерева может быть n.

Выпишите три порядка для одного дерева

Для дерева с корнем 4, левыми узлами 2/1/3 и правым 5 выпишите preorder, inorder и postorder.

Реализуйте postorder без готового шаблона

Задача 1

Реализуйте итеративный inorder бинарного дерева с явным стеком и верните список значений.

Место обработки корня определяет вид DFS

Один шаблон обхода становится тремя алгоритмами только из-за момента обработки корня.