Решение задач работы с бинарным деревом.

Элемент дерева используется для хранения какой-либо информации, следовательно, он должен содержать информационные поля, возможно разнотипные. Элемент двоичного дерева связан в общем случае с двумя прямыми потомками, а при необходимости может быть добавлена и третья связь - с непосредственным предком. Отсюда следует, что по структуре элемент дерева (узел) похож на элемент списка и может быть описан так же. Как и в списке, в дереве должна существовать возможность доступа к его «первому» элементу - корню дерева. Она реализуется через необходимую принадлежность дерева - поле ROOT, в котором записывается ссылка на корневой элемент.

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

Type

Nd = ^node;

Node = record

Inf1 : integer;

Inf2 : string ;

Left : nd;

Right : nd;

End;

Var

Root, p,q : nd;

Приведенный пример описания показывает, что описание элемента списка и узла дерева по сути ничем не отличаются друг от друга. Различия в технологии действий тоже невелики - основные действия выполняются над ссылками, адресами узлов. Основные различия - в алгоритмах.

При работе с двоичным деревом возможны следующие основные задачи:

1) создание элемента, узла дерева,

2) включение его в дерево по алгоритму двоичного поиска,

3) нахождение в дереве узла с заданным значением ключевого признака,

4) определение максимальной глубины дерева,

5) определение количества узлов дерева,

6) определение количества листьев дерева,

7) ряд других задач.

Приведем примеры процедур, реализующих основные задачи работы с бинарным деревом.

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

Procedure CREATE_EL_T(var q:ND; nf1:integer;

inf2:string);

Begin

new(q);

q^.inf1:=inf1;

q^.inf2:=inf2;

{значения полей передаются в качестве параметров}

q^.right:=nil;

q^.left:=nil;

end;

procedure Insert_el ( p : nd; {адрес включаемого элемента}

var root : nd);

Var

q, t : nd;

Begin

if root = nil { дерево пусто }

then root := p {элемент стал корнем}

else begin { поиск по дереву }

t := root;

q := root;

while ( t < > nil ) do

Begin

if p^.inf1 < t^.inf1