Структуры и алгоритмы обработки данных

       

Деревья


 

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

(рис. 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.



Содержание раздела