2015-04-08
1005
Дерево представляет собой иерархическую структуру какой-либо совокупности элементов (узлов) и отношений, образующих иерархическую структуру узлов. Один из узлов определен как корень. Узлы дерева могут быть элементами любого типа и обычно изображаются буквами, строками или числами.
Формально дерево можно определить следующим образом.
Один узел является деревом, он же является корнем этого дерева.
Пусть 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;
