![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Определение. Корневые (ориентированные) деревьяСтр 1 из 3Следующая ⇒
Корневые (ориентированные) деревья Рассмотрим такое понятие, как корневое дерево. Во многих приложениях определенную вершину дерево обозначают как корень. После этого можно вполне естественно задать ориентацию для каждого ребра графа. Поскольку в дереве существует единственная простая цепь от корня к каждой вершине, то каждой ребро ориентируют в направлении от корня.
Определение Дерево вместе с выделенным корнем образует ориентированный граф (ребро ориентируют в направлении от корня), который называют корневым деревом.
Пример
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, то дерево называется бинарным.
Определение Совокупность вершин, которые находятся на расстоянии к от корня, называется к уровнем или к ярусом дерева.
Определение Высотой корневого дерева называют максимальный из уровней его вершин.
Корневое дерево является рекурсивным объектом, который содержит сам себя и определяется с помощью самого себя. В корневом дереве
Теперь определим формально понятие корневого дерева.
|