Лабораторная работа «Деревья», задание №6.

Задание.

Создать сбалансированное дерево и выполнить проход с распечаткой в префиксном, инфиксном и постфиксном обходе.

Описание алгоритма решения.

Создаём дерево в классе, с полями Data – тут храниться значение элемента, а также ссылки на его левую и правую ветку типа TreeNode. Затем создаём конструктор и дерево из 12 элементов: var Three:= CreateTree(12) при помощи ввода с клавиатуры и балансировки new TreeNode<Integer>(x, CreateTree((n-1) div 2), CreateTree(n - 1 - (n-1) div 2)); Далее происходят обходы дерева с печатью корня. Сначала мы проходим левое поддерево InfixPrintTree(Root.Left), потом печатаем значение корня Write(Root.Data, ' '), далее идём в правое поддерево InfixPrintTree(Root.Right); В конце рекурсивно возвращаемся и просматриваем остальные элементы дерева. Ниже пример рекурсивного обхода дерева.

Листинг программы.

type

TreeNode<T> = class

Data: T;

Left, Right: TreeNode<T>;

constructor Create(Data: T; Left, Right: TreeNode<T>);

begin

Self.Data:= Data;

Self.Left:= Left;

Self.Right:= Right;

end;

end;

// Создание дерева

function CreateTree(n: Integer): TreeNode<Integer>;

begin

if n <= 0 then

Result:= nil

else

begin

Writeln('Введите элемент');

var x:= ReadInteger;

Result:= new TreeNode<Integer>(x, CreateTree((n-1) div 2), CreateTree(n - 1 - (n-1) div 2));

end;

end;

// Инфиксный обход

procedure InfixPrintTree(Root: TreeNode<Integer>);

begin

if Root = nil then

Exit;

InfixPrintTree(Root.Left);

Write(Root.Data, ' ');

InfixPrintTree(Root.Right);

end;

// Префиксный обход

procedure PrefixTraverseTree(Root: TreeNode<Integer>);

begin

if Root = nil then

Exit;

Write(Root.Data, ' ');

PrefixTraverseTree(Root.Left);

PrefixTraverseTree(Root.Right);

end;

// Постфиксный обход

procedure PostfixTraverseTree(Root: TreeNode<Integer>);

begin

if Root = nil then

Exit;

PostfixTraverseTree(Root.Left);

PostfixTraverseTree(Root.Right);

Write(Root.Data, ' ');

end;

begin

var Three:= CreateTree(12); // кол-во элементов

Writeln('Инфиксный обход');

PostfixTraverseTree(Three);

Writeln;

Writeln('Префиксный обход');

PrefixTraverseTree(Three);

Writeln;

Writeln('Постфиксный обход');

InfixPrintTree(Three);

end.

Дата добавления: 2015-08-17