Обход бинарных деревьев

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

Существует несколько принципиально разных способов обхода дерева:

Обход в прямом порядке

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

Для корня дерева рекурсивно вызывается следующая процедура:

Посетить узелОбойти левое поддеревоОбойти правое поддерево

Примеры использования обхода:

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

Симметричный обход

Посещаем сначало левое поддерево, затем узел, затем - правое поддерево.

Для корня дерева рекурсивно вызывается следующая процедура:

Обойти левое поддеревоПосетить узелОбойти правое поддерево

Обход в обратном порядке

Узлы посещаются 'снизу вверх'.

Для корня дерева рекурсивно вызывается следующая процедура:

Обойти левое поддеревоОбойти правое поддеревоПосетить узел

Примеры использования обхода:

• анализ игр с полной информацией
• разузлование снизу
• динамическое программирование

Обход в ширину

При обходе в ширину узлы посещаются уровень за уровнем(N-й уровень дерева - множество узлов с высотой N). Каждый уровень обходится слева направо.

Для реализации используется структура queue - очередь с методами

• enqueue - поставить в очередь
• dequeue - взять из очереди
• empty - возвращает TRUE, если очередь пуста, иначе - FALSE

q.enqueue(root); // корень в очередьwhile (! q.empty) { x = q.dequeue(); visit x; // посетить x if (! x.left.empty) // x.left - левое поддерево q.enqueue(x.left); if (! x.right.empty) // x.right - правое поддерево q.enqueue(x.right);}

Рекурсивные обходы можно, очевидно, организовать и с помощью стека, 'развернув' рекурсию.

Прошитые деревья

Хитроумный способ экономного использования памяти предложен А. Дж. Перлисом и Ч. Торнтоном, которые придумали метод прошитого (threaded) представления бинарного дерева. В этом методе концевые связи заменяются "нитями" (threads), которые связаны с другими частями дерева для упрощения его обхода. Прошитое дерево выглядит следующим образом:

Здесь пунктиром обозначены "нити", которые всегда направлены к более высокому узлу дерева. Каждый узел теперь имеет две связи. Некоторые узлы, например C, имеют две обычные связи с левым и правым поддеревьями, другие узлы, например H, - две связи в виде "нитей", а третьи по одной связи каждого типа. Две особые нити появляются в крайнем левом и крайнем правом узлах дерева, они указывают на вспомогательный элемент дерева HEAD, который мы опишем позже.

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

Пусть теперь:

• P - узел дерева
• LLINK(P), RLINK(P) - левый и правый ребенок узла P
• LTAG(P), RTAG(P) - флаги. Если значение флага 0, то соответствующая ему связь обычная, в противном случае, соответствующая связь пунктирная ("нить")

Определим элемент HEAD следующим образом:

• LLINK(HEAD) = A
• RLINK(HEAD) = HEAD
• LTAG(HEAD) = 0
• RTAG(HEAD) = 0

Преимуществом прошитых деревьев является то, что алгоритмы обхода для них упрощаются.

Пусть теперь: Если LLINK(P) - нить, то LLINK(P) указывает на узел предшествующий узлу P при симметричном обходе дерева (LPR-обход), а RLINK(P) указывает на узел последующий за узлом P при том же обходе. Тогда следующий алгоритм находит последующий за узлом P узел при симметричном обходе:

Алгоритм NEXT(P): возвращает узел, следующий за узлом P при симметричном обходе

NEXT(P): 1. Q = RLINK(P) Идем вправо 2. if RTAG(P) == 1 Если связь, то она уже указывает на следующий return Q элемент. Остановка. 3. while LTAG(Q) == 0: Если это поддерево, то спускаемся вниз по левой Q = LLINK(Q) ветке 4. return Q

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

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

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

ADDRIGTH(P, Q): 1. RLINK(Q) = RLINK(P) Правое поддерево узла P становится правым поддеревом узла Q 2. RTAG(Q) = RTAG(P) Копируем признак "нити" 3. RLINK(P) = Q Добавляем узел Q, как правое поддерево к P 4. RTAG(P) = 0 Теперь правая связь узла P точно не "нить" 5. LLINK(Q) = P Теперь узел P предшествует узлу Q в симметричном обходе дерева 6. LTAG(Q) = 1 Левая связь добавленного узла - это "нить" 7. if RTAG(Q) = 0: Если у P было правое поддерево, нам необходимо LLINK(NEXT(Q)) = Q установить правильную нить

Алгоритм NEXT не использует левые "нити\" и будет работать корректно

Отметим, что шаг 7 выполняется только в случае, когда у узла P уже есть правое поддерево. Если мы собираемся добавлять элементы, только в качестве листьев, то алгоритм ADDRIGHT не зависит от NEXT. Симметричным образом могут быть написаны алгоритмы PREV и ADDLEFT

Процессы сортировки

Статья на Wikipedia - http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B8