Уровень корня дерева равен

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

Дерево — это граф, который характеризуется следующими свойствами:

• 1. Cуществует единственный элемент (узел или вершина), на который не ссылается никакой другой элемент — и который называется КОРНЕМ .
• 2. Начиная с корня и следуя по определенной цепочке указателей, содержащихся в элементах, можно осуществить доступ к любому элементу структуры.
• 3. На каждый элемент, кроме корня, имеется единственная ссылка, т.е. каждый элемент адресуется единственным указателем.

Название «дерево» проистекает из логической эквивалентности древовидной структуры абстрактному дереву в теории графов. Линия связи между парой узлов дерева называется обычно ВЕТВЬЮ. Те узлы, которые не ссылаются ни на какие другие узлы дерева, называются ЛИСТЬЯМИ (или терминальными вершинами) Узел, не являющийся листом или корнем, считается промежуточным или узлом ветвления (нетерминальной или внутренней вершиной). Для ориентированного графа число ребер, исходящих из некоторой начальной вершины V, называется ПОЛУСТЕПЕНЬЮ ИСХОДА этой вершины. Число ребер, для которых вершина V является конечной, называется ПОЛУСТЕПЕНЬЮ ЗАХОДА вершины V, а сумма полустепеней исхода и захода вершины V называется ПОЛНОЙ СТЕПЕНЬЮ этой вершины. ДеревоЛес Ниже будет представлен важный класс орграфов — ориентированные деревья — и соответствующая им терминология. Деревья нужны для описания любой структуры с иерархией. Традиционные примеры таких структур: генеалогические деревья, десятичная классификация книг в библиотеках, иерархия должностей в организации, алгебраическое выражение, включающее операции, для которых предписаны определенные правила приоритета. Ориентированное дерево — это такой ациклический орграф (ориентированный граф), у которого одна вершина, называемая корнем, имеет полустепень захода, равную 0, а остальные — полустепени захода, равные 1. Ориентированное дерево должно иметь по крайней мере одну вершину. Изолированная вершина также представляет собой ориентированное дерево. Вершина ориентированного дерева, полустепень исхода которой равна нулю, называется КОНЦЕВОЙ (ВИСЯЧЕЙ) вершиной или ЛИСТОМ; все остальные вершины дерева называют вершинами ветвления. Длина пути от корня до некоторой вершины называется УРОВНЕМ (НОМЕРОМ ЯРУСА) этой вершины. Уровень корня ориентированного дерева равен нулю, а уровень любой другой вершины равен расстоянию (т.е. модулю разности номеров уровней вершин) между этой вершиной и корнем. Ориентированное дерево является ациклическим графом, все пути в нем элементарны. Во многих приложениях относительный порядок следования вершин на каждом отдельном ярусе имеет определенное значение. При представлении дерева в ЭВМ такой порядок вводится автоматически, даже если он сам по себе произволен. Порядок следования вершин на некотором ярусе можно легко ввести, помечая одну вершину как первую, другую — как вторую и т.д. Вместо упорядочивания вершин можно задавать порядок на ребрах. Если в ориентированном дереве на каждом ярусе задан порядок следования вершин, то такое дерево называется УПОРЯДОЧЕННЫМ ДЕРЕВОМ. Введем еще некоторые понятия, связанные с деревьями. Узел X называется ПРЕДКОМ (или ОТЦОМ), а узлы Y и Z называются НАСЛЕДНИКАМИ (или СЫНОВЬЯМИ) их соответственно между собой называют БРАТЬЯМИ. Причем левый сын является старшим сыном, а правый — младшим. Число поддеревьев данной вершины называется СТЕПЕНЬЮ этой вершины. ( В данном примере X имеет 2 поддерева, следовательно СТЕПЕНЬ вершины X равна Если из дерева убрать корень и ребра, соединяющие корень с вершинами первого яруса, то получится некоторое множество несвязанных деревьев. Множество несвязанных деревьев называется ЛЕСОМ Мы видели, что последовательности и списки можно опре­делить следующим образом: любая последовательность (спи­сок) с базовым типом Т — это либо: пустая последовательность (список); либо конкатенация (цепочка) из элемента типа Т и последова­тельности с базовым типом Т. Здесь для определения принципов структурирования (сле­дования или итерации) используется рекурсия. Следование и итерация встречается настолько часто, что их обычно счи­тают фундаментальными «образами» как структур данных, так и «управления» в программах. Однако всегда следует помнить, что с помощью рекурсий их только можно опреде­лять, но рекурсии можно эффективно и элегантно использо­вать для определения более сложных структур. Хорошо известным примером служат деревья. Пусть дре­вовидная структура определяется следующим образом:дре­вовидная структура с базовым типом Т — это либо: 1) пустая структура; либо 2) узел типа Т, с которым связано конечное число древовид­ных структур с базовым типом Т, называемых подде­ревьями. Из сходства рекурсивных определений последовательно­стей и древовидных структур видно, что последовательность (список) есть древовидная структура, у которой каждый узел имеет не более одного «поддерева». Поэтому последователь­ность (список) называется также вырожденным деревом. Существует несколько способов изображения древовидной структуры. Например, пусть базовый тип Т есть множество букв; такая древовидная структура разными способами изо­бражена на рис. Все эти представления демонстрируют одну и ту же структуру и поэтому эквивалентны. С помощьюграфа можно наглядно представить разветвляющиеся связи, которые по понятным причинам привели к общеупотребитель­ному термину «дерево». Однако довольно странно, что де­ревья принято рисовать перевернутыми или — если кто-то предпочитает иначе выразить этот факт — изображать корни дерева. Но последняя формулировка вводит в заблуждение, так как верхний узел (Л) обычно называюткорнем. Хотя мысознаем, что в природе деревья представляют собой не­сколько более сложные образования, чем наши абстракции, мы будем в дальнейшем древовидные структуры называть просто деревьями.Упорядоченное дерево — это дерево, у которого ветви каж­дого узла упорядоченные. Следовательно, два упорядочен­ных дерева— это особые, отличные друг от друга деревья. Узел у, который находится непосредственно под узлом х, называется (непосредственным) потомком х; если л находится науровнеI, то говорят, чтоу — на уровнеi-\-\. Наоборот, узелх называется (непосредственным)предком у. Считается, что корень дерева расположен на уровне 1. Макси­мальный уровень какого-либо элемента дерева называется его глубиной или высотой. Если элемент не имеет потомков, он называется терми­нальным элементом или листом, а элемент, не являющийся терминальным, называетсявнутренним узлом. Число (непо­средственных) потомков внутреннего узла называется егостепенью. Максимальная степень всех узлов есть степень де­рева. Число ветвей, или ребер, которые нужно пройти, чтобы продвинуться от корня к узлух, называетсядлиной пути.Корень имеет длину пути 1, его непосредственные потомки — длину пути 2 и т. д. Вообще, узел на уровне i имеет длину пути L Длина пути дерева определяется как сумма длин пу­тей всех его узлов. Она также называется длиной внутрен­него пути. Например, длина внутреннего пути дерева, изображенного на рис. 2.1, равна 52. Рис 2.1.Представления древовидной структуры. Для того чтобы определить, что называется длиной внешнего пути, мы будем дополнять дерево специальным узлом каждый раз, когда в нем встре­чается нулевое поддерево. При этом мы считаем, что все узлы должны иметь одну и ту же степень — степень дерева. Следо­вательно, подобное расширение дерева предполагает заполнение пустых ветвей, разумеется, при этом специальные узлы не имеют дальнейших потомков. Дерево на рис. 2.1, допол­ненное специальными узлами, показано на рис. 2.3, где спе­циальные узлы изображены квадратиками. Рис. 2.2 Два различных бинарных дерева. Рис. 2.3. Тернарное дерево со специальными узлами. Длина внешнего пути теперь определяется как сумма длинпутей всех специальных узлов. У дерева, приведенного на рис. 2.3, длина внешнего пути равна 153. Число специальных узлов т, которые нужно добавить к дереву степени d, непосредственно зависит от числа п ис­ходных узлов. Заметим, что на каждый узел указывает ровно одна ветвь. Следовательно, в расширенном поддереве имеется m -f- n ветвей. С другой стороны, из каждого исходного узла выходят d ветвей, а из специальных узлов — ни одной. По­этому всего имеетсяdn -f- 1 ветвей (1 дает ветвь, указываю­щую на корень). Из этих двух формул мы получаем следую­щее равенство между числом m специальных узлов и п исход­ных узлов: dn + 1 = m -f- n,илиm=(d—l)n+l. Максимальное число узлов в дереве заданной высоты h достигается в случае, когда все узлы имеют d поддеревьев, кроме узлов уровня h, не имеющих ни одного. Тогда в дереве степени d первый уровень содержит 1 узел (корень),уровень2 содержит d его потомков, уровень 3 содержит d2 потомков d узлов уровня 2 и т. д. Это дает следующую величину: N_d (А) = 1 +d+d2+ . +dh‘1= £dl в качестве максимального числа узлов для дерева с высотой h и степенью d. При d= 2 мы получаем N₂(h)=Z 2′ = 2 ft -l. Упорядоченные деревья степени 2 играют особо важную роль. Они называются бинарными деревьями. Мы определяем упорядоченное бинарное дерево как конечное множество эле­ментов (узлов), каждый из которых либо пуст, либо состоитиз корня (узла), связанного с двумя различными бинарнымидеревьями, называемыми левым и правым поддеревом корня. В следующих пунктах этого раздела мы будем рассматривать исключительно бинарные деревья и поэтому будем употреб­лять слово «дерево», имея в виду «упорядоченное бинарное дерево». Деревья, имеющие степень больше 2, называются сильно ветвящимися деревьями (multiwaytrees).. Знакомыми примерами бинарных деревьев являются фамильное (генеалогическое) дерево с отцом и матерью человека в качестве его потомков (!), история теннисного турнира, где узлом является каждая игра, определяемая ее победителем, а поддеревьями — две предыдущие игры соперников; арифметическое выражение с двухместными операциями, где каждаяоперация представляет собой ветвящийся узел с операндами в качестве поддеревьев.

Источник