Деревья и обходы

Что такое дерево и зачем нужны обходы

Если в задаче встречается папка с подпапками, схема турнира, родословная или система ходов, обычного списка уже недостаточно: объекты связаны уровнями. Дерево помогает увидеть эту структуру, а обходы превращают её в понятный порядок действий. Разберём тему так, чтобы ты мог уверенно читать схемы, находить высоту и количество вершин, а затем применять правильный алгоритм на экзамене и в задачах.

Дерево — это связный граф без циклов. Его элементы называют вершинами, а соединения — рёбрами. У дерева есть одна особая вершина — корень. От корня идут ветви к дочерним вершинам, а вершины без потомков называют листьями.

У каждой вершины, кроме корня, есть ровно один родитель. Между любыми двумя вершинами существует единственный путь. Если в дереве n вершин, то рёбер всегда n − 1. Это свойство часто позволяет быстро проверить ответ.

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

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

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

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

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

Понятие	Что означает	Как проверить
Корень	Главная вершина дерева	Нет родителя
Лист	Вершина без потомков	Нет исходящих ветвей
Глубина	Расстояние от корня	Считаем рёбра на пути
Высота	Максимальная глубина	Берём самый длинный путь вниз

Три главных обхода

Обход — это способ посетить вершины дерева в определённом порядке. В двоичных деревьях особенно важны три варианта. В прямом обходе сначала посещают вершину, затем левое поддерево, потом правое: корень → левое → правое.

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

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

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

Не пытайся запоминать названия отдельно от схемы. Сначала найди момент, когда записывается корень: в начале — прямой обход, в середине — симметричный, в конце — обратный.

Разобранный пример

Рассмотрим дерево. У корня 8 есть левый сын 3 и правый сын 10. У вершины 3 дети 1 и 6, а у 6 дети 4 и 7. У вершины 10 есть правый сын 14. Найдём высоту, листья и три последовательности обхода.

Дерево: 8 → (3, 10)
3 → (1, 6)
6 → (4, 7)
10 → (∅, 14)
Листья: 1, 4, 7, 14
Высота: путь 8 → 3 → 6 → 4 содержит 3 ребра

Сначала проверяем высоту: самый длинный путь от корня до листа проходит через 3 и 6, поэтому высота равна 3. В прямом обходе записываем 8, затем полностью левую часть: 3, 1, 6, 4, 7, и после этого правую: 10, 14.

Прямой: 8 → 3 → 1 → 6 → 4 → 7 → 10 → 14
Симметричный: 1 → 3 → 4 → 6 → 7 → 8 → 10 → 14
Обратный: 1 → 4 → 7 → 6 → 3 → 14 → 10 → 8

Заметь: симметричная последовательность получилась возрастающей. Это не случайность: перед нами дерево поиска, где слева лежат меньшие значения, а справа — большие.

Типичные ошибки и практика

Первая ошибка — считать вершины вместо рёбер при поиске глубины. Если путь содержит четыре вершины, рёбер в нём три. Вторая — начинать обход в ширину, когда требуется обход в глубину. Внимательно читай условие: «по уровням» означает ширину, а «сначала корень» или «после потомков» обычно подсказывает один из трёх глубинных вариантов.

Третья ошибка — менять местами левое и правое поддеревья. В симметричном обходе это особенно заметно: для дерева поиска правильный результат должен идти по возрастанию. Четвёртая — считать корень листом. Лист не имеет детей, а корень может быть листом только в дереве из одной вершины.

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

Что запомнить

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

Перед решением задачи определи корень, направление, тип обхода и способ подсчёта уровней. Если нужно повторить базовые алгоритмы, загляни в раздел подготовки к ЕГЭ или материалы для ОГЭ. Следующий шаг простой: зарегистрируйся и реши 5 заданий бесплатно в личном кабинете.