ВУЗ:
Составители:
76
дившееся место. Аналогично осуществляется перестройка дерева и массива при
удалении записи.
Последовательный способ хранения не позволяет использовать все пре-
имущества древовидных структур данных, поэтому обычно для их хранения
используется связанное представление данных. Для этого способа включение и
удаление записей не требует перезаписи массива, чем обеспечивается большая
гибкость структуры. Древовидная структура
при этом может расти неограни-
ченно.
Двоичное дерево отображается в памяти ЭВМ двусвязным списком.
Каждый элемент этого списка имеет формат, показанный на рис. 5.26.
Рис. 5.26. Формат элемента двусвязного списка:
DATA – информационное поле, в котором содержится информация о
данной вершине; LPTR и RPTR поля указателей соответственно левого и право-
го.
Любой из указателей может
принимать значение Q, означающее, что в
соответствующем направлении элементов больше нет. Если значение Q прини-
мают оба указателя, то данный узел является листом дерева.
Часто принимают, что левый указатель задает направление к записи с
меньшим значением ключа, а правый указатель – с большим. Пример двоичного
дерева и структуры его хранения показаны
на рис. 5.27.
Рис. 5.27. Двоичное дерево и структура его хранения в виде двусвязного списка
Для включения в дерево новой записи из стека свободной памяти бе-
рется свободная ячейка и в ней размещается новая запись. В дереве ищется узел
LPTR DATA RPTR
7
63
51
260
100
38
33
21
19
21
Q 7 Q 33
Q 38
100
26063
Q 51 Q 180
Q 19 Q
Q Q
QQ
180
Страницы
- « первая
- ‹ предыдущая
- …
- 74
- 75
- 76
- 77
- 78
- …
- следующая ›
- последняя »
