ГоловнаЗворотній зв'язок
Главная->Математика і інформатика->Содержание->3.2. Абстрактный тип данных TREE

Алгоритмы структуры данных

3.2. Абстрактный тип данных TREE

В главе 2 списки, стеки, очереди и отображения получили трактовку как абстрактные типы данных (АТД). В этой главе рассмотрим деревья как АТД и как структуры данных. Одно из наиболее важных применений деревьев — это использование их при разработке реализаций различных АТД. Например, в главе 5 мы покажем, как можно использовать "дерево двоичного поиска" при реализации АТД, основанных на математической модели множеств. В следующих двух темах будут представлены многочисленные примеры применения деревьев при реализации различных абстрактных типов данных.

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

1.    PARENT(n, Т). Эта функция возвращает родителя (parent) узла л в дереве Т. Если п является корнем, который не имеет родителя, то в этом случае возвращается Л. Здесь Л обозначает "нулевой узел" и указывает на то, что мы выходим за пределы дерева.

2.    LEFTMOST_CHILD(n, Т). Данная функция возвращает самого левого сына узла п в дереве Т. Если n является листом (и поэтому не имеет сына), то возвращается Л.

3.    RIGHT_SIBLING(n, Т). Эта функция возвращает правого брата узла n в дереве Т и значение Л, если такового не существует. Для этого находится родитель р узла n и все сыновья узла р, затем среди этих сыновей находится узел, расположенный непосредственно справа от узла n. Например, для дерева на рис. 3.6 LEFTMOST_CHILD(n2) = п4, RIGHT_SIBLING(n4) = n5 и RIGHT_SIBLING(n5) = Л.

4.    LABEL(n, Т). Возвращает метку узла n дерева Т. Для выполнения этой функции требуется, чтобы на узлах дерева были определены метки.

5.    CREATEi(v, t1, T2, .... Тi) — это обширное семейство "созидающих" функций, которые для каждого і = О, 1, 2, ... создают новый корень г с меткой v и далее для этого корня создает і сыновей, которые становятся корнями поддеревьев Т1, Т2, ..., Тi. Эти функции возвращают дерево с корнем r. Отметим, что если і = 0, то возвращается один узел г, который одновременно является и корнем, и листом.

6.    ROOT(T) возвращает узел, являющимся корнем дерева Т. Если Т — пустое дерево, то возвращается Л.

7.    MAKENULL(T). Этот оператор делает дерево Т пустым деревом.

Пример 3.5. Напишем рекурсивную PREORDER и нерекурсивную NPREORDER процедуры обхода дерева в прямом порядке и составления соответствующего списка его меток. Предположим, что для узлов определен тип данных node (узел), так же, как и для типа данных TREE (Дерево), причем АТД TREE определен для деревьев с метками, которые имеют тип данных labeltype (тип метки). В листинге 3.2 приведена рекурсивная процедура, которая по заданному узлу п создает список в прямом порядке меток поддерева, корнем которого является узел п. Для составления списка всех узлов дерева Т надо выполнить вызов PREORDER(ROOT(T)).

Листинг 3.2. Рекурсивная процедура обхода дерева в прямом порядке

procedure PREORDER ( n: node );

var

с: node;

begin

print(LABEL(n,    T));

c:=  LEFTMOST_CHILD(n,    Т);

while с <> Λ do begin

PREORDER(с) ;

 c:= RIGHT_SIBLING(c,   T)

end

end;   {   PREORDER   }

Теперь напишем нерекурсивную процедуру для печати узлов дерева в прямом порядке. Чтобы совершить обход дерева, используем стек S, чей тип данных STACK уже объявлен как "стек для узлов". Основная идея разрабатываемого алгоритма заключается в том, что, когда мы дошли до узла п, стек хранит путь от корня до этого узла, причем корень находится на "дне" стека, а узел п — в вершине стека.

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

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

Программа начинается в первом режиме с нахождения корня дерева и определения, является ли стек пустым. В листинге 3.3 показан полный код этой программы.

 

Листинг 3.3. Нерекурсивная процедура обхода дерева в прямом порядке

procedure NPREORDER ( Т: TREE );

var

m: node; { переменная для временного хранения узлов }

S: STACK; { стек узлов, хранящий путь от корня до

родителя ТОР(S) текущего узла т }

begin { инициализация }

MAKENULL(S);

m: = ROOT (Г) ;

while true do

if m <> Λ then begin

print (LABEL (m, Т));

PUSH(m, S) ;

{ исследование самого левого сына узла m }

m:= LEFTMOST_CHILD(m, T)

end

else begin

{ завершена проверка пути, содержащегося в стеке }

if EMPTY(S) then

return;

{ исследование правого брата узла,

находящегося в вершине стека}m:= RIGHT_SIBLING(ТОР(S), Т); POP(S)

          end

end; { NPREORDER }

 

35