PrintTree(Root,0)

Пример 3.6. Описать процедуру MaxEl, определяющую наибольший
элемент непустого дерева T.

Алгоритм MaxEl использует префиксный обход дерева: наибольший элемент находится или в узле, или в его левом поддереве, или в его правом
поддереве.

procedure MaxEl(T: Tree; var max: integer);

var m: integer;

Begin

if T <> nil then

Begin

max:=T^.inf;

if T^.L <> nil then

Begin

MaxEl(T^.L, m);

if m > max then max:=m

End;

if T^.R <> nil then

Begin

MaxEl(T^.R, m);

if m > max then max:=m

End

End

end; { MaxEl }

Пример 3.7. Описать рекурсивную процедуру Leaf подсчета количества k листьев дерева.

procedure Leaf(T: Tree; var k: integer);

Begin

if T <> nil then

if (T^.L=nil) and (T^.R=nil) then

k:=k+1

Else

Begin

Leaf(T^.L,k);

Leaf(T^.R,k)

End

end; { Leaf }

Количество List листьев дерева Root можно определить, обратившись к процедуре Leaf:

List:=0; Leaf(Root,List);

Если описать реализацию в виде функции, то не придется заботиться о присваивании нуля параметру–результату перед ее вызовом.

function fLeaf (T: Tree): integer;

Begin

if T=nil then fLeaf:=0

Else

if (T^.L=nil) and (T^.R=nil) then

fLeaf:=1

else fLeaf:= fLeaf(T^.L)+fLeaf(T^.R)

end {fLeaf};

Пример 3.8. Описать рекурсивную функцию Double, которая проверяет, есть ли в дереве T хотя бы два одинаковых элемента.

Один из вариантов проверки состоит в использовании функции Count подсчета числа вхождений заданного элемента El в дерево T. Функция Double поочередно проверяет число вхождений текущего значения T^.inf в дерево: если число вхождений больше 1, то результат проверки – истина, если нет, то такая ситуация может возникнуть в левом поддереве или в правом поддереве.

function COUNT(T: Tree; El:integer): integer;

var k: integer;

Begin

if T=nil then COUNT:=0

Else

Begin

if T^.inf = El then k:=1 else k:=0;

COUNT:=k+COUNT(T^.L,El)+COUNT(T^.R,El)

End

end; { COUNT }

function Double(T: Tree): boolean;

Begin

if T=nil then Double:=false

Else

Begin

if COUNT(T,T^.inf) > 1 then Double:=true

Else

Double:= Double(T^.L) or Double(T^.R)

End

end; { Double }

Пример 3.9. Описать функцию Equal проверки на равенство двух двоичных деревьев одинаковой структуры.

function Equal(T1,T2: Tree): boolean;

Begin

if T1=T2 then Equal:=true

Else

if (T1 <> nil) and (T2 <> nil) then

if T1^.inf = T2^.inf then

Equal:=Equal(T1^.L,T2^.L) and

Equal(T1^.R,T2^.R)

else Equal:=false

else Equal:=false

end; { Equal }

Пример 3.10. Описать процедуру Copy, которая создает копию T2
дерева T1.

procedure Copy(T1: Tree; var T2: Tree);

Begin

if T1 = nil then T2:=nil

Else

Begin

new(T2); T2^.inf:=T1^.inf;

Copy(T1^.L,T2^.L);

Copy(T1^.R,T2^.R);

End

end; { Copy }

Упражнение 3.2. Описать нерекурсивную процедуру или функцию, которая возвращает элемент из самого левого (правого) листа непустого дерева.

Упражнение 3.3. Описать нерекурсивную процедуру или функцию, которая

а) определяет количество узлов дерева;

б) вычисляет сумму (произведение, среднее арифметическое) всех элементов дерева.

в) определяет число вхождений заданного элемента в дерево;

г) выдает элементы из всех листьев дерева.

Упражнение 3.4. Описать рекурсивную процедуру или функцию, которая

а) определяет количество узлов (листьев, внутренних узлов) дерева;

б) вычисляет сумму (произведение, среднее арифметическое) всех элементов дерева.

в) определяет, входит ли заданный элемент в дерево;

г) выдает элементы из всех листьев (внутренних узлов) дерева;

д) определяет глубину непустого дерева;

е) определяет количество узлов на заданном уровне;

ж) удаляет листья дерева со значениями, равными заданному.

 

4. ДЕРЕВО ПОИСКА (СОРТИРОВКИ)

 

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

4.1 Построение дерева поиска

Алгоритм создания дерева поиска основан на следующих правилах:

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

Если в дереве есть узел с таким значением, то возможны варианты:

а) новый узел добавляется в правое поддерево,

б) новый узел добавляется в левое поддерево,

в) добавление не происходит.

Инфиксный обход такого дерева дает упорядоченную по возрастанию
(неубыванию в случае добавления одинаковых элементов) последовательность.

Пример 4.1. Упорядочить по неубыванию последовательность целых чисел, которая вводится из текстового файла.