Методы программирования. Громов Ю.Ю - 39 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

39
6. ПРОХОЖДЕНИЕ ДЕРЕВЬЕВ
Все алгоритмы обработки древовидных структур неизменно связаны
с прохождением деревьев. Под прохождением дерева понимается способ
методичного исследования его узлов, при котором каждый узел прохо-
дится точно один раз. Полное прохождение дерева даёт линейную рас-
становку его узлов.
Рассмотрим три способа прохождения бинарного дерева: прямой
порядок, обратный порядок и концевой порядок. Каждый из них выпол-
няется в три этапа.
Прямой порядок: попасть в корень, пройти левое поддерево, пройти
правое поддерево.
Обратный порядок: пройти левое поддерево, попасть в корень,
пройти правое поддерево.
Концевой порядок: пройти левое поддерево, пройти правое поддере-
во, попасть в корень.
При прямом порядке прохождения дерева (см. рис. 14 из предыду-
щего параграфа) узлы располагаются в порядке A, B, D, C, E, G, F, H, J;
при обратном − в порядке D, B, A, E, G, C, H, F, J и при концевом − D, B,
G, E, H, J, F, C, A.
Рассмотрим алгоритм прохождения бинарного дерева в обратном
порядке.
Алгоритм Т. (Обход бинарного дерева в обратном порядке.)
Пусть Т − указатель на бинарное дерево, имеющее представление,
аналогичное рис. 15; А − вспомогательный стек.
Т1. [Начальная установка.] Очистить стек А; Р ← Т.
Т2. [Р = Λ?] Если Р = Λ, перейти к шагу Т4.
Т3. [Стек ⇐ Р] (Теперь Р указывает на непустое бинарное дерево,
которое нужно пройти.) А ⇐ Р, Р ← LLINK(P) и вернуться к шагу Т2.
Т4. [Р ⇐ стек] Если стек А пуст, то работа алгоритма заканчивается;
в противном случае Р ⇐ A .
Т5. [Попасть в Р] «Попасть» в NODE(P), P ← RLINK(P) и вернуться
к шагу Т2. ■
Для удобства дальнейших рассуждений введём следующие обозна-
чения. Если Р указывает на узел бинарного дерева, то:
Р* – адрес преемника узла NODE(P) в прямом порядке;
Р$ – адрес преемника узла NODE(P) в обратном порядке;
Р# – адрес преемника узла NODE(P) в концевом порядке;
*Р – адрес предшественника узла NODE(P) в прямом порядке;
$P – адрес предшественника узла NODE(P) в обратном порядке;
#P – адрес предшественника узла NODE(P) в концевом порядке.
Тогда *(Р*) = (*Р)* =Р, $(P$) = ($P)$ = P и т.д.

Страницы