Представления и реализации бинарных деревьев

Рассмотрим варианты представления и реализации структуры данных бинарного дерева. Пусть базовый тип узлов есть Elem.

Ссылочная реализация бинарного дерева в связанной памяти основана на представлении типа BT (Elem) рекурсивными типами BinT и Node:

type

BinT = ^Node; {представление бинарного дерева}

Node = record {узел: }

Info: Elem; {- содержимое}

LSub: BinT; {- левое поддерево}

RSub: BinT {- правое поддерево}

end {Node}

Здесь каждый узел дерева рассматривается как корень соответствующего поддерева, и этому поддереву сопоставляется запись из трех полей: поле Info хранит значение корня (типа Elem), а поля LSub и RSub - указатели на левое и правое поддеревья. Пустому дереву сопоставляется константа NilBT

На рис. а, б изображены бинарное дерево и его представление в ссылочной реализации.

ЛЕКЦИЯ 10. РЕАЛИЗАЦИЯ БИНАРНОГО ДЕРЕВА НА БАЗЕ ВЕКТОРА. ПРОШИТЫЕ БИНАРНЫЕ ДЕРЕВЬЯ

Цели и задачи лекции:

1.Ознакомление с векторной реализацией дерева.

2. Ознакомление с особенностями построения прошитых деревьев

Основные рассматриваемые вопрос: реализация бинарного дерева на базе вектора. Прошитые бинарные деревья.

Ссылочная реализация ограниченногобинарного дерева на базе вектора:

type Adr = 0 .. MaxAdr; {диапазон «адресов» в векторе Mem}

BinT = Adr; {представление бинарного дерева}

Node = record{узел: }

Info: Elem; {- содержимое}

LSub: BinT; {- левое поддерево}

RSub: BinT {- правое поддерево}

end {Node};

Mem = array [Adr]of Node {вектор для хранения дерева}

Здесь вектор типа Mem представляет собой память для хранения одного бинарного дерева (или нескольких бинарных деревьев, ограниченных в совокупности). Элемент вектора есть запись типа Node, содержащая узел и ссылки на поддеревья. На рис. приведен пример представления бинарного дерева. Дерево представляется переменной b: BinT, причем значение b = 3 есть номер элемента массива, в котором хранится корень дерева. Фактически переменная b играет роль ссылки на корень дерева (или адреса корня в векторной памяти). Пустому дереву соответствовало бы значение b = 0, т. е. в этом представлении константа NillBT = 0. Элементы вектора, не занятые под хранение узлов дерева, образуют свободную память, которую удобно организовать в виде линейного циклического списка (для этого используется одно из полей звена Node, например, поле LSub). При этом элемент вектора с индексом (адресом) 0 играет роль ссылки на начало списка свободной памяти.

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