Структуры данных. Деревья - 6 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

Составители: 

Рубрика: 

8
То есть дерево можно определить как граф, в котором
а) имеется одна особая вершина, называемая корнем, в которую не заходит
ни одно ребро;
б) во все остальные вершины заходит ровно одно ребро, а исходит сколько
угодно ребер.
По аналогии с деревьями ребра называют ветвями, а вершины на концах
ветвей –
листьями.
Стандартная терминология для структур типа дерева обязана своим проис-
хождением родовой схеме (рисунок 1) генеалогического дерева. Термины предок
и потомок для обозначения родства могут простираться на несколько уровней
дерева.
Итак, терминология, используемая в связи с деревьями, включает следую-
щие понятия:
Узел или вершина – каждый элемент дерева.
Поддерево называют потомком по отношению
к своей вершине –
предку.
Корень – особая вершина дерева, не имеющая предка.
Каждый узел, кроме корня, имеет единственного предка.
Вершина связана с каждым из своих поддеревьев ветвью.
Узлы, не имеющие поддеревьев ( потомков ), называются листьями или
терминальными вершинами.
Узлы, не являющиеся терминальными, называются внутренними.
Число непосредственных потомков внутреннего узла называется его
степенью.
Максимальная степень всех узлов есть степень дерева.
Вершина (например, D на рисунке 3), находящаяся непосредственно ниже
другой вершины (B на рисунке 3), называется непосредственным ее потомком;

Страницы