Представление деревьев. Основные операции над деревом

Дерево – это сложная динамическая структура данных, применяющаяся для эффективного хранения информации.

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

Type
TreeLink = ^Tree;
Tree = Record
Data: <тип данных>;
Left, Right: TreeLink;
End;

Корень дерева опишем в разделе описания переменных:

Var
kd: TreeLink;

К основным операциям над деревьями относятся:

• занесение элемента в дерево;
• обход дерева;
• удаление элемента из дерева.

Рассмотрим вставку и обход дерева на примере следующей задачи.

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

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

Procedure InsTree(n: integer; Var t: TreeLink);
Begin
if t=nil
then
begin
new(t);
with t^ do
begin
Left:= nil;
Right:= nil;
Data:= n;
end;
end;
else
if n<=t^.data
then
InsTree(n, t^.Left)
else
InsTree(n, t^.Right)
End;

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

• вывод числа, хранящегося в узле;
• обход левого поддерева;
• обход правого поддерева.

Порядок выполнения этих действий определяет способ обхода дерева. Способы вывода:

• прямой вывод (сверху вниз);
• обратный вывод (слева направо);
• концевой вывод (снизу вверх).

Процедура обратного вывода дерева имеет следующий вид:

Procedure PrintTree(t: TreeLink);
Begin
if t<>Nil
then
begin
PrintTree(t^.Left);
Write(t^.Data:3);
PrintTree(t^.Right);
end;
End;

Задание. Написать процедуры прямого и концевого вывода значений элементов дерева.

Основная программа осуществляет ввод чисел с клавиатуры. Используются: переменная nd типа TreeLink – значение указателя на корень дерева; переменная Digit типа integer для хранения очередного введенного числа.

Begin
writeln('Вводите вершины дерева. Окончание ввода – 0');
kd:= nil;
read(Digit);
while Digit <> 0 do
begin
InsTree(Digit, kd);
writeln(' Введите очередное число ');
read(Digit);
end;
PrintTree(kd);
End.