Определение (неформальное)
Определим дерево как конечное множество T, состоящее из одного или более элементов (называемых вершинами или узлами), таких, что
· имеется одна специально выделенная вершина, называемая корнем дерева;
· остальные вершины (исключая корень) содержатся в m попарно непересекающихся множествах T1,T2,...,Tm, каждое из которых, в свою очередь, является деревом.
Определение Деревья T1,T2,...Tm называются поддеревьями данного дерева.
Определение Упорядоченным деревом мы будем называть такое дерево, в котором важен порядок следования поддеревьев T1,T2,...Tm.
Определение Дуга - это ориентированная связь между двумя вершинами дерева, поэтому, например, корень можно определить, как такую вершину дерева, в который не входит ни одной дуги, поэтому часто говорят, что корень - это "исходная" вершина дерева, через которую доступны остальные его вершины.
Определение Ребро - это неориентированная связь между двумя вершинами дерева. Ясно, что ребро можно превратить в дугу, если задать на нем ориентацию (направление), а любое дерево можно превратить в ориентированное дерево, если задать ориентацию ребер.
Определение Количество поддеревьев некоторой вершины называется степенью этой вершины. Деревья, имеющие степень больше 2, называются сильно ветвящимися деревьями.
Определение Вершина с нулевой степенью называется листом, иначе - она называется внутренней вершиной (внутренним узлом).
Определение Число листьев дерева называется весом дерева.
Определение Символы A,B,C,..., которые служат для обозначения вершин, называются метками вершин.
Приведенное неформальное определение является рекурсивным (мы определили дерево в терминах деревьев). Ниже мы дадим формальное нерекурсивное определение дерева, но рекурсивное определение кажется более подходящим, так как рекурсивность является естественной характеристикой структур типа дерево.
Для удобства дальнейших рассмотрений договоримся о графическом способе изображения деревьев. Корень будем располагать выше поддеревьев (ясно, что корень при изображении будет располагаться выше всех остальных вершин дерева). Вершины дерева будем изображать точками на плоскости, а корень дерева связывать дугами (ребрами) с корнями деревьев T1,T2,...Tm. Взгляните на рисунок и на комментарии, приведенные ниже его:
Рис.1. Иллюстрация основных понятий
Символы A, B, C, D, K, L, M, N, R - метки вершин, вершина А - корень, вершины C, L, R, M, N, K - листья, вес дерева равен 6 (количество листьев - 6), вершина В имеет степень 2, вершина D имеет степень 4.
Определение (неформальное)
Вершина Y, которая находится непосредственно под узлом X, называется (непосредственным) потомком (сыном) X, вершина X в данном случае называется (непосредственным) предком (отцом) Y.
В этом случае, если вершина X находится на уровне i, то говорят, что вершина Y находится на уровне i+1. Мы будем считать, что корень дерева расположен на уровне 0.
Определение Максимальный уровень какой-либо вершины дерева называется его глубиной или высотой.
Определение Максимальная степень всех вершин дерева называется степенью дерева.
Теперь, например, ясно, что:
- если вершина не имеет потомков, то она является листом;
- степень внутренней вершины можно определить, как число ее (непосредственных) потомков.
Максимальное число вершин в дереве заданной высоты h достигается в случае, когда все вершины имеют по d поддеревьев, кроме вершин уровня h, не имеющих ни одного. Тогда в дереве степени d нулевой уровень содержит одну вершину (корень), первый уровень содержит d ее потомков, второй уровень содержит d2 потомков d узлов уровня 2 и т.д.
Таким образом получаем, что максимальное число вершин для дерева с высотой h и степенью d можно найти по формуле:
При d=2 мы получаем:
