Лекция: Решение задач работы с бинарным деревом.

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