Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Then begin. NLeft:= n div 2; NRight:= n - NLeft-1;






NLeft: = n div 2; NRight: = n - NLeft-1;

Item: = New(pItem);

Read(f, v);

if Eoln(f) then ReadLn(f);

Item^.Value: = v;

Item^.Left: = BuildTree(NLeft);

Item^.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(Item: pItem); // рекурсивная процедура обхода

Begin

If Item < > nil

Then begin

Write(f, Item^.Value); // 1. Обработка узла - вывод в файл f

UpDown(Item^.Left); // 2. Обход левого поддерева

UpDown(Item^.Right); // 3. Обход правого поддерева

end;

end; // procedure UpDown

Begin

UpDown(fRoot);

Writeln(f);

end; // procedure tBinaryTree.UpDownRevision

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

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

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

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

Begin

If Addr^.Left < > nil

then WriteLn('Левая ветвь узла не пуста. Включение невозможно')

Else begin

Addr^.Left: = SubTree.Root;

// увеличение числа узлов базового дерева на число узлов поддерева

Inc(fSize, SubTree.Size);

// поддерево становится пустым

SubTree.Root: = nil; SubTree.Size: = 0;

end;

end; // procedure tBinaryTree.AddLeft

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

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

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

Begin

Result: = tBinaryTree.Create;

Result.Root: = Addr^.Left;

Result.Size: = NodesQuantity(Addr^.Left);

Dec(fSize, Result.Size);

Addr^.Left: = nil;

end; // function tBinaryTree.DeleteLeft

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

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

procedure tBinaryTree.WriteTo(var f: Text);

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

procedure WriteTree(Item: pItem; Step: Byte);

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

Begin






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.