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

Ориентированное дерево (корневое ориентированное дерево) (рисунок 6.76) – это ориентированный граф без циклов со свойствами:

1. Существует в точности одна вершина , называемая корнем, в которую не заходит ни одна дуга.

2. В каждую вершину, кроме корня, заходит в точности одна дуга.

3. Существует путь из корня в любую другую вершину.

Рисунок 6.76

Потомок вершины – это вершина , в которую ведет путь из вершины ; при этом называется предком для . Если длина этого пути равна 1, то есть из в ведет дуга, то – «отец» для , а – «сын» для .

Вершины, у которых общий отец, называются братьями или сестрами.

Вершина, не имеющая потомков, называется листом.

Глубина вершины в дереве – это длина пути из корня в .

Высота вершины в дереве – это длина самого длинного пути из в какой-нибудь лист.

Высота дерева – это число дуг самого длинного пути, то есть высота корня.

Уровень вершины – это разность между высотой всего дерева и глубиной вершины .

Высота дерева на рисунке 6.77 равна 3, вершина 8 имеет глубину 2, высоту 1, уровень 1.

Рисунок 6.77

Лемма. Если в любом неориентированном дереве выбрать произвольную вершину в качестве корня и сориентировать все ребра в направлении «от корня», т.е. сделать началом всех инцидентных ей ребер, вершины, смежные с – началами всех инцидентных им еще не сориентированных ребер и т.д., то полученный в результате ориентированный граф будет ориентированным деревом.

Упорядоченное ориентированное дерево – это дерево, у которого множество сыновей каждой вершины упорядочено, обычно слева направо, как на рисунке 62: .

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

Бинарное ориентированное дерево называют полным, если из любой его вершины, не являющейся листом, исходят ровно две дуги, а уровни всех листьев совпадают.

Каждая вершина бинарного дерева может иметь либо двух сыновей – левого и правого (вершина 2 имеет левого сына 3 и правого сына 4), либо иметь только левого сына (левый сын 9 вершины 8), либо только правого сына (вершина 5 – единственный правый сын вершины 4), либо не иметь ни одного сына (листья 3, 5, 7, 9).

Бинарное дерево называется полным, если у каждой его внутренней вершины имеется два сына и все его ветви имеют одинаковую длину.

Полное бинарное дерево уровня – это дерево, в котором каждый узел уровня является листом и каждый узел уровня меньше имеет непустые левое и правое поддеревья.

На рисунке 6.78 приведен пример полного бинарного дерева уровня 3.

Рисунок 6.78

Левое поддерево вершины – это максимальное поддерево, корнем которого является левый сын вершины .

Правое поддерево вершины – это максимальное поддерево, корнем которого является правый сын вершины .

На рисунке 6.77 левое поддерево вершины 6 состоит из одной вершины 7, правое поддерево – из вершин 8, 9 и дуги (8,9).

Теорема 6.13 (теорема о высоте бинарного ориентированного дерева с заданным числом листьев). Бинарное ориентированное дерево с листьями имеет высоту, не меньшую .