Представления и реализации бинарных деревьев
Рассмотрим варианты представления и реализации структуры данных бинарного дерева. Пусть базовый тип узлов есть 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 играет роль ссылки на начало списка свободной памяти.
Рис. Пример ссылочного представления бинарного дерева на базе вектора.
Дата добавления: 2018-05-10; просмотров: 1347;