У текущей вершины У текущей вершины
есть левый слуга есть правый слуга
да нет да нет
Сделать левого Занести запись в Сделать правого Занести запись в
слугу текущим качестве правого слуги слугу текущим качестве правого слуги
Более сложно устроены другие процедуры: переход к следующей и предыдущей записи, составление списка записей в возрастающем порядке, удаление вершины из индексного дерева и т.д. Мы не будем приводить их здесь. Фактически базы данных, как и индексы баз данных, размещаются в файлах. Запись файла индекса базы данных имеет те же четыре компоненты, что были указаны выше. Роль ссылки на запись базы данных играет порядковый номер записи в файле базы данных. Роль ссылки на вершину дерева индекса играет номер записи описания вершины индексного дерева в файле индекса базы данных.
4.14. Рекурсия.
В связи с рассмотрением деревьев уместно разобрать понятие рекурсии и его роль в прграммировании вообще и в Паскале в частности. Рекурсией называется использование при программировании процедуры в качестве оператора вызова этой же процедуры. Возможна опосредованная рекурсия, когда первая процедура вызывает вторую, а вторая процедура – первую. Основу для использования рекурсии составляют такие ситуации, когда подслучай общего случая подобен общему случаю и может быть проанализирован с помощью того же алгоритма, что и общий случай. Мы уже встречались с рекурсивным вызовом при решении задачи нахождении числа простых делителей натурального числа n. Аналогичная ситуация возникает в большинстве задач оперирования с деревьями индексов.
Особенность бинарных деревьев вообще и способа их описания с помощью указателей в частности заключается в том, что поддерево, образованное всеми потомками левого и правого сына корневой вершины, по своей структуре идентично самому дереву. Более того, для задания этого поддерева, как и для задания всего дерева, достаточно иметь указатель на корневую вершину поддерева. В этих условиях, например, задача перечисления всех вершин индексного инарного дерева в порядке возрастания решается следующей тривиальной рекурсивной процедурой (тип записи pterm определен в предыдущей главе):
procedure write_list (pt: pterm); {Процедура вывода дерева (в файл или на печать}
begin
if pt^.left Nil then write_list (pt^.left); {Вывести левое поддерево}
write_term (pt^.num); {Вывести запись, соответствующую корню}
if pt^.right Nil then write_list (pt^.right) {Вывести правое поддерево}
end;
Также с помощью рекурсивных процедур можно реализовать алгоритм поиска записи в файле с помощью индексного дерева, который был приведен в предыдущей главе:
function find_rec (pt: pterm; v: type_val {тип записи поля упорядочения}): longint;
{Возвращает по указателю на корень и индексному значению номер записи или -1, если запись не найдена}
begin
if pt^.val=v then find_rec:=pt^.num; {Запись соответствует корню дерева}
else if pt^.val>v then {Запись надо искать в левом поддереве}
if pt^.left = Nil {Левое поддерево отсутствует}
then find_rec := -1 {Запись не найдена}
else find_rec: = find_rec (pt^.left, v) {Запись ищется в левом поддереве}
elseif pt^.val
if pt^.right = Nil {Правое поддерево отсутствует}
then find_rec := -1 {Запись не найдена}
else find_rec := find_rec (pt^.right, v) {Запись ищется в правом поддереве}
end;
При записи рекурсивных процедур на Паскале возникает одна маленькая проблема. В вышеприведенной программе компилятор узнает обращение к процедуре find_rec внутри процедуры find_rec, поскольку заголовок функции расположен ранее, чем вызов функции. Но если есть две функции, вызывающие друг друга, то один из вызовов обязательно будет раньше, чем заголовок соответствующей функции. Для того, чтобы разрешить это противоречие, в Турбо-Паскале разрешается записывать только заголовок функции или процедуры без тела процедуры. Такое предварительное объявление обозначается ключевым словом forward так, как это делается в следующем примере:
|
8th Май 2011
|
Теги:
|