Определение. Корневые (ориентированные) деревья

Корневые (ориентированные) деревья

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

Определение

Дерево вместе с выделенным корнем образует ориентированный граф (ребро ориентируют в направлении от корня), который называют корневым деревом.

Пример

f g a c

b d a e

b c

f b d

d a g e

f g

c e

В корневых деревьях часто используется генеалогическая терминология. Для любого ориентированного ребра (u, v) – u – отец, v – сын.

Вершины, у которых нет сыновей, называются листьями. Аналогично вводится понятие потомков и предков. Если существует путь из вершины v в w, то v – предок, а w – потомок.

Определение

Корневое дерево называют m-арным, если каждая его вершина имеет не больше, чем m сыновей. Если m=2, то дерево называется бинарным.

Определение

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

Определение

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

Корневое дерево является рекурсивным объектом, который содержит сам себя и определяется с помощью самого себя.

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

Теперь определим формально понятие корневого дерева.