Ориентированные, упорядоченные и бинарные деревья
Ориентированные (упорядоченные) деревья являются абстракцией иерархических отношений, которые очень часто встречаются как в практической жизни, так и в математике и в программировании. Дерево (ориентированное) и иерархия – это равнообъемные понятия.
Ориентированные деревья. Ориентированным деревом (или ордеревом, или корневым деревом) называется орграф со следующими свойствами: 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. Сыновья одного узла называются братьями.
Эквивалентное определение ордерева.
Ордерево T— это конечное множество узлов, таких что:1)Имеется один узелv, называемый корнем данного дерева;2)Остальные узлы (исключая корень) содержатся вkпопарно непересекающихся множествах.
Упорядоченные деревья.
Множества в эквивалентном определении ордерева являются поддеревьями.
Если относительный порядок поддеревьев фиксирован, то ордерево называется упорядоченным.
Представление в эвм свободных, ориентированных и упорядоченных деревьев.
Обсуждению представлений деревьев можно предпослать в точности те же рассуждения, что были предпосланы обсуждению представлений графов (см. раздел 7.4). Кроме того, следует подчеркнуть, что задача представления деревьев в программе встречается гораздо чаще, чем задача представления графов общего вида, а потому методы ее решения оказывают еще большее влияние на практику программирования.
Представление свободных, ориентированных и упорядоченных деревьев.
Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Всякое упорядоченное дерево можно представить бинарным деревом, проведя правую связь к старшему брату, а левую - к младшему сыну.
Замечание: Рассматривается генеологическая терминология. Узлы, достижимые из узла называются потомками. Если в дереве существует дугаu,v, то узелuназывают отцом, а узелv– сыном. Сыновья одного узла - братья
Пример:На рис. приведены диаграммы упорядоченного и соответствующего ему бинарного деревьев.
Таким образом, достаточно рассмотреть представление в ЭВМ бинарных деревьев.
Замечание:Из данного представления следует, что множество бинарных деревьев взаимнооднозначно соответствует множеству упорядоченных лесов упорядоченных деревьев.