Вершина дерева имеющая максимальный уровень
На этом шаге мы приведем основные термины, которые будут использоваться при изучении бинарных деревьев .
- имеется одна специально выделенная вершина, называемая корнем дерева ;
- остальные вершины (исключая корень) содержатся в m попарно непересекающихся множествах T1,T2. Tm , каждое из которых, в свою очередь, является деревом.
Деревья T1,T2. Tm называются поддеревьями данного дерева .
Упорядоченным деревом мы будем называть такое дерево, в котором важен порядок следования поддеревьев T1,T2. Tm .
Дуга — это ориентированная связь между двумя вершинами дерева, поэтому, например, корень можно определить как такую вершину дерева, в который не входит ни одной дуги, поэтому часто говорят, что корень — это «исходная» вершина дерева, через которую доступны остальные его вершины.
Ребро — это неориентированная связь между двумя вершинами дерева. Ясно, что ребро можно превратить в дугу, если задать на нем ориентацию (направление), а любое дерево можно превратить в ориентированное дерево, если задать ориентацию ребер.
Количество поддеревьев некоторой вершины называется степенью этой вершины. Деревья, имеющие степень больше 2, называются сильно ветвящимися деревьями .
Вершина с нулевой степенью называется листом , иначе — она называется внутренней вершиной (внутренним узлом) .
Число листьев дерева называется весом дерева.
Символы A,B,C. , которые служат для обозначения вершин, называются метками вершин .
Приведенное неформальное определение является рекурсивным (мы определили дерево в терминах деревьев). Ниже мы дадим формальное нерекурсивное определение дерева, но рекурсивное определение кажется более подходящим, так как рекурсивность является естественной характеристикой структур типа дерево.
Для удобства дальнейших рассмотрений договоримся о графическом способе изображения деревьев. Корень будем располагать выше поддеревьев (ясно, что корень при изображении будет располагаться выше всех остальных вершин дерева). Вершины дерева будем изображать точками на плоскости, а корень дерева связывать дугами (ребрами) с корнями деревьев T1,T2. Tm . Взгляните на рисунок и на комментарии, приведенные ниже его:
Рис.1. Иллюстрация основных понятий
Символы A, B, C, D, K, L, M, N, R — метки вершин , вершина А — корень , вершины C, L, R, M, N, K — листья , вес дерева равен 6 (количество листьев — 6), вершина В имеет степень 2, вершина D имеет степень 4.
Определение 2 (неформальное) Вершина Y , которая находится непосредственно под узлом X , называется (непосредственным) потомком (сыном) X , вершина X в данном случае называется (непосредственным) предком (отцом) Y .
В этом случае, если вершина X находится на уровне i , то говорят, что вершина Y находится на уровне i+1 . Мы будем считать, что корень дерева расположен на уровне 0. Максимальный уровень какой-либо вершины дерева называется его глубиной или высотой .
Максимальная степень всех вершин дерева называется степенью дерева .
- если вершина не имеет потомков, то она является листом ;
- степень внутренней вершины можно определить как число ее (непосредственных) потомков.
Максимальное число вершин в дереве заданной высоты h достигается в случае, когда все вершины имеют по d поддеревьев, кроме вершин уровня h , не имеющих ни одного. Тогда в дереве степени d нулевой уровень содержит одну вершину (корень), первый уровень содержит d ее потомков, второй уровень содержит d 2 потомков d узлов уровня 2 и т.д.
Таким образом получаем, что максимальное число вершин для дерева с высотой h и степенью d можно найти по формуле:
Определение 3 (неформальное) Количество дуг, которые нужно пройти, чтобы продвинуться от корня к вершине X , называется длиной пути к вершине X . Очевидно, что вершина, расположенная на уровне i , имеет длину пути i .
Ветвью будем называть путь от корня дерева к любому ее листу .
Длина пути дерева определяется как сумма длин путей ко всем его вершинам . Она также называется длиной внутреннего пути дерева . Длина внутреннего пути может быть определена по следующей рекурсивной формуле:
Длина внутреннего пути = Длина внутреннего пути в левом поддереве + Длина внутреннего пути в правом поддереве + Количество узлов в дереве - 1.
Для иллюстрации определений приведем рисунок двух деревьев, которые будем предполагать упорядоченными:
Рис.2. Упорядоченные деревья
- длина пути к вершине L равна 3,
- длина пути к вершине К равна 1,
- длина внутреннего пути равна 18,
- одно из ветвей дерева — AKDL .
Дерево II отличается от дерева I , так как в нем изменен порядок следования поддеревьев с корнями K и B . Определение 4 [1] (неформальное) Лес — это множество деревьев (обычно упорядоченное), состоящее из некоторого (быть может, равного нулю) числа непересекающихся деревьев. Часто для леса, состоящего из n деревьев пользуются термином «дерево с n-кратным корнем» .
Между лесами и деревьями есть лишь небольшое различие; если мы удалим у дерева корень, то получим лес, и наоборот, если к любому лесу добавить всего один узел, то получим дерево.
- либо пусто,
- либо состоит из корня (некоторая выделенная нами вершина), связанного с двумя различными бинарными деревьями, называемыми левым и правым поддеревом корня .
Важно отметить, что бинарное дерево не является частным случаем дерева, определенного выше. Оно представляет собой упорядоченное (см. в определении бинарного дерева слова «. с двумя различными бинарными деревьями. » ) дерево, у которого в каждую вершину, отличную от корня, входит только одна дуга, а выходит не более двух. При этом для каждой входящей дуги известно, является ли она правой или левой.
Каждая вершина бинарного дерева, отличная от корня, может рассматриваться как корень бинарного поддерева с вершинами, достижимыми из нее.
Изобразим несколько бинарных деревьев:
Рис.4. Примеры бинарных деревьев
Определение 6 (неформальное) Говорят, что два бинарных дерева T и T’ подобны , если они имеют одинаковую структуру ; это означает, что подобные деревья либо оба пусты, либо оба непусты и их левые и правые поддеревья соответственно подобны.
Попросту говоря, подобие означает, что графические изображения деревьев T и T’ имеют одинаковую «конфигурацию».
Говорят, что бинарные деревья T и T’ эквивалентны , если они подобны и если, кроме того, соответствующие вершины содержат одинаковую информацию.
- либо оба пусты,
- либо же оба непусты, Info (Корень(T))=Info (Корень(T’)) и их левые и правые поддеревья соответственно эквивалентны.
В качестве иллюстрации приведенных определений рассмотрим четыре бинарных дерева:
Первые два из них не подобны; второе, третье и четвертое деревья подобны, причем второе и четвертое эквивалентны. (1) Кнут Д. Искусство программирования для ЭВМ. Т.1: Основные алгоритмы. — M.: Мир, 1976. — 736 с.
Со следующего шага мы начнем рассматривать бинарные деревья поиска .
Источник
Лекция 21. Деревья. Обход дерева Деревья
Дерево – это связный неориентированный граф без циклов (или связный граф с минимальным числом ребер). Связным называют граф, в котором для любых двух вершин существует связывающий их путь. Дерево имеет n-1 ребер, где n — число вершин.
Дерево с выделенной вершиной (корнем) называют корневым деревом. В дальнейшем под деревом понимается корневое дерево.
Дерево обычно рассматривают как ориентированное, причем от корня (реже — к корню), но изображают без стрелок. Преемников вершины называют ее сыновьями, предшественника – отцом (в этом случае более уместно называть вершину узлом – словом мужского рода).
Корень обычно изображают наверху, на уровне 0, остальные вершины — ниже, на уровнях, соответствующих расстоянию от корня. Сыновья вершин уровня i относятся к уровню i+1. Высотой дерева считают максимальный уровень его вершин.
Степень вершины равна числу ее сыновей (в отличие от других графов, не учитывается входящая сверху дуга). Вершины без сыновей называют терминальными (концевыми) вершинами или листьями, вершины, имеющие сыновей, называют внутренними. Дерево называют упорядоченным, если сыновья каждой вершины каким-либо образом упорядочены.
Важную роль играет бинарное дерево — упорядоченное дерево степени два: вершина имеет не более двух сыновей — корни ее левого и правого поддерева.
Деревья определяют очень распространенные иерархические отношения (подчиненность, старшинство, вложенность, родственные отношения и т. п.). Приведем примеры.
1. Структура книги, состоящей из разделов, подразделов и т. д. Вершина — часть книги, ее сыновья — вложенные в нее составные части. Аналогично представляется: структура организации и ее подразделений; состав промышленного изделия из агрегатов и входящих в них узлов и деталей; программа из модулей, подпрограмм, блоков и операторов; скобочная структура выражения; грамматическая структура предложения и т. д.
На рис. 21.1 — структура оператора присваивания: листья — операнды; внутренняя вершина представляет операцию, а ее сыновья – операнды этой операции, которые могут быть результатом других операций.
Рис. 21.1. Древовидная структура выражения
2. Генеалогические деревья: предки человека (бинарное дерево) и его потомки. В случае брака между потомками и наличия у них общего ребенка ветви дерева потомков срастаются, образуя орграф более общего вида, чем дерево.
3. История спортивного турнира с выбыванием побежденного — бинарное дерево: вершина — игра, сыновья — ее участники или определившие их игры.
Операции над деревьями такие же, как для графов.
Представление деревьев
Для деревьев можно использовать любые методы хранения графов, но матрица смежности неудобна, т. к. сильно разрежена (доля единиц меньше, чем 2 / n, где n — число вершин). Обычно используют списковые структуры и сети. На рис. 21.2 а — 21.2 в показано дерево и примеры его представления списковой структурой и регулярной сетью. Списковая структура (рис. 21.2 б) содержит элементы двух типов: для вершин и для дуг.
Неудобство нерегулярной сети — разные размеры элементов из-за разного числа ссылок. У регулярной сети много места занимают пустые ссылки.
а) Дерево б) Списковая структура дерева
A
C
Рис. 21.2. Способы представления деревьев
Этих недостатков не будет, если вместо исходного дерева хранить бинарное дерево с теми же вершинами, полученное из исходного дерева по принципу “левый сын – правый брат”. Каждая вершина бинарного дерева имеет две ссылки: к ее левому сыну и правому брату в исходном дереве. Это преобразование взаимно однозначно и по бинарному дереву можно восстановить исходное дерево.
Таким способом можно хранить и совокупность деревьев – лес, т.е. несвязный граф без циклов. Корни составляющих лес деревьев считаются братьями и упорядочиваются по какому-либо принципу.
На рис. 21.2 г показано бинарное дерево, соответствующее дереву рис. 21.2а; на рис. 21.2 д — представление бинарного дерева в виде регулярной сети с тремя ссылками: не только вниз к двум сыновьям, но и вверх к отцу.
Дополнительные ссылки расширяют пути доступа, но тратится память и время на их корректировку — нужен компромисс.
Дерево можно представить вектором: у каждой вершины одна ссылка наверх, к отцу, как в алгоритме обхода графа в ширину. Бинарные деревья представляются также с помощью адресной арифметики.
Источник