Новиков Ф.А. Дискретная математика для программистов (860615), страница 56
Текст из файла (страница 56)
теоремы 9.1.2,G' — дерево.[ 3 ] Следует из п. 2.[ 4 ] От противного. Если бы в G существовали два пути из г в v, то в G' имелсябы цикл.9.2. Ориентированные, упорядоченные и бинарные деревья299[ 5 ] Пусть Gv — правильный подграф, определяемый множеством узлов, достижимых из v. Тогда d~Qv (v) = 0, иначе узел v был бы достижим из какого-то узлаv' е Gv и, таким образом, в Gv, а значит, и в G имелся бы контур, что противоречит п.
3. Далее имеем: W е Gv - v ( d + ( v ' ) = 1), так как Gv с G. Все узлыGv достижимы из v по построению. По определению 9.2.1 получаем, что Gv —ордерево.[ 6 ] Пусть вершина г назначена корнем и дуги последовательно ориентированы«от корня» обходом в глубину. Тогда d+(r) = 0 по построению; Vv е V — г (d + (v) = 1), так как входящая дуга появляется при первом посещении узла;все узлы достижимы из корня, так как обход в глубину посещает все вершинысвязного графа.
Таким образом, по определению 9.2.1 получаем ордерево.•СЛЕДСТВИЕАлгоритм поиска в глубину строит ордерево с корнем в начальномузле.ЗАМЕЧАНИЕКаждую вершину в свободном дереве с р вершинами можно назначить корнем и получить ордерево. Некоторые из полученных ордеревьев могут оказаться изоморфными.Следовательно, свободное дерево определяет не более р различных ориентированных деревьев. Таким образом, общее число различных ордеревьев с р узлами не более чем в рраз превосходит общее число различных свободных деревьев с р вершинами.Концевая вершина ордерева называется листом.
Множество листьев называется кроной. Путь из корня в лист называется ветвью. Длина наибольшей ветвиордерева называется его высотой. Уровень узла ордерева — это расстояние откорня до узла. Сам корень имеет уровень 0. Узлы одного уровня образуют ярусордерева.ЗАМЕЧАНИЕНаряду с «растительной» применяется еще и «генеалогическая» терминология. Узлы,достижимые из узла и, называются потомками узла и (потомки одного узла образуютподдерево). Если узел v является потомком узла и, то узел и называется предком узла v.Если в дереве существует дуга (U, v), то узел и называется отцом (ИЛИ родителем) узлаv, а узел v называется сыном узла и. Сыновья одного отца называются братьями.9.2.2. Эквивалентное определение ордереваОрдерево Т — это непустое конечное множество узлов, на котором определеноразбиение, обладающее следующими свойствами:1.
Имеется один выделенный одноэлементный блок {г}, называемый корнемданного ордерева.2. Остальные узлы (исключая корень) содержатся в к (к ^ 0) блокахT\,...,Tk,каждый из которых, в свою очередь, является ордеревом и называется поддеревом.300Глава8.СвязностьDefНетрудно видеть, что данное определение эквивалентно определению 9.2.1.
Достаточно построить орграф, проводя дуги от заданного корня ордерева г к корнямподдеревьев Т \ , . . . , Ть и далее повторяя рекурсивно этот процесс для каждого изподдеревьев.9.2.3. Упорядоченные деревьяЕсли относительный порядок поддеревьев Т \ , . . . ,Тк в эквивалентном определении ордерева фиксирован, то ордерево называется упорядоченным.ПримерыОриентированные и упорядоченные ориентированные деревья интенсивно используются в программировании:1. Выражения. Для представления выражений языков программирования, какправило, используются ориентированные упорядоченные деревья.
Примерпредставления выражения а + b * с показан на рис. 9.7, а.2. Для представления блочной структуры программы и связанной с пей структуры областей определения идентификаторов часто используется ориентированное дерево (может быть, неупорядоченное, так как порядок определения переменных в блоке в большинстве языков программирования считаетсянесущественным). На рис.
9.7, б показана структура областей определенияидентификаторов а, Ь, с, d, е, причём для отображения иерархии использованывложенные области.3. Для представления иерархической структуры вложенности элементов данныхи/или операторов управления часто используется техника отступов, показанная на рис. 9.7, в.4.
Структура вложеипости каталогов и файлов в современных операционныхсистемах является упорядоченным ориентированным деревом. Обычно дляизображения таких деревьев применяется способ, показанный па рис. 9.7, г.5. Различные «правильные скобочные структуры» (например (a(b)(c(d)(e)))) являются ориентированными упорядоченными деревьями.ааЬЬссddJV.абеевРис. 9.7. Примеры изображения деревьев в программированииг9.2. Ориентированные, упорядоченные и бинарные деревья301ОТСТУПЛЕНИЕТот факт, что большинство систем управления файлами использует ориентированныедеревья, отражается даже в терминологии, например: «корневой каталог диска».ЗАМЕЧАНИЕОбщепринятой практикой при изображении деревьев является соглашение о том, что корень находится наверху и все дуги ориентированы сверху вниз, поэтому стрелки можноне изображать.
Таким образом, диаграммы свободных, ориентированных и упорядоченныхдеревьев оказываются графически неразличимыми, и требуется дополнительное уточнение, дерево какого класса изображено па диаграмме. В большинстве случаев это ясно изконтекста.Пример На рис. 9.8 приведены три диаграммы деревьев, которые внешне выглядят различными. Как упорядоченные деревья они действительно все различны: (1) ф (2), (2) ф (3), (3) ф (1). Как ориентированные деревья (1) = (2), но(2) ф (3). Как свободные деревья они все изоморфны: (1) = (2) = (3).(1)(2)(3)Рис.
9.8. Диаграммы деревьевУказанное в подразделе 9.2.2 построение позволяет определить па упорядоченном ордереве единый линейный порядок узлов, согласованный с уже заданнымив дереве упорядочениями.ТЕОРЕМАВ упорядоченном ордереве с р узлами существует такая нумерацияузлов числами из диапазона 1 ..р, что номера потомков больше номеров предков иномера старших братьев больше номеров младших братьев.Применим к упорядоченному ордереву алгоритм обхода в глубину (алгоритм 7.1), начиная с корня, причём узлы, смежные с данным, посещаются в порядке, определяемым порядком поддеревьев (см. 9.2.2).
Присвоимузлам номера в порядке первого посещения. По теореме 7.4.6 все узлы получатуникальные номера из диапазона 1..ри корень получит номер 1. Далее, старшиебратья получат номера, большие, чем номера младших братьев по условию обхода, а потомки получат номера большие, чем номера предков, поскольку алгоритмобхода в глубину посещает предков раньше, чем потомков.•ДОКАЗАТЕЛЬСТВО302Глава8.СвязностьЗАМЕЧАНИЕУказанный порядок обхода часто называют прямым.Пример Узлы упорядоченного ордерева на рис.
9.11 слева при прямом обходеполучат следующие номера: a i—• 1, Ь i—• 2, с и 5, d i—• 3, е н 4 , /6, д ^ 7,h I—• 8, г I—• 9.ЗАМЕЧАНИЕПостроенная в доказательстве теоремы нумерация не является единственной нумерацией,обладающей указанными свойствами.Пример Можно обойти упорядоченное ордерево по ярусам. При этом узлыупорядоченного ордерева на рис. 9.11, слева, получат следующие номера: а1,6 |—• 2, с I—>• 3, d I—• 4, е I—• 5, / I—>• 6, ^ I—> 7, Л. —i »• 8, г —i >• 9.9.2.4. Бинарные деревьяБинарное (или двоичное) дерево — это непустое конечное множество узлов, накотором определена структура, обладающая следующими свойствами:1.
Имеется один выделенный узел г, называемый корнем данного бинарногодерева.2. Остальные узлы (исключая корень) содержатся в двух непересекающихсямножествах (поддеревьях) — левом и правом, каждое из которых, в своюочередь, либо пусто, либо является бинарным деревом.На первый взгляд может показаться, что бинарное дерево — это частный случай упорядоченного ориентированного дерева, в котором у каждого узла не более двух смежных.
Но это не так, бинарное дерево не является упорядоченнымордеревом. Дело в том, что даже если у некоторого узла бинарного дерева имеется только одно непустое поддерево, то всё равно известно, какое именно этоподдерево: левое или правое.Пример На рис. 9.9 приведены две диаграммы деревьев, которые изоморфныкак упорядоченные, ориентированные и свободные деревья, но не изоморфныкак бинарные деревья.Рис.
9.9. Два различных бинарных дерева9.3. Представление деревьев в программах303ЗАМЕЧАНИЕПонятие двоичного дерева допускает обобщение, т-ичным деревом называется непустоеконечное множество узлов, которое состоит из корня и m непересекающихся подмножеств, имеющих номера 1,...,ш, каждое из которых в свою очередь, либо пусто, либо является m-ичиым деревом. Большая часть утверждений и алгоритмов для двоичных деревьев может быть сравнительно легко распространена и на m-ичные деревья(с соответствующими модификациями).
Поэтому хотя на практике m-ичные деревья ииспользуются достаточно часто, здесь мы ограничиваемся только двоичными деревьями.9.3. Представление деревьев в программахОбсуждению представлений деревьев можно предпослать в точности те же рассуждения, что были предпосланы обсуждению представлений графов (см. 7.4).Кроме того, следует подчеркнуть, что задача представления деревьев в программе встречается гораздо чаще, чем задача представления графов общего вида,а потому методы её решения оказывают ещё большее влияние на практику программирования.9.3.1. Представление свободных деревьевДля представления деревьев можно использовать те же приёмы, что и для представления графов общего вида — матрицы смежиости и инциденций, спискисмежности и др.
Но используя особенные свойства деревьев, можно предложить существенно более эффективные представления. Рассмотрим следующеепредставление свободного дерева, известное как код Прюфера. Допустим, чтовершины дерева T(V,E) занумерованы числами из интервала 1 ..р. Построим последовательность А : array [1 ..р — 1] of 1 ..р в соответствии с алгоритмом 9.1.Алгоритм 9.1 Построение кода Прюфера свободного дереваВход: Дерево T(V,E) в любом представлении, вершины дерева занумерованычислами 1 ..р произвольным образом.Выход: Массив А : array [l..p - 1] of l..p — код Прюфера дерева Т.for г from 1 to р - 1 dov\ = min{k е V | d(k) = 1} { выбираем вершину v — висячую вершину снаименьшим номером }A[i]: = Г(ь) { заносим в код номер единственной вершины, смежной с v }V: = V — v { удаляем вершину v из дерева }end forПо построенному коду можно восстановить исходное дерево с помощью алгоритма 9.2.304Глава8.СвязностьАлгоритм 9.2 Распаковка кода Прюфера свободного дереваВход: Массив А : array [1..р — 1] of 1..р — код Прюфера дерева Т.Выход: Дерево T(V, Е), заданное множеством рёбер Е, вершины деревазанумерованы числами 1 ..р.Е : = 0 { в начале множество рёбер пусто }В: = 1..р { множество неиспользованных номеров вершин }for г from 1 to р — 1 dov : = min [к Е В \ \/ j ^ i (к Ф А[?'])}{ выбираем вершину v — неиспользованную вершину с наименьшим номером, который не встречается в остатке кодаПрюфера }Е-.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
