Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Обход бинарного дерева. Виды обхода дерева. Прошитое дерево

На главную Математический раздел Криптография и т.д. Новости

1. Виды обхода бинарного дерева

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

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

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

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

Обход в ширину: посещаем корень, далее посещаем узлы первого уровня (то есть сыновей корня) слева направо, далее - узлы второго уровня ("внуков" корня) слева направо и т.д. Также обход в ширину можно встретить под названием волновой алгоритм - порядок обхода сильно напоминает движение волны. Волновой алгоритм может оказаться полезен, когда среди узлов дерева, некоторые из которых обладают свойством P, нужно найти ближайший к корню узел со свойством P. Например, узлы дерева - ситуации в игре-головоломке, корень соответствует исходному положению в игре, свойство P - "найдено решение". Тогда волновой алгоритм даст кратчайшее решение.

2. Программисту: нерекурсивные обходы и прошитое дерево

Также можно разработать нерекурсивные аналоги прямого, симметричного и обратного обхода. Например, можно нерекурсивно вывести ключи узлов бинарного дерева поиска по следующему алгоритму. Пусть N - только что обработанный узел узел, нужно определить узел S, который будет обработан следующим. Обозначим RN - корень правого поддерева N (правый сын N). 1. Если у N непустое правое поддерево, то S - самый левый узел правого поддерева (то есть узел, в котором мы остановимся, при спуске от RN всегда поворачивая влево). Если у RN нет левого сына, то S=RN. 2. Если у N нет правого поддерева и N - корень всего обрабатываемого дерева, то обход завершен. 3. Если у N нет правого поддерева и N - левый сын своего родителя, то S - родитель N. 4. Если у N нет правого поддерева и N - правый сын своего родителя, то мы восходим по дерева, пока не найдем узел Q, являющийся левым сыном своего родителя. Если такой узел найден, то S - родитель Q, иначе N - узел с максимальным ключом.

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

Если требуется многократно обходить бинарное дерево в одном и том же порядке (например, регулярно ведя поиск некоторых данных), то полезно сделать обход эффективнее. Это можно организовать следующим образом. В каждом узле есть по две ссылки на сыновей. Когда у узла меньше двух потомков, эти ссылки "пустуют". Их можно использовать для указания на последователей/предшественников узла по обходу. Нужно только каждой ссылке поставить в соответствие флаг, показывающий, данная ссылка указывает на сына или на соседа по обходу. Такая структура называется прошитым деревом, а обработка дерева для установки наших "особенных" ссылок - прошиванием дерева. Так, для прошивания дерева при симметричном порядке обхода можно адаптировать выше упомянутый алгоритм.

3. Некоторые применения алгоритмов обхода дерева

Некоторые вопросы применения обходов дерева уже рассмотрены выше в статье. В данном разделе немного дополним эту тему.

Деревья и арифметические выражения. Арифметические выражения можно представлять с помощью бинарных деревьев (см. рис. 6). Листьям дерева соответствуют операнды, внутренним узлам - операции. В зависимости от разных способов обхода дерева получаем разные формы записи арифметического выражения. Симметричный обход дает инфиксную запись, то есть привычную нам, когда знак операции между операндами. Прямой обход дает префиксную запись - знак операции ставится перед операндами. Обратный обход дает постфиксную запись - знак операции ставится после операндов. Из-за этого названные обходы иногда называют соответственно как инфиксный обход, префиксный обход, постфиксный обход.

Сортировка вставками в дерево. Выше мы уже говорили, что симметричный обход бинарного дерева поиска дает сортировку ключей узлов. Мы можем сортировать массивы следующим образом. Каждый элемент массива вставляем в бинарное дерево поиска (первый элемент - в качестве корня и т.д.). Для полученного дерева выполняем симметричный обход и получаем отсортированную последовательность.

copyright © Исканцев Н.В., 2014

К математическому разделу
На главную
X