15. Упорядоченные деревья

Определение. Корневым деревом называется ориентированный граф, для которого выполняются следующие условия:

1) существует узел , называемый Корнем, для которого ;

2) для всех остальных узлов и каждый из них достижим из корня.

Например, на рис. 24 представлена диаграмма корневого дерева.

Рис. 24. Диаграмма корневого дерева

Корневое дерево также называется упорядоченным Деревом.

При рассмотрении деревьев используется растительная терминология. Уровнем узла называется расстояние от корня до этого узла. Ярусом дерева называется множество узлов одного уровня. Листом дерева называется сток графа. Ветвью дерева называется путь из корня в лист. Высотой дерева называется длина наибольшей ветви.

Например, в корневом дереве, изображенном на рис. 24, узел является корнем. Это узел нулевого яруса. Узлами первого уровня являются узлы и , образующие первый ярус дерева. Узлами второго уровня являются узлы , , , и . Они образуют второй ярус дерева. Узел является узлом третьего уровня. Листьями дерева являются узлы , , , и . Дерево имеет пять ветвей: , , , и . Длина наибольшей ветви равна трём, значит, дерево имеет высоту 3.

При рассмотрении деревьев также используется генеалогическая терминология. Корень дерева называется Предком, остальные узлы – Потомками. Среди потомков различаются Отцы – начала дуг и Сыновья – концы дуг.

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

Например, на рис. 25 представлена диаграмма бинарного дерева.

Рис. 25. Диаграмма бинарного дерева

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

Например, бинарное дерево, представленное на рис. 25, является полным деревом.

Задачи и упражнения

62. Сколько листьев имеет дерево с пятью внутренними узлами, порядок каждого из которых равен двум?

63. Найдите число бинарных деревьев с четырьмя узлами.

64. Сколько листьев имеет дерево, в котором кроме листьев содержатся два узла порядка 1 и три узла порядка 2?

Вопросы для самоконтроля

1. Сформулируйте свойство рангов матриц изоморфных графов.

2. Постройте диаграмму тривиального графа.

3. Приведите пример гамильтонова графа, одновременно являющегося эйлеровым.

4. Докажите, что всякое дерево является двудольным графом.

5. Установите, какие деревья являются полными двудольными графами.

6. Ориентированный граф с шестью узлами задан списком дуг . Задайте матрицей смежности вершин соответствующий Неориентированный граф.

< Предыдущая