EssayAI
Блог
Блог
Естественные науки

Обходы двоичного дерева: порядки и примеры

8 ноября 2026Время чтения: 8 минут
#двоичное дерево#обход дерева#рекурсия#алгоритмы#структуры данных
Обходы двоичного дерева: порядки и примеры

Обход двоичного дерева - это способ посетить его узлы в определённом порядке. Одно и то же дерево можно прочитать несколькими последовательностями: например, обработать родителя до его потомков или дождаться результатов обоих поддеревьев. Порядок важен, когда нужно скопировать структуру, вычислить выражение или вывести ключи.

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

Дерево для примера и значение посещения

У корня 1 два ребёнка: 2 слева и 3 справа. У узла 2 дети 4 и 5, у узла 3 - 6 и 7. Узлы 4, 5, 6 и 7 - листья. В примере числа служат именами, а не обязательно ключами дерева поиска. Левое и правое поддеревья различаются даже тогда, когда у узла есть только один ребёнок.

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

Прямой обход: корень, левое, правое

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

Для примера получаем 1, 2, 4, 5, 3, 6, 7. Сначала записываем 1, затем переходим к 2 и его листьям 4 и 5. Лишь завершив всю левую часть, посещаем 3, 6 и 7. Анимация показывает именно моменты записи узлов; переход выделения не обозначает обязательный путь по одному ребру.

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

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

Симметричный обход: левое, корень, правое

При симметричном обходе, или inorder, сначала полностью обрабатывается левое поддерево, затем текущий узел и наконец правое. Для нашего дерева результат - 4, 2, 5, 1, 6, 3, 7. Корень 1 оказывается между всеми узлами левого и правого поддеревьев. То же верно для узла 2: сначала 4, затем 2, затем 5.

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

Четыре последовательности обхода одного дерева из семи узлов
Четыре последовательности обхода одного дерева из семи узлов

Обратный обход: левое, правое, корень

Обратный обход, или postorder, посещает узел после обоих поддеревьев. В примере это 4, 5, 2, 6, 7, 3, 1: сначала завершается ветвь 2, затем ветвь 3, а общий корень записывается последним.

Такой порядок подходит для вычислений, где результат родителя зависит от результатов детей. Например, в дереве арифметического выражения сначала вычисляют операнды, а затем применяют операцию в родительском узле. Аналогично при освобождении связанных узлов сначала обрабатывают потомков, пока ссылки на них доступны. «Обратный» здесь не означает простое чтение прямой последовательности справа налево: сравните приведённые семь чисел.

Рекурсивный алгоритм трёх обходов

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

def traverse(node, order, visit):
    if node is None:
        return
    if order == "pre":
        visit(node.value)
    traverse(node.left, order, visit)
    if order == "in":
        visit(node.value)
    traverse(node.right, order, visit)
    if order == "post":
        visit(node.value)

Перед вызовом выберите одно из трёх допустимых значений order. Базовый случай проверяет сам текущий узел, поэтому вызов с пустым корнем безопасен. После возврата из левой ветви выполнение продолжается со следующей строки в вызове родителя. Правила этих трёх порядков также приведены в учебных материалах OpenDSA о двоичных деревьях.

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

Обход по уровням и очередь

Обход по уровням - level order - идёт сверху вниз, а внутри каждого уровня в нашем соглашении слева направо. Для того же дерева он даёт 1, 2, 3, 4, 5, 6, 7. Здесь используется очередь: первым выходит тот узел, который первым в неё попал.

Начните с очереди [1]. Извлеките 1, посетите его и добавьте 2, затем 3: получится [2, 3]. После извлечения 2 и добавления его детей очередь станет [3, 4, 5]. Узел 3 уже ждал раньше, поэтому обрабатывается до 4 и 5; затем в конец попадают 6 и 7. Продолжайте до пустой очереди, добавляя только существующих детей.

Это частный случай обхода графа в ширину. У обычного дерева каждый узел имеет единственный путь от корня, поэтому отдельное множество посещённых не требуется. Для произвольного графа с циклами оно необходимо, чтобы не возвращаться бесконечно. Обходы preorder и postorder, напротив, связаны с идеей обхода в глубину.

Как пройти дерево без рекурсии

Для прямого обхода можно хранить ожидающие узлы в явном стеке. Положите в него корень, затем повторяйте действия, пока стек не пуст: извлеките верхний узел, посетите его, положите правого ребёнка и после него левого, если они существуют. Поскольку стек отдаёт последний добавленный элемент первым, левый ребёнок будет обработан раньше правого. В нашем примере после посещения 1 стек содержит 3 и 2, причём 2 лежит сверху. После обработки 2 сверху окажется 4, а 5 и 3 будут ждать своей очереди.

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

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

Сложность и выбор способа

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

Рекурсивным обходам нужна память стека O(h+1)O(h+1), где hh - высота в рёбрах: одновременно активны вызовы вдоль одного пути. Для цепочки эта величина достигает O(n)O(n), и ограничение глубины рекурсии языка может стать практической проблемой. Итеративный вариант с явным стеком помогает контролировать память программы, хотя асимптотическая оценка остаётся той же.

Очередь обхода по уровням требует O(w)O(w) дополнительной памяти, где ww - максимальная ширина, то есть наибольшее число узлов на одном уровне. В очереди одновременно могут находиться части двух соседних уровней, но их суммарный размер ограничен величиной порядка ww. Запись готового списка из nn значений в обоих случаях дополнительно занимает O(n)O(n); при обработке на лету хранить весь вывод не обязательно.

Частые ошибки

  • Менять правило внутри поддерева. Если выбран inorder, левую и правую части тоже нужно обходить в этом порядке.
  • Считать inorder сортировкой любого дерева. Упорядоченность результата следует из свойства дерева поиска, а не из самого алгоритма.
  • Записывать узел при каждом возврате. Проход может несколько раз касаться родителя, но выбранный полный обход посещает его один раз.
  • Путать стек и очередь. Стек извлекает последний добавленный элемент; очередь - первый. Поэтому порядок обработки различается.
  • Забывать пустых детей. Рекурсивная функция должна завершаться на пустой ссылке, а очередь не должна получать отсутствующие узлы.

FAQ

Можно ли восстановить дерево по одному обходу?

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

Чем обход отличается от поиска?

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

Какой обход выбрать для вычисления выражения?

Обычно обратный: значения дочерних выражений готовы до обработки операции в родителе. Для вывода выражения в привычной записи применяют симметричный порядок с необходимыми скобками.

Коротко

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

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: построение и операции

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

8 ноября 20268 минут
Высота и глубина дерева: формулы и примеры

Высота и глубина дерева: формулы и примеры

Разбираем высоту и глубину дерева в информатике: точные определения, формулы для полного двоичного и вырожденного дерева, примеры задач и типичные ошибки.

11 июня 20268 минут
Ханойские башни и рекурсия: решение по шагам

Ханойские башни и рекурсия: решение по шагам

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

8 ноября 20268 минут
Односвязный список: операции и их сложность

Односвязный список: операции и их сложность

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

8 ноября 20269 минут
Префиксное дерево: как устроен бор строк

Префиксное дерево: как устроен бор строк

Префиксное дерево хранит общие начала строк вместе. Разбираем построение бора, поиск и удаление слов, сложность операций и применение на наглядном примере.

8 ноября 20268 минут
Сортировка слиянием: как работает merge sort

Сортировка слиянием: как работает merge sort

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

8 ноября 20268 минут