2014-02-02
673
9.2.1 Естественное представление дерева
Дерево может быть представлено в машинной памяти в форме многосвязного списка, в котором каждый логический указатель соответствует ребру древовидного графа. При таком представлении каждому узлу дерева ставится в соответствие элемент многосвязного списка, причем в каждом элементе резервируются следующие поля:
- поля, содержащие полезные данные;
- поле степени исхода;
- поля логических указателей; их общее число в одном узле равно степени дерева, но в каждый момент времени количество непустых логических указателей равно степени исхода соответствующей вершины дерева.
На рисунке 9.3 показана логическая структура спискового представления дерева, изображенного на рисунке 9.1. Такое представление называют естественным представлением дерева. Все элементы дерева при этом имеют один и тот же тип. Тип элемента дерева, назовем этот тип Tvertex, называется базовым типом для дерева.
Рисунок 9.3 - Естественное представление дерева
Теперь можно сформулировать рекурсивное определение дерева: дерево типа Tvertex - это
|
|
|
а) либо пустое дерево,
б) либо некоторая вершина типа Tvertex, называемая корнем, с конечным числом связанных с ней поддеревьев, имеющих базовый тип Tvertex.
При естественном списковом представлении дерева обязательно должен быть организован указатель (курсор) на корневую вершину, обеспечивающий доступ к дереву. На рисунке 9.3 курсором корня является указатель Root. Иногда в элементе списка, соответствующем вершине дерева, размещают указатель, направленный к родительскому узлу, - это упрощает реализацию некоторых алгоритмов обработки деревьев.
Базовый тип (Tvertex) и курсор корня (Root) для дерева степени 3 можно описать нотациями языка Pascal, представленными ниже. Очевидно, при таком объявлении типа Tvertex количество полей для размещения структурных указателей фиксируется описанием типа Pchild. Если имеются основания предполагать, что при выполнении операций в дереве степень дерева потребуется увеличить, то это нужно предусмотреть в описании типа Pchild.
