If Item <> nil

Then begin

WriteTree(Item^.Right, Step+2);

WriteLn(f, ' ': Step, Item^.Value);

WriteTree(Item^.Left, Step+2);

end;

end; // procedure WriteTree

Begin

WriteTree(fRoot, 5);

end; // procedure tBinaryTree.WriteTo

Остальные операции над бинарным деревом могут быть реализованы на основе уже рассмотренных методов исследования дерева.

Функция Father(Addr), возвращающая указатель на отца узла с адресом Addr, может быть реализована с использованием рекурсивной процедуры обхода дерева сверху вниз, причем обработка узла при этом заключается в сравнении указателей сыновей этого узла с заданным адресом Addr. Если ни один из узлов дерева не имеет сыновей с адресом Addr, то узел с адресом Addr – корень дерева, и функция Father(Addr) должна возвращать значение nil. Напомним, что при выполнении этой и подобных операций предполагается, что узел с указателем Addr присутствует в дереве. При реализации операций эту ситуацию можно анализировать дополнительно.

Функция Brother(Addr), возвращающая указатель на брата узла Addr, может сначала вызывать метод Father(Addr) для определения адреса отца этого узла, а затем сравнивать адреса сыновей найденного предка с адресом Addr и выдавать не совпадающий с Addr адрес сына в качестве результата операции.

Функции IsLeft(Addr) и IsRight(Addr), возвращающие значение «истина», если узел с адресом Addr является соответственно левым или правым сыном некоторого узла дерева, также реализуются путем вызова метода Father(Addr) и последующего анализа адресов его сыновей.

В конструкторе Create указателю на корень дерева fRoot присваивается значение nil и полю fSize – значение 0.

Процедура удаления всех узлов дерева Clear может быть реализована с использованием рекурсивной процедуры обхода дерева снизу вверх, обработка текущего узла с указателем Item при этом заключается в удалении его из памяти ЭВМ процедурой Dispose(Item). После вызова рекурсивной процедуры обхода указатель корня дерева должен получить значение nil, а поле fSize – значение 0

Деструктор Destroy класса tBinaryTree содержит вызов метода Clear.

Функция NodesQuantity(Addr) вычисления количества узлов поддерева с корнем Addr может быть реализована на основе любой процедуры обхода поддерева, начиная от узла с адресом Addr, обработка узла будет заключаться в увеличении на единицу числа вершин поддерева.

6. Дерево выражения

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

Дерево выражения можно строить по инфиксной записи, но при этом алгоритм построения должен учитывать приоритеты выполнения операций и наличие скобок. Более простым путем является предварительное преобразование арифметического выражения из инфиксной записи в префиксную с использованием стека.

При построении дерева префиксная запись сканируется слева направо и дерево строится также слева направо.

Рекурсивный алгоритм построения дерева выражения может быть описан следующим образом:

1) получить очередной символ префиксной записи выражения и поместить его в узел дерева;

2) если этот символ – операция,

то построить таким же способом его левое поддерево,

построить таким же способом его правое поддерево,

иначе конец алгоритма.

Дерево выражения может строиться и по постфиксной записи, в этом случае запись выражения сканируется справа налево и дерево строится также справа налево.

Дерево выражения может быть реализовано как наследник бинарного дерева с символьным или строковым значением содержательного поля Value элемента дерева. Метод Build дерева выражения перекрывает одноименный метод бинарного дерева, так как реализуется иначе; все остальные методы бинарного дерева наследуются.

Type

tOperatorSet = set of '*'.. '/'; // тип - множество операторов

tExprTree = class (tBinaryTree) // класс - дерево выражения