Деревья
Дерево - нелинейная связанная структура данных
(рис. 4.2).
Дерево характеризуется следующими признаками:
- дерево имеет 1 элемент, на которого нет ссылок от других элементов. Этот элемент называется корнем дерева;
- в дереве можно обратиться к любому элементу путем прохождения конечного числа ссылок (указателей);
- каждый элемент дерева связан только с одним предыдущим элементом, Любой узел дерева может быть промежуточным либо терминальным (листом). На рис. 4.2 промежуточными являются элементы M1, M2, листьями - A, B, C, D, E. Характерной особенностью терминального узла является отсутствие ветвей.
Высота - это количество уровней дерева. У дерева на рис. 4.2 высота равна двум.
Количество ветвей, растущих из узла дерева, называется степенью исхода узла (на рис. 4.2 для M1 степень исхода 2, для М2 - 3). По степени исхода классифицируются деревья:
1) если максимальная степень исхода равна m, то это - m-арное дерево;
2) если степень исхода равна либо 0, либо m, то это - полное m-арное дерево;
3) если максимальная степень исхода равна 2, то это - бинарное дерево;
4) если степень исхода равна либо 0, либо 2, то это - полное бинарное дерево.
Для описание связей между узлами дерева применяют также следующую терминологию: М1 - “отец” для элементов А и В. А и В - “сыновья” узла М1.
