5.1 Бинарные деревья

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

Формально дерево можно определить следующим образом.

Один узел является деревом, он же является корнем этого дерева.

Пусть n– это узел, а – деревья с корнямисоответственно. Можно построить новое дерево, сделавnродителем узлов. В этом деревеnбудет корнем, а– поддеревьями этого корня. Узлыназываются сыновьями узлаn.

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

Type pt=^node;

node=record

data:integer; {Информационное поле}

left,right:pt; {Указатели на левого и правого потомков}

end;

var root :pt; {Указатель на корень дерева}

К основным операциям, выполняемым с деревом, относятся вставка элемента, удаление элемента, обход дерева.

Создание бинарного древа можно реализовать на основе операции вставки элемента. Ниже приведена соответствующая процедура.

Procedure Insert(var x : pt; y:integer);{х – указатель на корень дерева, у -

Begin вставляемая вершина}

if x=nil then

Begin

new(x);

x^.data:=y;

x^.left:=nil;

x^.right:=nil;

End

else if y<= x^.data then insert (x^.left,y)

else insert (x^.right,y);

End;

Реализация удаления элемента из дерева выполнятся чуть сложнее. Если узел имеет одного потомка, то в поле ссылки родителя удаляемого элемента записывается ссылка, не равная nil. В том случае, когда у удаляемого элемента два потомка, для сохранения структуры дерева поиска на место этого элемента необходимо записать или самый правый элемент левого поддерева, или самый левый элемент правого поддерева. Ниже на рисунке приведена схема удаления элемента для первого варианта.

{Удаление элемента из дерева}

procedure Del_tree (var x : pt; y:integer);

var q:pt;

{Поиск самого правого элемента в дереве}

procedure Del (var w : pt);

begin

if w^.right<>nil then Del(w^.right)

else begin

q:=w; {Запоминается адрес для освобождения места в «куче» }

x^.data:=w^.data;

w:=w^.left;

end;

end;

begin

if x<>nil then

if y<x^.data then Del_tree (x^.left, y)

else if y>x^.data then Del_tree (x^.right, y)

else Begin

q:=x;

{Правого поддерева нет}

if x^.right=nil then x:=x^.left

{Левого поддерева нет}

else if x^.left=nil then x:=x^.right

else del(x^.left); {Поиск самого правого элемента в левом

dispose(q); поддереве}

end;

end;