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

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

Ориентированные деревья. Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами: 1) Существует единственный узел, полустепень захода которого равна 0. Он называется корнем ордерева. 2) Полустепень захода всех остальных узлов равна 1. 3)Каждый узел достижим из корня.

Пример:

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

__________

Теорема: Ордерево обладает следующими свойствами: 1) Число рёбер равно числу вершин-1(свойство древовидности): q = p – 1. 2) Если в ордереве отменить ориентацию ребер, то получится свободное дерево. 3) В ордереве нет контуров. 4) Для каждого узла существует единственный путь, ведущий в этот узел из корня. 5) Подграф, определяемый множеством узлов, достижимых из узла v, является ордеревом с корнем v (это ордерево называется поддеревом узла v). 6) Если в свободном дереве любую вершину назначить корнем, то получится ордерево.

Замечание: Каждое свободное дерево определяет не более р ориентированных деревьев. Таким обра­зом, общее число различных ордеревьев с р узлами не более чем в р раз превосходит общее число различных свободных деревьев с р вершинами.

Концевая вершина ордерева называется листом. Путь из корня в лист называется ветвью. Длина наибольшей ветви ордерева называется высотой. Уровень узла ордерева – это расстояние от корня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярус дерева.

Замечание: Наряду с "растительной" применяется еще и "генеалогическая" терминология. Узлы, достижимые из узла и, называются потомками узла и (потомки образуют поддерево). Если в дереве существует дуга (u,v), то узел 0 называется отцом (или родителем) узла u, а узел v называется сыном узла u. Сыновья одного узла называются братьями.