Деревья

Дерево есть конечное множество T узлов, такое, что:

1. имеется один специально обозначенный узел, называемый корнем дерева.

2. остальные узлы содержатся в m³0 попарно непересекающихся множествах T₁,T₂,…T_m, каждое из которых является деревом.

Деревья T₁,T₂,…T_mназываются поддеревьями данного корня. Строго говоря, приведенное определение относится к специальному случаю дерева, называемому корневым деревом. Деревья, в которых корень не выделен, называют висячими. Здесь рассматриваются исключительно корневые деревья.

Число поддеревьев узла называют его степенью. Узел нулевой степени называют листом. Уровень узла в дереве определяется следующим образом:

- корень имеет уровень 1

- корни поддеревьев узла имею уровень на 1 больший, чем уровень узла.

Высотой дерева называют наибольший уровень узла в нём.

Если в п.2 определения дерева имеет значение относительный порядок следования поддеревьев T₁,T₂,…T_m,то дерево называют упоря­доченным. Лес – это множество, быть может, пустое, состоящее из некоторого числа непересекающихся деревьев. Определение дерева рекурсивно и также рекурсивными являются большинство методов обработки деревьев.

Дерево можно изобразить различными способами. Изображения деревьев на рис. 20 эквивалентны.

Рис.20 Различные изображения деревьев

Примерами древовидной структуры являются генеалогические деревья, оглавления, формулы, классификации. На рис. 21 изображены деревья, изображающие формулу a-b*(c/d+e/f)и классификации товаров.

Рис. 21 Примеры деревьев

Когда говорят о деревьях, часто используют такие термины, как "отец", "сын", "брат", "предок", "потомок". Каждый узел является отцом корней своих поддеревьев. Последние являются братьями между собой и сыновьями своего отца. В упорядоченном дереве левый брат считается старшим. По аналогии можно ввести термины "дядя", "племянник" и другие. Термины "предок" и "потомок" употребляются для обозначения родства, простирающегося на несколько уровней дерева.