Файл: Бинарные деревья - дерево бинарного поиска.doc

Листинг функции поиска в бинарном дереве

Function Find(R:PTree;X:integer):boolean;

begin

if R=nil then Result:=false {Дошли до тупика, искать больше негде.}

else // Указатель на дерево не пуст

if R^.inf=X then // Проверяем содержимое на равенство

Result:=True // Узел найден

else

if n < R^.inf then

find:=find(R^.left,X) // Продолжаем поиск в левом поддереве

else

find:=find(R^.right,X); // Продолжаем поиск в правом поддереве

end;

Функцию Find можно записать иначе, изменив тип возвращаемого результата с логического типа на указатель узла бинарного дерева. В этом случае при успешном поиске получаем адрес найденного элемента, при неудаче – пустой указатель nil.

Удаление бинарного дерева.

После окончания работы с такой динамической структурой как бинарное дерево необходимо высвободить память, удалив все его узлы. Для удаления узлов бинарного дерева воспользуемся процедурой обхода cнизу вверх (PosOrder). Только такой порядок обхода гарантирует корректное удаление всех узлов (При удалении необходимо освобождать сначала самые крайние дочерние узлы, постепенно переходя на вышележащие родительские уровни. Последним должен быть удален корень дерева). Решает эту задачу процедура DeleteTree. В рекурсивную процедуру передается как параметр-переменная адрес корня дерева. После выхода из процедуры фактический параметр, будет продолжать хранить адрес бывшего корня дерева, но обращение по нему вызовет ошибку. Поэтому, после удаления дерева указателю на корень желательно присвоить значение nil, т.е. провести его повторную инициализацию.

Листинг процедуры удаления бинарного дерева.

procedure DeleteTree (var Root: ptelem);

begin

if r <> nil then

begin

DeleteTree (r^.left);

DeleteTree (r^.right);

dispose(r);

end;

end;

Удаление узла из упорядоченного дерева

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

Алгоритм удаления узла с ключом х из упорядоченного дерева реализован процедурой Delete(), приведенной далее.

Процедура обрабатывает три случая:

• В дереве нет узла с ключом х.

• Узел с ключом х имеет не более одного сына.

• Узел с ключом х имеет двух сыновей.

Параметры процедуры: x – значение удаляемого узла, Tree – указатель на корень дерева, moving – флаг удаления (moving=True – узел найден и удален, иначе - False)

Листинг процедуры удаления узла из упорядоченного дерева

Procedure Delete(x:integer; var Tree:PTree; var moving: boolean);

Var q :PTree;

Procedure Del(var R:PTree);

begin

If R^.Right <> nil then Del(R^.Right)

else begin

q^.inf:=R^.inf;

q:=R; R;=R^.left;

end;

end;

begin

If Tree = nil then moving:=false // узел для удаления не найден

else

If x< Tree^.inf then Delete(x,Tree^.left,moving)

else

If x> Tree^.inf then Delete(x,Tree^.right,moving)

else

begin // удаление узла

Moving:=true; q:=Tree;

If q^.right=nil then Tree:=q^.left

else

If q^.left= nil then Tree:=q^.right

else

Del(q^.left);

Dispose(q);

end

end;

Вспомогательная рекурсивная процедура Del() вызывается только в случае, когда удаляемый узел имеет двух сыновей. Она “спускается” вдоль самой правой ветви левого поддерева удаляемого узла q^, а затем заменяет ключ в q^ соответствующим значением самого правого узла r^ этого левого поддерева. После чего r^ удаляется. Параметр-переменная moving передает сведения о том, был ли удален требуемый узел. True – узел найден и удален, false - в противном случае.

Пример использования упорядоченного бинарного дерева для частотного анализа данных

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

Решение заключается в следующем. Создадим упорядоченное бинарное дерево, которое будет содержать числа. Если число встретилось первый раз, то добавляется новый узел с соответствующим значением. Если такое число уже есть в дереве, то увеличивается счетчик появления этого числа, хранящийся в этом узле. Поэтому внесем некоторые изменения в описание узла дерева Tree, добавив новое целочисленное поле cnt, которое будет являться счетчиком повторений. В основе алгоритма лежит процедура Insert(), осуществляющая поиск места вставки и добавляющая новый узел в упорядоченное бинарное дерево. Однако теперь в ней требуется дополнительная проверка на наличие в дереве значения. В остальном процедура Insert() аналогична процедуре описанной выше.

program testTree;

{$APPTYPE CONSOLE}

uses

SysUtils;

type

PTree = ^Tree;

Tree = record

inf, cnt: integer;// поле cnt – счетчик числа повторений

left, right: PTree;

end;

var

root: PTree; // указатель на корень дерева

n: integer;

procedure Insert (var r: PTree; x: integer); // Процедура поиска и добавления узла

var

p: PTree;

begin

if r = nil then

begin {Дерево пусто или нашли место добавления}

new(r);{Создаем и заполняем узел}

r^.inf := x;

r^.cnt := 1;{Счетчик повторений устанавливаем в единицу }

r^.left := nil;

r^.right := nil;

end

else if x < r^.inf then

Insert(r^.left, x) // Продолжение поиска в лев. поддереве

else if x > r^.inf then

Insert(r^.right, x) // Продолжение поиска в прав. поддереве

else

r^.cnt := r^.cnt + 1; { нашли узел со значением равным Х – увеличиваем счетчик cnt на единицу}

end; {Insert}

procedure PrintTree (r: PTree); {Обход и вывод дерева на экран(InOrder)}

begin

if r <> nil then

begin

PrintTree(r^.left);

writeln(' ', r^.inf : 4, ' ', r^.cnt : 4);

PrintTree(r^.right);

end; {if}

end; {PrintTree}

procedure DeleteTree (r: PTree); {Удаление дерева}

begin

if r <> nil then

begin

DeleteTree (r^.left);

DeleteTree (r^.right);

dispose(r);

end;

end; { DeleteTree }

begin {main program}

root := nil; {Инициализация структуры дерева }

writeln('Input integers; 777- exit');

repeat {Читаем числа с клавиатуры до ввода числа 777 и добавляем в дерево}

write('> ');

readln(n);

Insert(root, n);

until n = 777;

Writeln('Tree sorted contents :');

Writeln(' Value Count');

PrintTree(root); {Печатаем содержимое дерева на экране, сортировка - по возрастанию значения ключа inf}

DeleteTree (root); {Удаляем структуру дерева и освобождаем память}

readln;

end.

Задачи

1. Проверить, является ли данное двоичное дерево деревом поиска.

2. Дан текстовый файл. Определить частоту использования каждого слова в тексте. Результаты вывести в алфавитном порядке (слово - сколько раз встретилось). Найти наиболее и наименее встречающиеся слова.

3. Подсчитать число узлов в заданном двоичном дереве.

4. В бинарном дереве хранятся целые числа, определить их среднее значение.

5. Дан текстовый файл с целыми числами. Распечатать числа по убыванию. (Использовать бинарное дерево).

6. Даны два текстовых файла А и Б. Занести в файл С те слова, которых нет в файле В. Для хранения слов из файла В и ускорения поиска воспользуйтесь деревом двоичного поиска.

7. Даны два текстовых файла А и Б. Занести в файл С те слова, которых есть и в файле А и в файле В.

8. Описать логическую функцию, проверяющую на равенство два заданных двоичных дерева.

9. Описать логическую функцию, проверяющую, есть ли в заданном двоичном дереве хотя бы два одинаковых элемента.

10. Определить сколько раз встречается в упорядоченном бинарном дереве максимальное значение.