Program UP;

type Tree = ^Node;

Node = record

inf: integer;

L,R: Tree

End;

var x: integer; Root: Tree;

F: text; imf: string;

{ процедура добавления значения x в дерево поиска T }

procedure InTree(var T: Tree; x: integer);

var flag: boolean;

p,n: Tree; { указатели на текущий и новый элементы }

Begin

new(n); n^.inf:=x; { создание нового узла }

n^.L:=nil; n^.R:=nil;

if T=nil then

T:=n

Else

begin p:=T; flag:=true;

While flag do

Begin

if x < p^.inf then { меньший присоединяется слева }

if p^.L=nil then

Begin

p^.L:=n; flag:=false

End

else p:=p^.L { по левой ветви вниз}

Else

if p^.R=nil then

begin { больший или равный присоединяется справа }

p^.R:=n; flag:=false

End

else p:=p^.R { по правой ветви вниз }

End

End

end; { InTree }

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

procedure PrintInf(T: Tree);

Begin

if T <> nil then

Begin

PrintInf(T^.L);

writeln(T^.inf);

PrintInf(T^.R)

End

end; { PrintInf }

Begin

write('Задайте имя файла - ');

Readln(imf);

Assign(F,imf); reset(F);

Root:=nil;

While not eof(F) do

Begin

Read(F,x);

InTree(Root,x)

End;

Close(F);

writeln('Упорядоченная последовательность чисел:');

PrintInf(Root)

End.

Если в файле F содержится такая последовательность чисел:

5 2 8 0 9 6 3

то программа UP построит дерево поиска, показанное на рисунке 6 а).

Другой вариант включения значения x в дерево поиска реализован в процедуре In_Tree(T, x):

procedure In_Tree(var T: Tree; x: integer);

Var

p,q,n: Tree; {указатели на текущий, предыдущий и новый элементы}

Begin

new(n); n^.inf:=x; { создание нового узла }

n^.L:=nil; n^.R:=nil;

if T=nil then

T:=n

Else

begin p:=T;

while p<>nil do

begin q:=p;

if x < p^.inf then p:=p^.L

else p:=p^.R

End;

if x < q^.inf then q^.L:=n

else q^.R:=n

End

end; { In_Tree }

Рекурсивная процедура In_Tree_Rec(T,x) добавления значения x в
дерево поиска соответствует алгоритму:

Если новый элемент меньше значения в узле, то он должен добавляться в левое поддерево, иначе (больше или равен) в правое поддерево.

procedure In_Tree_Rec(var T: Tree; x: integer);

Begin

if T=nil then

Begin

new(T); T ^.inf:=x; { создание нового узла }

T^.L:=nil; T^.R:=nil

End

Else

if x < T^.inf

then In_Tree_Rec(T^.L, x)

else In_Tree_Rec(T^.R, x)

end; { In_Tree_Rec }

Упражнение 4.1. Как изменится процедура InTree, если узел с имеющемся в дереве значением будет добавляться в левое поддерево?

Упражнение 4.2. Как изменится процедура In_Tree, если узел с имеющемся в дереве значением будет добавляться в левое поддерево?

Упражнение 4.3. Описать нерекурсивную процедуру включения в дерево неповторяющихся элементов.

 

4.2. Поиск и включение для дерева сортировки

Для дерева сортировки поиск идет по единственному пути от корня к нужной вершине. Поэтому его можно описать с помощью итерации.

Пример 4.2. Бинарное дерево с элементами–литерами упорядочено по возрастанию. Определить, имеется ли в нем вершина, содержащая заданную литеру. Если она есть, то возвратить ссылающийся на нее указатель, в противном случае – пустую ссылку nil.

function Search_P(T: Tree; ch: char): Tree;

var flag: boolean;{ признак удачного поиска }

Begin

flag:=false;

while (T <> nil) and not flag do

if T^.inf = ch then flag:=true

Else

if ch < T^.inf then T:=T^.L

else T:=T^.R;

Search_P:=T

end; { Search_P }

Возможности динамического размещения данных более наглядно проявляются в примерах, где дерево растет или сокращается в ходе выполнения программы.

Рассмотрим сначала случай, когда дерево только растет, но не убывает. Типичный пример – построение алфавитного частотного словаря. Задача состоит в чтении текста, выборке из него слов и подсчете частоты их появления. Вначале дерево – пустое. Затем, если слово найдено, то счетчик его вхождений увеличивается на единицу, а если нет, то это - новое слово и оно включается в дерево с единичным значением счетчика.

Такой алгоритм часто называют [ 2 ] поиском по дереву с включением.

Пример 4.3. Описать процедуру включения слова в частотный словарь.

В этом случае тип Elem информационной части inf узлов дерева
(см. раздел 2) – запись из двух полей: слова (строки из 20 символов) и количества его появления в тексте:

type t_slovo = string[20];

Elem = record

slovo: t_slovo;

count_sl: integer

End;

Путь поиска для дерев слов очевиден. И если он приводит к пустому (nil) поддереву, то заданное слово нужно включить на место пустого поддерева.

procedure Slovar(var T: Tree; slovo: t_slovo);

Begin

if T = nil then

begin { включение нового слова }