Protected. fRoot: pItem; // поле - указатель на корень

fRoot: pItem; // поле - указатель на корень

fSize: Word; // поле - число элементов дерева

Public

// Свойство - указатель на корень дерева (доступ по чтению и записи)

property Root: pItem read fRoot write fRoot;

// Свойство - число элементов дерева (доступ по чтению и записи)

property Size: Word read fSize write fSize;

// Построение дерева из n узлов

procedure Build(n: Word; var f: Text);

// Обход дерева сверху вниз

procedure UpDownRevision(var f: Text);

// Обход дерева слева направо

procedure LeftRightRevision(var f: Text);

// Обход дерева снизу вверх

procedure DownUpRevision(var f: Text);

// Включение поддерева SubTree в левую ветвь узла Addr

procedure AddLeft(Addr: pItem; SubTree: tBinaryTree);

// Включение поддерева SubTree в правую ветвь узла Addr

procedure AddRight(Addr: pItem; SubTree: tBinaryTree);

// Исключение поддерева из левой ветви узла с адресом Addr

function DeleteLeft(Addr: pItem): tBinaryTree;

// Исключение поддерева из правой ветви узла с адресом Addr

function DeleteRight(Addr: pItem): tBinaryTree;

function Addr(v: tValue): pItem; // адрес узла со значением v

function Value(Addr: pItem): tValue; // значение узла Addr

function LeftSon(Addr: pItem): pItem; // левый сын узла Addr

function RightSon(Addr: pItem): pItem; // правый сын Addr

function Father(Addr: pItem): pItem; // отец Addr

function Brother(Addr: pItem): pItem; // брат Addr

function IsLeft(Addr: pItem): Boolean; // Addr - левый сын узла

function IsRight(Addr: pItem): Boolean; // Addr - правый сын узла

// Вывод дерева в файл f с помощью отсту пов

procedure WriteTo(var f: Text);

// Возвращение числа узлов поддерева с корнем Addr

function NodesQuantity(var Addr: PItem): Word;

function Empty: Boolean; // возвращение true, если дерево пусто

procedure Clear; // удаление всех узлов из дерева

constructor Create; // конструктор дерева

destructor Destroy; override; // деструктор дерева

end; // tBinaryTree

5. Реализация основных операций над бинарным деревом

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

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

Построение бинарного дерева минимальной высоты с числом узлов n предусматривает, что из входного потока (в данном случае – из текстового файла) считываются значения, размещаемые в узлах строящегося дерева.

procedure tBinaryTree.Build(n: Word; var f: Text);

// Построение дерева минимальной высоты из n узлов из файла f

function BuildTree(n: Word): pItem; // рекурсивная функция построения

Var

Item: pItem;

NLeft, NRight: Word;

v: tValue;

Begin

if n < > 0