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

Пример 3.8. Новое представление для дерева, показанного на рис. 3.9, а, схематически изображено на рис. 3.10. Узлы дерева расположены в тех же ячейках массива, что и на рис. 3.9, б. □


S

у 2

Поля teffmosf label right cfiild sibling

Массив cellspace

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

Используя описанное представление, все операторы, за исключением PARENT, можно реализовать путем прямых вычислений. Оператор PARENT требует просмотра всего массива cellspace. Если необходимо эффективное выполнение оператора PARENT, то можно добавить четвертое поле в массив cellspace для непосредственного указания на родителей.

В качестве примера операторов, использующих структуры данных рис. 3.10, напишем код функции CREATE2, показанный в листинге 3.7. Здесь мы предполагаем, что неиспользуемые ячейки массива cellspace связаны в один свободный список, который в листинге назван как avail, и ячейки этого списка связаны посредством поля right sibling. И& рис. 3.11 показаны старые (сплошные линии) и новые (пунктирные линии) указатели в процессе создания нового дерева.

Листинг 3.7. функция CREATE2

function CREATE2 { v. labeltyj>e; Tl, Т2: integer ): integer;

{ возвращает новое дерево с корнем v и поддеревьями 71 и Т2 } var

temp: integer; { хранит индекс первой свободной 51чейки для корня нового дерева }

begin

temp:= avail;

avail:= cellspacelavail].right 3ibling; cellspaceitemp] . leftmost child:= Tl; cellspaoeitemp] .label:= v; cellspaceitemp] . right slbling:= 0; се11зрасе[П] . rlght 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. Если мы примем соглащение, что на схемах двоичных деревьев левый сын всегда соединяется с родителем линией, направленной влево и вниз от родителя, а правый сын - линией, направленной вправо и вниз, тогда на рис. 3.12,а, б представлены два различных дерева, хотя они оба похожи на обьиное (упорядоченное ориентированное) дерево, показанное на рис. 3.13. Пусть вас не смущает тот факт, что деревья на рис. 3.12,а, б различны и не эквивалентны дереву на рис. 3.13. Дело в том, что двоичные деревья нельзя непосредственно сопоставить обычному дереву. Например, на рис. 3.12,а узел 2 является левым сыном узла 1 и узел 1 не имеет правого сына, тогда как на рис. 3.12,6 узел 1 не имеет левого сына, а имеет правого (узел 2). В тоже время в обоих двоичных деревьях узел 3 является левым сыном узла 2, а узел 4 - правым сыном того же узла 2. □

Обход двоичных деревьев в прямом и обратном порядке в точности соответствует таким же обходам обычных деревьев. При симметричном обходе двоичного дерева с



корнем п левым поддеревом Ti и правым поддеревом Т2 сначала проходится поддерево Tl, затем корень и и далее поддерево Гг- Например, симметричный обход дерева на рис. 3.12,а даст последовательность узлов 3, 5, 2, 4, 1.

Рис. 3.12. Два двоичных дерева

Рис. 3.13. "Обычное" дерево

Представление двоичных деревьев

ЕСЛИ именами узлов двоичного дерева являются их номера 1, 2, и, то подходящей структурой для представления этого дерева может служить массив cellspace записей с полями leftchild{AQm>m сын) и rightchild {пршъш сын), объявленный следующим образом:

cellspace: array [1. .maxnodes] of record leftchild: integer; right child: integer

end;

В этом представлении cellspaceXiYleftchlldAiiRTCK левым сыном узла i, а cellspace[i].rightchila- правым сыном. Значение О в обоих полях указывает на то, что узел I не имеет сыновей.

1Тример 3.10. Двоичное дерево на рис. 3.12,а можно представить в виде табл. 3.1. П

Таблица 3.1. Представление двоичного дерева

Значение поля leftchild

Значение поля rightchild

Пример: коды Хаффмана

Приведем пример применения двоичных деревьев в качестве структур данных. Для этого рассмотрим задачу конструирования кодов Хаффмана. Предположим, мы имеем сообщения, состоящие из последовательности символов. В каждом сообщении символы независимы и появляются с известной вероятностью, не зависящей от позиции в сообщении. Например, мы имеем сообщения, состоящие из пяти символов а, Ь, с, d, е, которые появляются в сообщениях с вероятностями 0.12, 0.4, 0.15, 0.08 и 0.25 соответственно.





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.0036