Понятие рекурсивных структур данных. Деревья, их признаки и представления

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

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

Деревья входят в состав рекурсивных структур данных.

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

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

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

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

- каждый элемент дерева связан только с одним предыдущим элементом. Любой узел дерева может быть промежуточным либо терминальным (листом). На рис. 4.2 промежуточными являются элементы М1, М2, листьями - А, В, С, В, Е. Характерной особенностью терминального узла является отсутствие ветвей.

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

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

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

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

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

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

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

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