C d e f

 

Рис. 8. Пример представления алгебраического выражения в виде дерева

Использование бинарных деревьев удобно в силу их регулярности – каждый узел имеет степень не более двух. Переход от произвольного леса к бинарному дереву выполняют на основе следующего правила (рис. 9):

· соединяют между собой корневые вершины;

· соединяют между собой сыновей каждой семьи;

· убирают все связи, идущие от родительской вершины к сыновьям, кроме связи, между родительской вершиной и первым сыном.

A D A D

B C E F G B C E F G

K H J K H J

Рис. 9. Иллюстрация перехода к двоичному дереву

Одним из естественных способов представления бинарных деревьев в ЭВМ является представление в виде записей, содержащих три поля (рис. 10):

· Key -- ключевое или информационное поле, отождествляемое с узлом;

· Llink -- указатель на левое поддерево;

· Rlink -- указатель на правое поддерево;

Помимо метода Llink-Rlink(левый сын-правый брат), Существует еще много способов программной реализации древовидных структур. Обычно надлежащий выбор представления в большей степени определяется видом операций над деревьями, которые предстоит выполнить.

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

Рис. 10. Иллюстрация представления дерева в виде двухсвязного списка

 

Два наиболее простых способа представления деревьев (и лесов) заключаются по существу в том, что опускаются Rlink либо Llink; последовательное расположение узлов замещает связь одного из этих типов. Например, случай, когда опущены связи Llink. Возьмем лес (A(B,C(K)),D(E(H),F(J),G)), диаграммы деревьев которого имеют вид, представленный на рис. 11.

В случае представления дерева в прямом порядке при последовательном распределении памяти узлы располагаются в прямом порядке с полями INFO, Rlink и Ltag в каждом узле.

Рис.11. Линейное представление деревьев

Здесь ненулевые связи Rlink отмечены стрелками, а Ltag =”_” (для концевых узлов) отмечены знаком “_|”. Связь Llink не нужна, поскольку она либо равна нулю, либо указывает на следующий элемент последовательности.

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

В процессе работы с деревьями необходимо уметь выполнять следующие основные операции:

· введение новой вершины.

· удаление указанной вершины.

· навигация по дереву.

· обход или прохождение дерева. Это способ методичного исследования узлов дерева, при котором каждый узел проходится точно один раз. Полное прохождение дерева даёт нам линейную расстановку узлов. Для прохождения бинарного дерева чаще всего используют один из двух способов: проходить узлы в прямом или обратном порядке. Прямой порядок определяют следующим правилом:

1. Попасть в корень.

2. Пройти левое поддерево.

3. Пройти правое поддерево.

Обратному порядку соответствует правило:

1. Пройти левое поддерево.

2. Попасть в корень.

3. Пройти правое поддерево.

Все эти методы имеют свои преимущества и недостатки в плане реализации средствами реляционных СУБД. Используя метод (Llink-Rlink) можно представлять не только произвольные деревья, но и сети без циклов, однако алгоритмы его обработки более сложны.