Структуры данных и алгоритмы (1021739), страница 22
Текст из файла (страница 22)
Используя такую нумерацию, можно реализовать оператор RIGHT_SIBLING, код для этого оператора приведен в листинге 3^4:. Для задания типов данных node (узел) и TREE (Дерево) используетсяследующее объявление:typenode = integer;TREE = array [1..maxnodes] of node;В этой реализации мы предполагаем, что нулевой узел Л представлен 0.Листинг 3.4. Оператор определения правого братаprocedure RIGHT_SIBLING ( л: node; Т: TREE ) : node;vari, parent: node;beginparent:=T[n];for i : = n + 1 to maxnodes doif T f i ] = parent thenreturn (i) ,return(0) { правый брат не найден }end; { RIGHT_SIBLING }Представление деревьев с использованием списков сыновейВажный и полезный способ представления деревьев состоит в формировании длякаждого узла списка его сыновей.
Эти списки можно представить любым методом,описанным в главе 2, но, так как число сыновей у разных узлов может быть разное,чаще всего для этих целей применяются связанные списки.На рис. 3.8 показано, как таким способом представить дерево, изображенное нарис. 3.7, а. Здесь есть массив ячеек заголовков, индексированный номерами (они жеимена) узлов. Каждый заголовок (header) указывает на связанный список, состоящийиз "элементов"-узлов. Элементы списка header[i] являются сыновьями узла i, например узлы 9 и 10 — сыновья узла 3.Прежде чем разрабатывать необходимую структуру данных, нам надо в терминахабстрактного типа данных LIST (список узлов) сделать отдельную реализацию списков сыновей и посмотреть, как эти абстракции согласуются между собой.
Позднеемы увидим, какие упрощения можно сделать в этих реализациях. Начнем со следующих объявлений типов:86ГЛАВА 3. ДЕРЕВЬЯtypenode = integer;LIST = { соответствующее определение для списка узлов };position = {соответствующее определение позиций в списках};TREE = recordheader: array[1..maxnodes] of LIST;labels: array[1..maxnodes] of labeltype;root: nodeend;12345678910H3—LJ_10headerРис. З.8.
Представление дерева с помощью связанных списковМы предполагаем, что корень каждого дерева хранится отдельно в поле root(корень). Для обозначения нулевого узла используется 0.В листинге 3.5 представлен код функции LEFTMOST_CHILD. Читатель в качествеупражнения может написать коды других операторов.Листинг 3.5. Функция нахождения самого левого сынаfunction LEFTMOST_CHILD ( n: node; T: TREE ): node;{ возвращает самого левого сына узла л дерева Т }varL: LIST; { скоропись для списка сыновей узла л }beginL:= Т.header[n];if EMPTY(L) then { л является листом }return(0)elsereturn(RETRIEVE(FIRST(L), L ) )end; { LEFTMOST_CHILD }Теперь представим конкретную реализацию списков, где типы LIST и positionимеют тип целых чисел, последние используются как курсоры в массиве записейcellspace (область ячеек):varcellspace: array[1..maxnodes]node: integer;next: integerof recordend;3.3.
РЕАЛИЗАЦИЯ ДЕРЕВЬЕВ87Для упрощения реализации можно положить, что списки сыновей не имеют ячеек заголовков. Точнее, мы поместим T.header[n] непосредственно в первую ячейкусписка, как показано на рис. 3.8. В листинге 3.6 представлен переписанный (с учетом этого упрощения) код функции LEFTMOST_CHILD, а также показан код функции PARENT, использующий данное представление списков. Эта функция болеетрудна для реализации, так как определение списка, в котором находится заданныйузел, требует просмотра всех списков сыновей.'•v;.. ."<....•;•• .
/••:'•'_•.'..:У.'-_:•••.••^-';;>'•''..•Листинг 3.6. функции, использующие представление деревьев посредством связанных списковfunction LEFTMOST_CHILD ( n: node; Т: TREE ): node;{ возвращает самого левого сына узла n дерева Т }varL: integer; { курсор на начало списка сыновей узла n }beginL:= Г.header[л] ;if L = 0 then { л является листом }return(0)elsereturn(cellspace[L].node)end; { LEFTMOST_CHILD }function PARENT ( n: node; T: TREE ): node;{ возвращает родителя узла л дерева Т }varр: node; { пробегает возможных родителей узла n }i: position; { пробегает список сыновей р }beginfor p:= 1 to maxnodes do begini: = T.header[p],,while i <> 0 do { проверка на наличие сыновей узла р }if cellspace[i].node = л thenreturn(p)elsei:= eelIspaсе[i].nextend;return(0) { родитель не найден }end; { PARENT }'I- " ''•';..-- V V.->..:-Представление левых сыновей и правых братьевСреди прочих недостатков описанная выше структура данных не позволяет такжес помощью операторов CREATEi создавать большие деревья из малых.
Это являетсяследствием того, что все деревья совместно используют массив сеШрасе для представления связанных списков сыновей; по сути, каждое дерево имеет собственныймассив заголовков для своих узлов. А при реализации, например, оператораCREATE2(i>, TI, T2) надо скопировать деревья TI и Т2 в третье дерево и добавить новый узел с меткой v и двух его сыновей — корни деревьев TI и Т2.Если мы хотим построить большое дерево на основе нескольких малых, то желательно, чтобы все узлы всех деревьев располагались в одной общей области. Логическим продолжением представления дерева, показанного на рис.
3.8, будет заменамассива заголовков на отдельный массив nodespace (область узлов), содержащий записи с произвольным местоположением в этом массиве. Содержимое поля headerэтих записей соответствует "номеру" узла, т.е. номеру записи в массиве cellspace, в88ГЛАВА 3. ДЕРЕВЬЯсвою очередь поле node массива cellspace теперь является курсором для массиваnodespace, указывающим позицию узла.
Тип TREE в этой ситуации просто курсор вмассиве nodespace, указывающий позицию корня.Пример 3.7. На рис. 3.9, а показано дерево, а на рис. 3.9, б — структура данных,где узлы этого дерева, помеченные как А, В, С и. D, размещены в произвольных позициях массива nodespace. В массиве cellspace также в произвольном порядке размещены списки сыновей. П< .2D5S/\/-\всJOЛ — | ^11DАС••\ Л 3 ,5АIf'V215 ч•|•J38 -Поля label headerМЭССИЕ inodespaceа. Дерево Т^N1 5 \цПоля node nextМассивcellspaceб. Структуры данныхРис.
3.9. Структура данных для дерева, использующая связанные спискиСтруктура данных, показанная на рис. 3.9, б, уже подходит для того, чтобы организовать слияние деревьев с помощью операторов CREATEi. Но и эту структуруможно значительно упростить. Для этого заметим, что цепочка указателей поля nextмассива cellspace перечисляет всех правых братьев.Используя эти указатели, можно найти самого левого сына следующим образом.Предположим, что cellspace[i].node — п.
(Повторим, что "имя" узла, в отличие от егометки, является индексом в массиве nodespace и этот индекс записан в поле cellspace[i].node.) Тогда указатель nodespace[n].header указывает на ячейку самого левогосына узла п в массиве cellspace, поскольку поле node этой ячейки является именемэтого узла в массиве nodespace.Можно упростить структуру, если идентифицировать узел не с помощью индексав массиве nodespace, а с помощью индекса ячейки в массиве cellspace, который соответствует данному узлу как сыну. Тогда указатель next (переименуем это поле вrightjsibling — правый брат) массива cellspace будет точно указывать на правого брата, а информацию, содержащуюдя в массиве nodespace, можно перенести в новое поле leftmost_child (самый левый сын) массива cellspace.
Здесь тип TREE является целочисленным типом и используется как курсор в массиве cellspace, указывающий накорень дерева. Массив cellspace можно описать как следующую структуру:cellspace:label:end;array[I..maxnodes] of recordlabeltype;leftmost_child: integer;right_sibling: integer3.3. РЕАЛИЗАЦИЯ ДЕРЕВЬЕВ89Пример 3.8. Новое представление для дерева, показанного на рис. 3.9, а, схематически изображено на рис. 3.10. Узлы дерева расположены в тех же ячейках массива, что и на рис.
3.9, б. П•С5•-»• -т S.СА2С/Л|1VNn—s'--D^2ВПоля leftmostchild••11 -•labelrightsiblingcellspaceМассивРис. 3.10. Представление дерева посредством левых сыновей и правых братьевИспользуя описанное представление, все операторы, за исключением PARENT,можно реализовать путем прямых вычислений. Оператор PARENT требует просмотравсего массива cellspace. Если необходимо эффективное выполнение оператораPARENT,'то можно добавить четвертое поле в массив cellspace для непосредственногоуказания на родителей.В качестве примера операторов, использующих структуры данных рис.
3.10, напишем код функции CREATE2, показанный в листинге 3.7. Здесь мы предполагаем,что неиспользуемые ячейки массива cellspace связаны в один свободный список, который в листинге назван как avail, и'ячейки этого списка связаны посредством поляright_sibling. На рис. 3.11 показаны старые (сплошные линии) и новые (пунктирныелинии) указатели в процессе создания нового дерева.Листинг 3.7. функция CREATE2'•90•.
. "J•'-;:'•:'••<•' -":.:: /"'"•.' '.?'.: V ''.'.' '• '."':: ,!:''.•'. V' ' ' ' ' . , : . ' " ' ' .. ••'''" "'' ~< .function CREATE2 ( v. labeltype; 21, Г2: integer ): integer;{ возвращает новое дерево с корнем v и поддеревьями 71 и 12 }vartemp: integer; { хранит индекс первой свободной ячейкидля корня нового дерева }begintemp:= avail;avail:= cellspacefavail].right_sibling;cellspace[temp].leftmost_child:= 21;cellspace[temp].label:= v;cellspace[temp].right_sibling:= 0;cellspace[n] . right_sibling:= T2;cellspace[ T2] . right__sibling:= 0; {необязательный оператор}return(temp)end; { CREATE2 }"ГЛАВА З.
ДЕРЕВЬЯустановка в нульavail'шtempРис. 3.11. Изменение указателей при выполнении функцииCREATE2Можно уменьшить область памяти, занимаемую узлами дерева (но при этом увеличится время выполнения операторов), если в поле right_sibling самого правого сына вместо нулевого указателя поместить указатель на родителя. Но в этом случае,чтобы избежать двусмысленности, необходимо в каждую ячейку поместить еще двоичную (логическую) переменную, которая будет показывать, что содержится в полеright _sibling: указатель на правого брата или указатель на родителя.При такой реализации можно найти для заданного узла его родителя, следуя зауказателями поля right_sibling, пока не встретится указатель на родителя.
В этомслучае время, необходимое для поиска родителя, пропорционально количеству сыновей у родителя.3.4. Двоичные деревьяДеревья, которые мы определили в разделе 3.1, называются упорядоченными ориентированными деревьями, поскольку сыновья любого узла упорядочены слева направо, а пути по дереву ориентированы от начального узла пути к его потомкам.Двоичное (или бинарное) дерево — совершенно другой вид. Двоичное дерево можетбыть или пустым деревом, или деревом, у которого любой узел или не имеет сыновей, или имеет либо левого сына, либо правого сына, либо обоих. Тот факт, что каждый сын любого узла определен как левый или как правый сын, существенно отличает двоичное дерево от упорядоченного ориентированного дерева.Пример 3.9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
