Var root, q, V: tRebro;

Здесь объектами типа TUzelявляются записи, в которых каждое ссылочное полеLeftилиRightравно либоNil, либо ссылке на конкретную ячейку памяти компьютера, отведенную для объекта типаTUzel.

Дерево можно представить в виде множества объектов типаTUzel, связанных ссылками. Сами эти объекты соответствуют узлам дерева, а ссылки – его ребрам. Если при этом полеLeft (Right)некоторого узла равноNil, то это значит, что в дереве из этого узла не исходит ребро, направленное влево-вниз (вправо-вниз). Переход от вышестоящего к нижестоящему узлу совершается, как и в связных списках, присваиванием ссылочной переменной значения ее ссылочного поля, левого или правого. Этим способом можно просмотреть все узлы дерева сверху вниз. Включение нового узла в дерево осуществляется, как и включение нового элемента в связный список, изменением значений ссылочных полей соответствующих узлов. Вместе с каждым деревом рассматривается переменная, значением которой является ссылка на корень дерева (в нашем примере этоroot). Если в дереве нет ни одного узла, то значение этой переменной равноNil.

Корень дерева можно создать, например, так:

New(root);

Write(‘Первое число: ’);

ReadLn(root^.Data);

root^.Left := Nil;

root^.Right := Nil;

После этого можно вводить сортируемую последовательность: очередное введенное число сравнивается с числом, стоящим в корне, и образует левый или правый узел следующего уровня. Ссылкуvбудем использовать для ввода нового элемента, ссылкуq(поисковик) – для поиска места в дереве для нового элемента.

Пример: создать бинарное дерево для сортировки последовательности целых чисел. Ввести несколько чисел (см. выше) – конец ввода – число 0. Вывести введенную последовательность на экран.

Интерфейс:

Первое число: 14

Очередное число: 15

Очередное число: 4

Очередное число: 9

……..

Очередное число: 0

Отсортированная последовательность:

3 4 4 5 5 7 9 9 14 14 15 16 17 18 20

Программа:

Program Bi_Tree;

Uses WinCRT;

Type TRebro = ^TUzel;

TUzel = Record

Data : Integer;

Left, Right : Rebro;

End;

Var root, q, V : tRebro;

Procedure Order(base: TRebro); процедура просмотра дерева

Begin

If (base <> Nil) Then

Begin

Order(base^.Left);

Write(base^.Data:5);

Order(base^.Right);

End;

End;

Begin

ClrScr;

New(root);

Write('Первое число: ');

ReadLn(root^.Data); первое число - в корень дерева

root^.Left:=Nil;

root^.Right:=Nil;

Repeat

Write('Очередное число: ');

New(v);

ReadLn(v^.Data);

If (v^.Data = 0) если очередное число - ноль,

Then Break; то выходим из цикла ввода

v^.Left:=Nil;

v^.Right:=Nil;

q:=Root; поисковик - в корень дерева

While (q <> Nil) Do пока не добрались до листа:

Begin

If (v^.Data < q^.Data) если введенное число меньше числа в очередном узле

Then If (q^.Left <> Nil) и левая ссылка узла не пуста,

Then q:=q^.Left то делаем шаг влево,

Else иначе

Begin если левая ссылка узла пуста,

q^.Left:=v; то подвешиваем туда очередное число

Break; и выходим из цикла поиска

End;

If (v^.Data >= q^.Data) если введенное число больше или равно числу в очередном узле

Then If (q^.Right <> Nil) и правая ссылка узла не пуста,

Then q:=q^.Right то делаем шаг вправо,

Else иначе

Begin если правая ссылка узла пуста,

q^.Right:=v; то подвешиваем туда очередное число

Break; и выходим из цикла поиска

End;

End; {While}

Until (False);

WriteLn;

Writeln('Отсортированная последовательность: ');

Order(root);

WriteLn;

ReadLn;

End.