TI Инициализачия

• RLINK(P)

Рис. 23. Алгоритм Т для симметричного обхода.

Алгоритм Т [Обход дерева в симметричном порядке). Пусть Т - указатель на бинарное дерево с представлением (2). Тогда в этом алгоритме (рис. 23) все узлы бинарного дерева обходятся в симметричном порядке с помощью вспомогательного стека А.

Т1. [Инициализация.] Опустошить стек А и установить переменную связи Р 4- Т. Т2. [Р = Л?] Если Р = Л, перейти к шагу Т4.

ТЗ. [Стек Р.] (Теперь Р указывает на непустое бинарное дерево, которое нужно пройти.) Установить А < Р, т. е. вставить (протолкнуть) значение Р в стек А (см. раздел 2.2.1). Затем установить Р 4- LLINK(P) и вернуться к шагу Т2.

Т4. [Р <j= Стек.] Если стек А пуст, выполнение алгоритма прекращается; в противном случае установить Р < А.

Т5. [Попасть в Р.] Попасть в узел NODE(P). Затем установить Р <- RLINK (Р) и вернуться к шагу Т2.

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

Чтобы понять идею, лежащую в основе этого алгоритма, читатель может в качестве полезного упражнения применить алгоритм Т к бинарному дереву (2). По достижении шага ТЗ следует приступить к обходу бинарного дерева с корнем, на который указывает Р. При этом основная идея заключается в сохранении указателя Р в стеке с последующим обходом левого поддерева. После вьтолнения этих действий необходимо вернуться к шагу Т4 и найти прежнее значение Р в стеке. После обхода корня NODE(P) на шаге Т5 остается только совершить обход правого поддерева.

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

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

Начиная с шага Т2 с указателем Р на бинарное дерево с п узлами и стеком А, содержащим элементы А [1] ... А [т] для некоторого m > О, эта процедура на шагах Т2-Т5 совершит обход бинарного дерева в симметричном порядке, а зате.м вернется к шагу Т4 с возвратом стека А в его исходное состояние А [1] ... А [т].

Для п = О это утверждение очевидно вьшолняется, как следствие шага Т2. Есди п > О, пусть Ро является значением указателя Р в начале шага Т2. Так как Ро ф Л, выполним шаг ТЗ, что для стека А означает его изменение с приведением к новому состоянию с элементами А[1] ...А[т]Ро, а Р равняется LLINK(Po). Теперь левое поддерево имеет меньше п узлов, а потому по индукции выполним обход левого поддерева в симметричном порядке и перейдем к шагу Т4 со стеком, содержание которого равно А [1] ... А [т] Ро. На шаге Т4 стек возвращается в исходное состояние А[1] ... А[т], а Р 4- Pq. На шаге Т5 выполняется обход узла NODE(Po) и устанавливается значение Р 4- RLINK (Ро). Теперь правое поддерево имеет менее п узлов и по индукции совершаем обход правого хюддерева в симметричном порядке с переходом к шагу Т4. Таким образом выполнен обход всего дерева в сим.метричном порядке согласно определению этого порядка. Доказательство завершено.

Практически идентичный алгоритм .можно сформулировать для обхода бинарных деревьев в прямом порядке (см. упр. 12). Несколько сложнее выглядит алгоритм обхода в обратном порядке (см. упр. 13), а потому подобный порядок не имеет такого большого значения, как два других.

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

Р+ - адрес узла-последователя NODE(P) при обходе в прямом порядке; Р$ - адрес узла-последователя NODE(P) при обходе в симметричном порядке; Ре - адрес узла-последователя NODE(P) при обходе в обратном порядке; *Р - адрес узла-предшественника NODE(P) при обходе в прямом порядке; SP - адрес узла-предшественника NODE(P) при обходе в симметричном порядке; JP - адрес узла-предшественника NODE(P) при обходе в обратном порядке.

Если узел NODE(P) не имеет узлов-предшественников и узлов-последователей, то обычно используется обозначение LOC(T), где Т - это внешний указатель на данное дерево. Таким образом, получаем +(Р+) = (+Р)+ = Р, s(Ps) = (sP)$ = Р и «(Рц) = (tlP)tt = Р. В качестве примера использования этих обозначений предположим, что INFO(P)-это буква, изображенная в узле NODE(P) дерева (2). Тогда, если Р указывает на его корень, получим INFO(P) = А, INFO(P+) = В, INFO(Ps) = Е, INFO($P) = В, INFO(ttP) = С и Рв = *Р = LOC(T).

Здесь у читателя может возникнуть чувство неуверенности в отношении правильности приведенных значений Р+, Р$ и т. д. Однако по мере изучения дальнейшего материала они станут более понятными, в частности для этого полезно выполнить упр. 16, приведенное в конце раздела. Символ "$" в обозначении "Р$"

представляет букву S в английском написании термина "симметричный порядок" (symmetric order).

Существует еще один,, альтернативный вариант представления бинарных деревьев (2) в памяти компьютера, который отличается от предыдущего способа так же, как циклические списки отличаются от линейных однонаправленных списков. Обратите внимание на то, что в дереве (2) пустых связей содержится больше, чем всех остальных; и действительно, это верно для любого дерева, представленного с помощью обычного метода (см. упр. 14). На самом деле вряд ли стоит из-за этого так неэкономно расходовать пространство памяти. Вместо этого можно было бы, например, хранить в каждом узле некий двухбитовый "признак" (tag) того, что узел содержит либо пустую, либо непустую связь LLINK (или RLINK), либо обе пустые, либо обе непустые связи. В таком случае высвободившееся пространство в памяти, которое прежде использовалось для концевых связей, можно применять в других целях.

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

Здесь пунктиром обозначены "нити", которые всегда направлены к более высокому узлу дерева. Каждый узел теперь имеет две связи: одни узлы, например С, имеют две обычные связи с левым и правым поддеревьями, другие узлы, например Я,- две связи в виде нИтей, а третьи -по одной связи каждого типа. Особые нити, которые выходят из узлов D и /, будут рассмотрены ниже. Они появляются в крайнем слева и крайнем справа узлах.

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

Обычное представление

LLINK(Р) = Л LLINK (Р) =QA RLINK(Р) = Л RLINK (Р) = Q 7 Л

Прошитое представление

LTAG(P) = 1, LLINK(Р) = $Р

LTAG(P) = О, LLINK(Р) = Q

RTAG(P) = 1, RLINK(Р) = Р$

RTAG(P) = О, RLINK(P) = Q