Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow Алгоритмы и структуры данных

РЕАЛИЗАЦИЯ ОСНОВНЫХ ОПЕРАЦИИ НАД БИНАРНЫМ ДЕРЕВОМ

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

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

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

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

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

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

var

Item: pltem;

NLeft, NRight: Word; v: tValue;

begin if n <> 0 then begin NLeft:= n div 2;

NRight:= n - NLeft-1; ltem:= New(pltem);

Read(f, v);

if SeekEoln(f) then ReadLn(f);

ltemA.Value:= v; ltemA.Left:= BuildTree(NLeft); ltemA.Right:= BuildTree(NRight); BuildTree:= Item;

end

else BuildTree:= nil; end; //function BuildTree

begin

fRoot:= BuildTree(n); fSize:=n;

end; //procedure tBinaryTree.Build

Обход дерева сверху вниз выполняется с помощью процедуры:

procedure tBinaryTree.UpDownRevision(var f: Text);

// Обход бинарного дерева сверху вниз и вывод результатов в файл f procedure UpDown(ltem: pltem); //рекурсивная процедура обхода

begin

if Item <> nil then begin

//1. Обработка узла - вывод в файл f // 2. Обход левого поддерева // 3. Обход правого поддерева

Write(f,ltemA. Value);

UpDown(ltemA.Left);

UpDown(ltemA. Right);

end;

end; //procedure UpDown

begin

UpDown(fRoot);

Writeln(f);

end; //procedure tBinaryTree.UpDownRevision

В процедурах обхода слева направо (Left Right Revision) и снизу вверх (DownUpRevision) изменится только последовательность выполнения основных операций (1,2 и 3) в соответствии со способом обхода.

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

procedure tBinaryTree.AddLeft(Addr: pltem; SubTree: tBinaryTree); //Включение поддерева SubTree в левую ветвь узла с адресом Addr

begin

if AddrMeft = nil

then begin

AddrA.Left:= SubTree.Root;

// Увеличение числа узлов дерева на число узлов поддерева lnc(fSize, SubTree. Size);

SubTree.Root := nil; SubTree.Size := 0; //поддерево пусто

end;

end; //procedure tBinaryTree.AddLeft

Метод исключения поддерева из левой ветви узла с адресом Addr возвращает новое (исключенное) поддерево:

function tBinaryTree.DeleteLeft(Addr:pltem):tBinaryTree;

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

begin

Result := tBinaryTree.Create;

Result.Root := AddrMeft;

Result.Size := NodesQuantity(AddrM_eft);

Dec(fSize,Result.Size);

AddrM_eft:= nil;

end; //function tBinaryTree.DeleteLeft

Включение и исключение для правой ветви узла выполняются аналогично. Узел с адресом Addr должен присутствовать в дереве.

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

procedure tBinaryTree.WriteTo(var f: Text);

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

procedure WriteTree(ltem: pltem; Step: Byte);

// Рекурсивная процедура вывода элемента Item со Step пробелами

begin

if Item О nil

then begin

WriteTree(ltemA.Right, Step+2);

WriteLn(f,' ':Step, ltemA.Value);

WriteTree(ltemA.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, а затем вызов наследуемого метода Destroy.

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

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы