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 { включение нового слова }
new(T);
with T^ do
begin
inf.slovo:=slovo; inf.count_sl:=1;
L:=nil; R:=nil
end
end
else
if slovo < T^.inf.slovo then
Slovar(T^.L, slovo)
else
if slovo > T^.inf.slovo then
Slovar(T^.R, slovo)
else T^.inf.count_sl:=T^.inf.count_sl+1
end; { Slovar }
Упражнение 4.4. Описать нерекурсивную логическую функцию, проверяющую, входит ли заданный элемент в дерево поиска.
Упражнение 4.5. Описать нерекурсивную процедуру или функцию подсчета числа вхождений заданного элемента в дерево поиска.
4.3 Исключение из дерева поиска
Алгоритм исключения из упорядоченного дерева должен описывать три случая:
1) Узла с заданным значением в дереве нет.
2) Узел с заданным значением имеет не более одного потомка, т.е. удаляемый узел или терминальная вершина ( лист ), или вершина с одним потомком.
3) Узел с заданным значением имеет двух потомков.
Трудности возникают в случае 3), так как удаляемый узел нужно заменить либо на самый правый узел его левого поддерева, либо на самый левый узел его правого поддерева, причем они должны иметь не более одного потомка.
Пример 4.4. Описать процедуру исключения узла с заданным значением x из дерева поиска T .
procedure Delete(var T : Tree; x : integer);