Основы программирования. Динамические массивы. Списки. Ассоциативные массивы. Деревья. Хеш-таблицы - 35 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

37
function NewNode(x: DataType; left,right: PNode):
PNode;
begin
New(Result);
Result.data:=x;
Result.left:=left;
Result.right:=right;
end;
Приведем решения нескольких задач на бинарные деревья. Все они имеют
простые рекурсивные решения, что является следствием рекурсивной природы
определения дерева.
Задача 1. Создать идеально сбалансированное дерево с n узлами, заполнен-
ными случайными значениями.
Решение. Для решения создадим корень дерева, и рекурсивно создадим его
левое и
правое поддеревья, которые являются идеально сбалансированными и со-
держат n div 2 и n - n div 2 – 1 узлов соответстванно.
function CreateTree(n: integer): PNode;
begin
if n=0 then
Result:=nil
else Result:=NewNode(Random(100),
CreateTree(n div 2),
CreateTree(n - n div 2 - 1));
end;
Очевидно, полученное дерево идеально сбалансировано, поскольку количе-
ство узлов в поддеревьях отличается максимум на 1 и поддеревья идеально сба-
лансированы.
Задача 2. Разрушить бинарное дерево.
Решение
. Если дерево пусто, то оно уже разрушено, в противном случае сле-
дует разрушить левое поддерево, затем правое поддерево и, наконец, корень:
procedure Destroy(r: PNode);
begin
if r=nil then exit;
Destroy(r.left);
Destroy(r.right);
Dispose(r);
end;
Задача 3. Выдать узлы бинарного дерева в инфиксном порядке.
Решение. По определению инфиксного обхода, если дерево непустое, то на-
до вначале обойти
его левое поддерево в инфиксном порядке, затем корень и, на-

Страницы