Бинарное дерево – иерархическая структура данных, в которой каждый узел может иметь не более двух непосредственных потомков. Их условно называют левым и правым ребёнком. Такое ограничение не делает структуру примитивной: из узлов и связей можно строить выражения, индексы, словари, игровые решения и модели выбора.
В отличие от линейного списка, дерево допускает несколько направлений продолжения. От корня путь разветвляется, а каждый потомок становится корнем собственного поддерева. Поэтому элементы описываются не только значениями, но и отношениями: кто является родителем, на каком уровне расположен узел и какие ветви начинаются от него.
Работа с бинарным деревом требует определить форму структуры, способ хранения и порядок посещения узлов. Одни задачи решаются рекурсивным спуском, другие используют стек или очередь. Эффективность поиска зависит не от самого слова «дерево», а от его организации: вытянутая цепочка и равномерно разветвлённое дерево ведут себя по-разному.
Минимальный элемент структуры – узел. Обычно он содержит полезное значение или ключ и две ссылки: left на левое поддерево и right на правое. Отсутствующий потомок обозначается пустой ссылкой. В программной реализации к узлу также можно добавить счётчик, высоту, цвет, ссылку на родителя или другие служебные поля.
Самый верхний узел называется корнем. Узел без детей является листом, а узел хотя бы с одним ребёнком – внутренним. Связь от родителя к потомку образует ребро. Любой узел вместе со всеми его потомками формирует поддерево, поэтому определение бинарного дерева естественно повторяется на каждом уровне.
Глубина узла равна числу рёбер от корня до этого узла. Высотой узла называют длину самого длинного пути от него до листа, а высотой всего дерева – высоту корня. В учебных источниках отсчёт иногда начинают с нуля, иногда с единицы, поэтому выбранное соглашение необходимо указать до вычислений.
Таблица 1. Основные понятия бинарного дерева
Понятия связаны между собой. Например, один и тот же узел может быть правым ребёнком своего родителя, корнем отдельного поддерева и внутренним узлом для собственных потомков. Поэтому при анализе важно всегда уточнять, относительно какой части дерева описывается положение элемента.
Бинарное дерево удобно задавать рекурсивно: оно либо пусто, либо состоит из корня, левого бинарного поддерева и правого бинарного поддерева. Благодаря этому поиск размера, высоты, суммы значений и многие обходы выражаются одинаковой схемой: решить задачу для корня, затем для двух поддеревьев и объединить результаты.
Форма дерева влияет на расход памяти и скорость операций. Строгое дерево не допускает узлов ровно с одним ребёнком. Идеальное дерево полностью заполняет каждый уровень. Полное дерево заполняется сверху вниз и слева направо, а сбалансированное ограничивает различие высот ветвей, не требуя абсолютной симметрии.
Таблица 2. Распространённые виды бинарных деревьев
Связное представление создаёт отдельный объект для каждого узла и хранит ссылки на детей. Оно удобно для деревьев меняющейся формы. Массивное представление нумерует позиции: для индекса i дети часто располагаются в 2i + 1 и 2i + 2. Такой способ особенно выгоден для почти полного дерева, например для двоичной кучи.
Обход определяет, в какой последовательности будут обработаны все узлы. В прямом обходе сначала посещают корень, затем левое и правое поддеревья. В симметричном корень расположен между обходами ветвей, а в обратном обрабатывается после них. Каждый порядок подчёркивает другую логику структуры.
Обход по уровням отличается от трёх глубинных вариантов. Он движется от верхних уровней к нижним и обычно использует очередь. Рекурсивные обходы неявно опираются на стек вызовов; итеративные версии создают собственный стек и позволяют точнее контролировать память.
Таблица 3. Порядки обхода бинарного дерева


Ошибка 1. Любую иерархию называют бинарным деревом. Если у узла допускаются три и более непосредственных потомка, структура не является бинарной. Нужно проверять ограничение для каждого узла, а не только для корня.
Ошибка 2. Путают глубину и высоту. Глубина показывает расстояние от корня вниз к выбранному узлу, а высота – расстояние от узла к наиболее удалённому листу. Полезно заранее нарисовать направление измерения.
Ошибка 3. Считают полное дерево обязательно идеальным. В полном дереве последний уровень может быть заполнен не до конца, но узлы на нём располагаются слева без пропусков. Идеальное дерево требует заполнения всех уровней целиком.
Ошибка 4. Предполагают, что любое бинарное дерево автоматически является деревом поиска. Для поискового свойства необходим упорядочивающий инвариант; без него симметричный обход не обязан выдавать ключи по возрастанию.
Ошибка 5. В рекурсивной функции забывают обработать пустую ссылку. Вызовы продолжаются за пределы листа и приводят к ошибке. Базовый случай должен возвращать результат до обращения к полям отсутствующего узла.
Перед написанием алгоритма полезно изобразить небольшое дерево и подписать левую и правую ветви. Затем вручную пройти его в требуемом порядке. Такая проверка быстро обнаруживает переставленные вызовы, пропущенный корень и неверное использование стека или очереди.
В коде удобно разделять структуру узла и операции над деревом. Класс Node отвечает за хранение значения и ссылок, а отдельные функции выполняют обход, поиск, вставку и вычисление высоты. Это облегчает тестирование пустого дерева, одного узла и нескольких форм ветвления.
Связный список имеет не более одного следующего элемента и образует линейный путь. Обычное дерево допускает произвольное число детей. Двоичная куча является бинарным деревом с дополнительными требованиями к форме и приоритету, а дерево бинарного поиска задаёт порядок ключей, но не обязано быть полным.
Граф может содержать циклы, несколько путей между вершинами и не иметь выделенного корня. Дерево в классическом понимании связно и не содержит циклов, поэтому между корнем и каждым узлом существует единственный путь. Эти признаки важнее внешнего сходства рисунков.
Таблица 4. Сравнение бинарного дерева с близкими структурами
Образец 1. В дереве с корнем 8, левым ребёнком 3 и правым ребёнком 10 узел 8 имеет глубину 0. Узлы 3 и 10 расположены на следующем уровне. Если они не имеют детей, оба являются листьями, а высота дерева при счёте по рёбрам равна 1.
Образец 2. Для прямого обхода дерева сначала записывают значение корня, затем полностью обходят левую ветвь и только после неё правую. Если корень A, слева B с детьми D и E, а справа C, порядок будет A, B, D, E, C.
Образец 3. Симметричный обход дерева бинарного поиска выводит ключи в неубывающем порядке при корректном размещении повторов. Сначала читается левое поддерево, затем ключ узла, после чего правое поддерево. Это свойство удобно для сортированного просмотра данных.
Образец 4. Поиск ключа 17 в дереве бинарного поиска начинается с корня. Если 17 меньше текущего ключа, переходят влево; если больше – вправо. Движение заканчивается при совпадении либо при пустой ссылке, означающей отсутствие элемента.
Бинарные деревья применяются в синтаксическом анализе выражений, индексах, кодировании, приоритетных очередях, системах принятия решений и игровых алгоритмах. Они помогают хранить не просто последовательность данных, а отношения подчинения и альтернативные направления продолжения.
Изучение темы развивает навык рекурсивного мышления. Большая задача раскладывается на одинаковые задачи для левой и правой частей, а базовый случай останавливает процесс. Одновременно становятся понятнее оценки сложности, роль высоты и различие между логической моделью и физическим хранением.
Упражнения расположены от распознавания элементов дерева к вычислению характеристик, построению обходов, анализу дерева поиска и составлению простых алгоритмов. После каждого задания приведено решение для самостоятельной проверки.
Упражнение 1. Сколько непосредственных потомков может иметь узел бинарного дерева?
Решение. Допустимо ноль, один или два потомка; больше двух быть не может.
Упражнение 2. Как называется самый верхний узел дерева?
Решение. Самый верхний узел называется корнем.
Упражнение 3. Как называется узел, у которого отсутствуют оба ребёнка?
Решение. Такой узел является листом.
Упражнение 4. Что образует узел вместе со всеми своими потомками?
Решение. Он образует поддерево с данным узлом в качестве корня.
Упражнение 5. Может ли корень иметь родителя внутри того же дерева?
Решение. Нет. По определению корень не имеет родителя.
Упражнение 6. Что хранит простейшая программная модель узла?
Решение. Значение и две ссылки: на левого и правого ребёнка.
Упражнение 7. Чем обозначают отсутствующего потомка в Python?
Решение. Обычно используют значение None.
Упражнение 8. Как называется узел хотя бы с одним ребёнком?
Решение. Это внутренний, или нелистовой, узел.
Упражнение 9. Сколько рёбер находится на пути от корня к его ребёнку?
Решение. Одно ребро, поэтому глубина ребёнка при отсчёте от нуля равна 1.
Упражнение 10. Какова глубина корня при наиболее распространённом отсчёте?
Решение. Глубина корня равна 0.
Упражнение 11. Что называют высотой дерева?
Решение. Это длина самого длинного пути от корня до листа по выбранному правилу счёта.
Упражнение 12. Какое дерево называют идеальным?
Решение. В нём каждый внутренний узел имеет двух детей, а все листья лежат на одном уровне.
Упражнение 13. Чем полное дерево отличается от идеального?
Решение. Последний уровень полного дерева может быть неполным, но заполняется слева направо.
Упражнение 14. Какое дерево называют вырожденным?
Решение. Дерево, где каждый внутренний узел имеет только одного ребёнка и структура похожа на цепочку.
Упражнение 15. Какой порядок задаёт прямой обход?
Решение. Корень, затем левое поддерево, затем правое поддерево.
Упражнение 16. Какой порядок задаёт симметричный обход?
Решение. Левое поддерево, корень, правое поддерево.
Упражнение 17. Какой порядок задаёт обратный обход?
Решение. Левое поддерево, правое поддерево, корень.
Упражнение 18. Какая структура данных нужна для обхода по уровням?
Решение. Очередь, потому что узлы обрабатываются в порядке добавления по уровням.
Упражнение 19. Какая структура неявно используется рекурсивным обходом?
Решение. Стек вызовов функций.
Упражнение 20. Найдите прямой обход: корень A, слева B, справа C.
Решение. Последовательность A, B, C.
Упражнение 21. Найдите симметричный обход того же дерева.
Решение. Последовательность B, A, C.
Упражнение 22. Найдите обратный обход того же дерева.
Решение. Последовательность B, C, A.
Упражнение 23. Какой обход дерева выражений удобно использовать для удаления структуры после обработки?
Решение. Обратный обход, потому что дети обрабатываются раньше родителя.
Упражнение 24. Что выводит симметричный обход корректного дерева бинарного поиска?
Решение. Ключи в неубывающем порядке, если правило повторов определено согласованно.
Упражнение 25. Куда перейти при поиске, если искомый ключ меньше ключа текущего узла?
Решение. В левое поддерево.
Упражнение 26. Куда перейти, если искомый ключ больше текущего?
Решение. В правое поддерево.
Упражнение 27. Когда поиск в дереве бинарного поиска заканчивается неудачей?
Решение. Когда очередная нужная ссылка оказывается пустой.
Упражнение 28. От чего зависит время поиска в обычном дереве бинарного поиска?
Решение. От высоты дерева и расположения искомого ключа.
Упражнение 29. Какова типичная сложность поиска в сбалансированном дереве?
Решение. O(log n), где n – число узлов.
Упражнение 30. Какой может стать сложность поиска в вырожденном дереве?
Решение. O(n), как при последовательном просмотре списка.
Упражнение 31. Как добавить ключ, меньший корня, в дерево поиска без других узлов?
Решение. Создать новый узел и связать его как левого ребёнка корня.
Упражнение 32. Как добавить ключ, больший корня?
Решение. Создать узел и связать его как правого ребёнка.
Упражнение 33. Как удалить лист из связного дерева?
Решение. У родителя заменить соответствующую ссылку на пустую.
Упражнение 34. Как обычно удаляют узел с одним ребёнком?
Решение. Родителя связывают непосредственно с единственным ребёнком удаляемого узла.
Упражнение 35. Чем заменяют узел дерева поиска с двумя детьми?
Решение. Часто его заменяют следующим ключом из правого поддерева или предыдущим из левого.
Упражнение 36. Как вычислить число узлов рекурсивно?
Решение. Для пустого дерева вернуть 0, иначе вернуть 1 плюс размеры левого и правого поддеревьев.
Упражнение 37. Как рекурсивно определить число листьев?
Решение. Пустая ссылка даёт 0, лист даёт 1, внутренний узел – сумму результатов двух ветвей.
Упражнение 38. Как проверить наличие ключа в произвольном бинарном дереве?
Решение. Сравнить корень и при несовпадении проверить оба поддерева, если нет свойства поиска.
Упражнение 39. Как представить почти полное дерево в массиве?
Решение. Размещать узлы по уровням; для индекса i дети находятся в 2i + 1 и 2i + 2.
Упражнение 40. Где расположен родитель элемента с индексом i > 0?
Решение. При нумерации с нуля его индекс равен (i - 1) // 2.
Упражнение 41. Почему массив неудобен для сильно разреженного дерева?
Решение. Между существующими узлами появляется много пустых позиций, расходующих место.
Упражнение 42. Какой базовый случай нужен функции высоты?
Решение. Для пустого поддерева вернуть выбранное начальное значение, например -1 при счёте высоты по рёбрам.
Упражнение 43. Что неверно в рекурсии без проверки node is None?
Решение. Функция попытается обратиться к полям отсутствующего узла и завершится ошибкой.
Упражнение 44. Как проверить корректность обхода вручную?
Решение. Нарисовать дерево, отметить порядок корня и ветвей, затем последовательно нумеровать посещения.
Упражнение 45. Выполните полный анализ дерева с корнем 5, левым листом 2 и правым листом 8.
Решение. В дереве три узла и два ребра; корень 5 имеет двух детей, 2 и 8 являются листьями. Высота по рёбрам равна 1. Прямой обход: 5, 2, 8; симметричный: 2, 5, 8; обратный: 2, 8, 5.
Бинарное дерево представляет данные как систему узлов, связанных отношениями родителя и двух возможных потомков. Корень задаёт начало структуры, листья завершают ветви, а поддеревья позволяют рассматривать любую часть по тем же правилам, что и целое дерево.
Для решения задач необходимо различать форму дерева, глубину и высоту, выбирать подходящий обход и понимать способ хранения. В дереве бинарного поиска дополнительный порядок ключей ускоряет переход к нужной ветви, но результат зависит от высоты и сохранения инварианта после вставки или удаления.
Главный способ самопроверки – проследить структуру на небольшом рисунке: отметить корень, детей и пустые ссылки, вручную выполнить нужный обход, проверить базовый случай рекурсии и оценить худшую форму дерева. Такой подход превращает тему из набора терминов в понятную систему алгоритмических действий.