5. Представление деревьев в памяти ЭВМ
 

Элементы древовидной структуры могут быть размещены как в последовательной (векторной) памяти, так и в динамически получаемых областях памяти. Поскольку каждый узел дерева имеет логические связи со своими дочерними уз-ами, эти связи должны быть отражены и в физической структуре в явном или неявном виде. Пока ограничимся рассмотрением только бинарных деревьев. При явном отражении связей каждый узел дерева имеет структуру вида:
Данные — Левый указатель LPTR — Правый указатель RPTR.

Здесь поля LPTR и RPTR содержат указатели на левое и правое поддеревья данного узла. Форма указателей может быть различной.

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

Неявное задание связей возможно только при работе с бинарными деревьями специального вида, например типа «пирамида», используемого для сортировки данных. Применение такого дерева рассматривается в разделе сортировки пирамидой. Связи между элементами дерева-пирамиды явно не задаются, а вычисляются.

Схема представления дерева

Связанное размещение элементов дерева в динамических областях памяти более удобно, обеспечивает возможность легко вставлять в дерево вершины или удалять их из него; кроме того, дерево может разрастаться до произвольного размера. Рассмотрением именно такого представления мы и будем заниматься. Схема связанного представления двоичного дерева приводится на рис.. Для управления любым деревом необходимо наличие дескриптора или в простейшем случае указателя на корень дерева (указателя дерева).