Главная Промышленная автоматика.

метками, которые имеют тип данных labeltype (тип метки). В листинге 3.2 приведена рекурсивная процедура, которая по заданному узлу и создает список в прямом порядке меток поддерева, корнем которого является узел п. Для составления списка всех узлов дерева Т надо выполнить вызов PREORDER(ROOT(T)).

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

procedure PREORDER { л: node ) ; var

С: node; begin

print (LABEL (п. Г));

c:= LEFTMOST CHlLD(n, T) ;

while с о Л do begin

PREORDER (c) ;

C:= RIGHT SIBLING(c, T)

end; j PREORDER j

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

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

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

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

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

procedure NPREORDER { Т.- TREE ) ; var

т: node; { переменная для временного хранения узлов } 5: STACK; { стек узлов, хранящий путь от корня до родителя TOP(S) текущего узла т } begin { инициализация } MAKENULL(S); m: = ROOT (г) ; while true do

if ill о Л then begin

print (LABEL (m, T) ) ; PUSH(n7, S) ;

Можно вернуться к разделу 2.6, где обсу>1<далась реализация рекурсивных процедур с помошью стека активационных записей. При рассмотрении листинга 3.2 нетрудно заметить, что активационную запись можно заносить в стек при каждом вызове процедуры PREORDER(n) и, это главное, стек будет содержать активационные записи для всех предков узла п.



{ исследование самого левого сьиа узла т } Л1:= leftm0st CHILD(n7, Т)

else begin

{ . завершена проверка гт/ти , содержащегося в стеке } if EMPTY (S) then return;

{ исследование гавого брата узла, находящегося в вершине стека } т:= RIGHT SIBLING(TOP(S> , Т) ; POP ( S)

end; { NPREORDER }

З.З.Реализациядеревьев

в этом разделе мы представим несколько основных реализаций деревьев и обсудим их возможности для поддержки операторов, введенных в разделе 3.2.

Представление деревьев с помощью массивов

Пусть Т- дерево с узлами 1, 2, и. Возможно, самым простым представлением дерева Т, поддерживающим оператор PARENT (Родитель), будет линейный массив А, где каждый элемент является указателем или курсором на родителя узла L Корень дерева Т отличается от других узлов тем, что имеет нулевой указатель или указатель на самого себя как на родителя. В языке Pascal указатели на элементы массива недопустимы, поэтому мы будем использовать схему с курсорами, тогда Ali] = j, если узел / является родителем узла i, я Alt] = О, если узел i является корнем.


1] 1 225]55[~

а

б. Курсоры на родителей Рис. 3. 7. Дерево и курсоры на родителей



Данное представление использует то свойство деревьев, что каждый узел, отличный от корня, имеет только одного родителя. Используя это представление, родителя любого узла можно найти за фиксированное время. Прохождение по любому пути, т.е. переход по узлам от родителя к родителю, можно выполнить за время, пропорциональное количеству узлов пути. Для реализации оператора LABEL можно использовать другой массив L, в котором элемент L\i\ будет хранить метку узла /, либо объявить элементы массивам! записями, состоящими из целых чисел (курсоров) и меток.

Пример 3.6. На рис. 3.7 показаны дерево и массив А курсоров на родителей этого дерева. D

Использование указателей или курсоров на родителей не помогает в реализации операторов, требующих информацию о сыновьях. Используя описанное представление, крайне тяжело для данного узла и найти его сыновей или определить его высоту. Кроме того, в этом случае невозможно определить порядок сыновей узла (т.е. какой сын находится правее или левее другого сына). Поэтому нельзя реализовать операторы, подобные LEFTMOSTCHILD и RIGHT SIBLING. Можно ввести искусственный порядок нумерации узлов, например нумерацию сыновей в возрастающем порядке слева направо. Используя такую нумерацию, можно реализовать оператор RIGHT SIBLING, код для этого оператора приведен в листинге 3.4. Для задания типов данных node (узел) и TREE (Дерево) используется следующее объявление:

type

node = integer;

TREE = array [1. .maxnodes] of node; В этой реализации мы предполагаем, что нулевой узел Л представлен 0.

Листинг 3.4. Оператор определения правого брата

procedure RIGHT SIBLING ( л: node; Т: TREE ) : node; var

i, parent: node; begin

parent:= T[n] ; for i: - П + 1 to maxnodes do if r[i] = parent tlien

return (i) ; retum(O) { правый брат не найден } end; { RIGHT SIBLING }

Представление деревьев с использованием списков сыновей

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

На рис. 3.8 показано, как таким способом представить дерево, изображенное на рис. 3.7, а. Здесь есть массив ячеек заголовков, индексированный номерами (они же имена) узлов. 1Саждый заголовок (header) указывает на связанный список, состоящий из "элементов"-узлов. Элементы списка /wader[i]являются сыновьями узла i, например узлы 9 и 10 - сыновья узла 3.

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





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 [24] 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0037