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

type

node = integer;

LIST = { соответствующее определение для списка узлов ); position = {соответствующее определение позиций в списках}; TREE = record

header: array[1..maxnodes] of LIST;

labels: array [ 1..maxnodes] of labeltype;

roo t: node

end;

2 3 4 5 6 7 8 9 10


header

Puc. 3.8. Представление дерева с помощью связанных списков

Мы предполагаем, что корень каждого дерева хранится отдельно в ноле root (корень). Для обозначения нулевого узла используется 0.

В листинге 3.5 представлен код функции LEFTMOST CHILD. Читатель в качестве упражнения может написать коды других операторов.

Листинг 3.5. Функция нахождения самого левого сына

function LEFTMOST CHILD { n: node; Т: TREE ) : node;

{ возвращает самого левого сына узла л дерева Т } var

L: LIST; { скоропись для списка сыновей узла л } begin

L:= Т.header[п] ;

if EMPTY(L) then { л является листом } return(0>

else

return(RETRIEVE(FIRST(X), L))

end; { LEFTMOST CHILD }

Теперь представим конкретную реализацию списков, где тины LIST и position имеют тин целых чисел, последние используются как курсоры в массиве записей cellspace (область ячеек):

cellspace: array[1. .maxnode.s] of record

node: integer;

next: integer

end;



Для упрощения реализации можно положить, что списки сыновей не имеют ячеек заголовков. Точнее, мы поместим T./zeade/fra] непосредственно в первую ячейку списка, как показано на рис. 3.8. В листинге 3.6 представлен переписанный (с учетом этого упрощения) код функции LEFTMOST CHILD, а также показан код функции PARENT, использующий данное представление списков. Эта функция более трудна для реализации, так как определение списка, в котором находится заданный узел, требует просмотра всех списков сыновей.

Листинг 3.6. функции, использующие представление деревьев посредством связанных списков

function LEFTMOST CHILD { п: node; Т: TREE ): node;

{ возвращает самого левого сьиа узла п дерева Т } var

X: integer; { курсор на начало списка сьиовей узла п } begin

L: = Г.header[п] ;

if I/ = О then { л является листом } return(0)

else

return (cellspace I L] .node) end; { LEFTMOST CH1LD }

function PARENT { n: node; T: TREE ): node; { возвращает родителя узла л дерева Т } var

р: node; { пробегает возможных родителей узла п } i: position; { пробегает список сыиовей р } begin

for р:= 1 to maxnodes do begin i: = T. header [p] ,-

while i <> 0 do { проверка на наличие сыиовей узла р } if cellspace[i].node = л then return(p>

else

i:= celispace[i].next

end;

return(0) { родитель не найден } end; { PARENT }

Представление левых сыновей и правых братьев

Среди прочих недостатков описанная выще структура данных не позволяет также с помощью операторов CREATEi создавать больщие деревья из малых. Это является следствием того, что все деревья совместно используют массив сеШрасе аля представления связанных списков сыновей; по сути, каждое дерево имеет собственный массив заголовков для своих узлов. А при реализации, например, оператора CREATE2(i;, Tj, Тг) надо скопировать деревья и Тг в третье дерево и добавить новый узел с меткой v и двух его сыновей - корни деревьев ТуН Тг.

Если мы хотим построить больщое дерево на основе нескольких малых, то желательно, чтобы все узлы всех деревьев располагались в одной общей области. Логическим продолжением представления дерева, показанного на рис. 3.8, будет замена массива заголовков на отдельный массив nodespace (область узлов), содержащий записи с произвольным местоположением в этом массиве. Содержимое поля header этих записей соответствует "номеру" узла, т.е. номеру записи в массиве cellspace, в



свою очередь поле node массива cellspace теперь является курсором для массива nodespace, указывающим позицию узла. Тип TREE в этой ситуации просто курсор в массиве nodespace, указывающий позицию корня.

Пример 3.7. На рис. 3.9, а показано дерево, а на рис. 3.9, б - структура данных, где узлы этого дерева, помеченные как А, В, С ти D, размещены в произвольных позициях массива nodespace. В массиве cellspace также в произвольном порядке размещены списки сыновей. □

а. Дерево Т

--11

Поля label header МассиЕ! nodespace


15 >

2

Поля node next Массив cellspace

б. Структуры данных Рис. 3.9. Структура данных для дерева, использующая связанные списки

Структура данных, показанная на рис. 3.9, б, уже подходит для того, чтобы организовать слияние деревьев с помощью операторов CREATE!. Но и эту структуру мокно значительно упростить. Для этого заметим, что цепочка указателей поля next массива cellspace перечисляет всех правых братьев.

Используя эти указатели, можно найти самого левого сына следующим образом. Предположим, что ceUspace[i\.node- п. (Повторим, что "имя" узла, в отличие от его метки, является индексом в массиве nodespace и этот индекс записан в поле сей-spacc[(].node.) Тогда указатель гаойс8расс[га].Леас/егуказывает на ячейку самого левого сына узла п в массиве cellspace, поскольку поле node этой ячейки является именем этого узла в массиве nodespace.

Мокно упростить структуру, если идентифицировать узел не с помощью индекса в массиве nodespace, а с помощью индекса ячейки в массиве cellspace, который соответствует данному узлу как сыну. Тогда указатель next (переименуем это поле в right sibUng- правый брат) массива cellspace будет точно указывать на правого брата, а информацию, содержащуюся в массиве nodespace, мокно перенести в новое поле leftmost child(caMbm левый сын) массива cellspace. Здесь тип TREE является целочисленным типом и используется как курсор в массиве cellspace, указывающий на корень дерева. Массив cellspace можно описать как следующую структуру:

cellspace: array [1. ./naxnodes] of record label: labeltype; leftmost child: integer; right sibling: integer

end;





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