Ориентированные, упорядоченные и бинарные деревья

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

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

1. Существует единственный узел r, полустепень захода которого равна 0, d⁺(r) = 0. Он называется корнем ордерева.

2. Полустепень захода всех остальных узлов равна 1, v V \ { r } d⁺(r) = 1 == 1.

3. Каждый узел достижим из корня, v V \ { r } <v, u >.

Пример

На рис. 9.5 приведены диаграммы всех различных ориентированных деревьев с 3 узлами, а на рис. 9.6 показаны диаграммы всех различных ориентированных деревьев с 4 узлами.

Теорема. Ордерево обладает следующими свойствами:

1. q = р - 1;

2. если в ордереве забыть ориентацию дуг, то получится свободное дерево;

3. в ордереве нет контуров

4. для каждого узла существует единственный путь, ведущий в этот узел из корня;

5. подграф, определяемый множеством узлов, достижимых из узла v, является ордеревом с корнем v (это ордерево называется поддеревом узла v);

6. если в свободном дереве любую вершину назначить корнем, то получится ордерево.

рис. 9.5. Ориентированные деревья с 3 узлами

Рис. 9.6. Ориентированные деревья с 4 узлами