Рассмотрим рекурсивные алгоритмы и рекурсивные структуры данных.

Рекурсия - процесс, протекание которого связано с обращением к самому себе (к этому же процессу).

Пример рекурсивной структуры данных - структура данных, элементы которой являются такими же структурами данных (рис. 4.1).

4.1 Деревья

Дерево - нелинейная связанная структура данных
(рис. 4.2).

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

 - дерево имеет 1 элемент, на которого нет ссылок от других элементов. Этот элемент называется корнем дерева;

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

 - каждый элемент дерева связан только с одним предыдущим элементом.

Любой узел дерева может быть промежуточным либо терминальным (листом).

На рис. 4.2 промежуточными являются элементы M1, M2, листьями - A, B, C, D, E. Характерной особенностью терминального узла является отсутствие ветвей.

Высота дерева - это количество уровней дерева. У дерева на рис. 4.2 высота равна двум.

Количество ветвей, растущих из узла дерева, называется степенью исхода узла (на рис. 4.2 для M1 степень исхода 2, для М2 - 3).

Для описания связей между узлами дерева применяют также следующую терминологию: М1 - “отец” для элементов А и В. А и В - “сыновья” узла М1.

Деревья могут классифицироваться по степени исхода:

1) если максимальная степень исхода равна m, то это - m-арное дерево;

2) если степень исхода равна либо 0, либо m, то это - полное m-арное дерево;      

3) если максимальная степень исхода равна 2, то это - бинарное дерево;

4) если степень исхода равна либо 0, либо 2, то это - полное бинарное дерево.

Представление деревьев

Наиболее удобно деревья представлять в памяти ЭВМ в виде связанных списков. Элемент списка должен содержать информационные поля, в которых содержится значение ключа и другая хранимая информация, а также - поля-указатели, число которых равно степени исхода (рис.4.3). Любой указатель элемента ориентирует данный элемент-узел с сыновьями этого узла.

Бинарные деревья

Бинарные деревья являются наиболее используемой разновидностью деревьев.

Согласно представлению деревьев в памяти ЭВМ каждый элемент будет записью, содержащей 4 поля. Значения этих полей будут соответственно ключ записи, текст записи, ссылка на элемент влево-вниз, на элемент вправо-вниз.

Для создания элемента бинарного дерева надо создавать в памяти элементы следующего формата (рис. 4.5):

Функция V = MakeTree(Key, Rec) - создает элемент (узел дерева) с двумя указателями и двумя полями (ключевым и информационным).

Алгоритм функции следующий:

p = getnode

r ( p ) = rec

k (p) = key

v = p

left (v)= nil

right ( v ) = nil

return

При построении необходимо помнить, что левый сын имеет ключ меньший, чем у отца, а значение ключа правого сына больше значения ключа отца. Например, построим бинарное дерево из следующих элементов: 50, 46, 61, 48, 29, 55, 79. Оно имеет следующий вид:

Получили упорядоченное бинарное дерево с одинаковым числом уровней в левом и правом поддеревьях. Это - идеально сбалансированное дерево, то есть дерево, в котором левое и правое поддеревья имеют уровни, отличающиеся не более чем на единицу.