Лекции по информатике (984119), страница 6
Текст из файла (страница 6)
6. Глубиной дерева называется наибольшее значение уровня вершины. По определению уровня, внутренние вершины дерева пе могут находиться на максимальном уровне. Таким образом, для определения глубины необходимо вычислить максимальный уровень для всех терминальных вершин дерева. В приведенном примере дерева корнем является А, узлы 1, << К, !., М, М< О и Р листья, вершины В, С, В, Е, Е, С и П узлы разветвления.
У у ла А степень равна 2, а у узла Е 3. Дерево имеет 4 уровня и все сто листья находятся на 4-ом уровне (в обгцем случае уровни листьев могут бьггь разными). Для описания взаимного расположения узлов принята терминология генеалогических деревьев, соответствующая родстгюнным отношениям между лицами преимущественно по мужской линии (ошец, сып или предок и потомок, но дочерняя вершина).
Корень дерева является отцом для всех узлов 2-го уровня, которые составляют множество его сыновей. Лналогично определяются эти отношения и лля других узлов дерева. Сыновья одного узла, часто называл>тся братьями. В примере дерева узел В является отцом узлов !) и Е и сыном для узла, А.
Узлы 1) и Е родные братья. узлы Р, С и Н тоже родные братья, но не братья для Р и Е. Если порядок поддеревьев существенен (а в оольшинстве приложений дело обстоит именно так), то сыновья упорядочиваются по номерам слева направо. Говоря о порядке сыновей, употребляют также термины сшарший и младший (чем меньше номер у сына,, тем он старше). Старшинство сыновей будет удобно выражать явно в виде очереди. Определенные нами таким образоги деревья называются деревьями общего вида или сильно ветвящимися. Эти деревья представляют собой пепуипые структуры (есть по крайней мере один элемент — корень) с многозвепным разветвлением каждой вершины на непересекающиеся поддеревья. Иногда с целью унификации функциональных спецификаций допускаются пустые деревья общего вида. 5.9.1 Двоичные деревья Бинарное. (двоичное) дерево — это конечное мно.кество узлов.
которое или пусто или состоит из корня и двух непересекающихся поддеревьев, называемых левым и правым поддеревьями данного узла. Бинарное дерево пе является частным случаем дерева общего вида, это особый вид структуры данных, хотя и близкий к дереву. Различие этих понятий видно на рисунке: Два нарисованных дерева идентичны как деревья, но различаются как бинарные деревья, так как у первого из них есть левое поддерево,но нет правого, а у второго наоборот,нет левого поддерева,но есть правое. На этом же рисунке изображено и пустое (невидимое!) двоичное дерево.
Таким образом, в бинарном дереве существенное значение имеет наклон ветвей, в то время как в обычном дереве он несущественен. Вторая особенность: бинарное дерево, в отличие от обычного, может быть пустым [72[. Бинарные деревья имеют важное значение в практике программирования; одна из причин этого заключается в том, что обычные деревья часто представляются с помощью специальных классов бинарных деревьев, т. к. их проще хранить и обрабатывать [63[.
Важным для информатики классом двоичных деревьев являются деревья арифметиче ских выражений с бинарными и унарными операциями, где каждой операции соответствует вершина,, поддеревьями которой являя>тся се операнды [54[. Рассмотрим представление 267 выражения (а ( 6/с) * (И вЂ” е л л') в виде дерева. Подобно математическим формулам выражения в языках программирования представлшот собой линейную запись со скобками, которые, вообще говоря, могут быть вложенными и на самом деле имеют существенно нелинейную интерпретацию. Нижеприведенное дерево выражения, оставаясь нелинейным объектом, представляет собой бесскобочнук> форму записи.
Роль скобок, в том числе и отсутствукнцих(!), играют поддеревья дерева выражения: В дальнейшем борьба со скобочностью и нелинейностью выражений буде г продолжена. Это необходимо для автоматического анализа, интерпретации и вычисления выражений на ЭВМ. Другие примеры: генеалогическое (семейное) дерево или родословная: родители каждого человека изображаются как его потомки Я, схема, спортивного турнира, проходящего по кубковой (оликлпийской) системе — проигравший выбывает.
Ниже приведен типичный пример турнирного дерева (данные взяты с теннисного турнира Апйга1ла Ореп 2005 'птьр://2005.апвтга1тапореп.сош ): Р оже Федерер Роже Федерер Андрэ Агасси Марат Сафин Марат Сафин Марат Сафин Доминик Хрбати Марат Сафин Давид Налбандян Ллсйтон Хьюз Ллейтон Хьюэтт Ллейтон Хьюэт Николай Давыденко Энди Родлик Энди Родлик 5.9.2 Двоичная интерпретация дерева общего вида Для преобразлзвания произвольного дерева в бинарное, надо в исходном дереве у каждого узла соединить его сыновей лот старпкто к ближайшему младшему брату) и убрать все связи узлов с сыновьями, сохранив лищь связь с первым сыном, за, которым выс ьраивается своеобразная очередь сыновей нисходящий правосторонний каскад [721. Для получения привычного вила дерева результат надо развернуть на 45' по часовой стрелке: В общем виде алгоритм преобразования обычного дерева Л в двоичное дерево В сводится к рекурсивному применению следующих правил: ° корень В есть корень Л; ° левое поддерево двоичного дерева В есть результат этого же преобразования первого поддерева дерева Л, если оно существует; ° правое поддерево двоичного дерева В есть результат этого преобразования очеред- ного брата, узла Л, если он существует.
Этот алгоритм можно проил,пострировать так Щ: 5.9.3 Функциональная спецификация '1'ип ВТт, или двоичное дерево типа Т, определяется так ~72~: СОЗДАТЬ: ПОСТРОИТЬ: ПУСТО: КОРЕНЬ: СЛЕВА: С! 1РАВА: УНИЧТОЖИТЬ; а — ВТ ВТт х Т х ВТт — ВТт ВТт — Ьоо1еап ВТт — ВТт ВТт — ~ ВТт ВТт — ~ О Функция С'1ЕВА осу.ществляет доступ к левому поддереву непустого дерева, а СПРАВА — к правому. Функция ПОСТРОИТЬ создает дерево из корня и двух заданных поддеревьев, одно из которых становится левым, другое - правым.
270 Здесь а', ~3',..., Л' — результаты конвертации соответствующих поддеревьев о, В,..., Л этим же алгоритмом. Данный алгоритм применим и в обратную сторону: рекурсивпо следуя по каскаду и преобразуя левые поддеревья каждого узла в его сыновей, а правые -- в братьев данного узла, получим снова исходное дерево общего вида. Доказательство может быть проведено индукцией по глубине дерева. Для дерева, состоящего из одной вершины, преобразование верно (базис индукции). Теперь предположим, что для 1ьуровыевого дерева утверждение справсдливо (гипотеза индукции).
Чтобы преобразовать дерево 1:+ 1-го уровня, надо сделать левое поддерево сыном, а правое братом, которые являются деревьями не более чем к:-ого уровня. Замечание. Изложенный рекурсивный алгоритм преобразования любого дерева общего вида в двоичное имеет и концептуальное значение. Подобно теореме Ьойма-ДжакопиниМиллса он конструктивно доказывает эквива.юнтность этих двух разновидностей де1эевьев; двои шые деревья есть деревья ограниченного разветвления аналогично тому, что схемы машин Тьюринга, с ограниченным набором управляющих структур были полным эквивалентом диги рамм.
Это определение подходит под спецификанию дека,, хотя моделирование дерева на, деке задача не гривиальная. Свойства операций: 1. ПУСТО(СОЗДАТЬ) -- $гпе 2. ПУСТО(ПОСТРОИТЬ(6(с, 1, .61,)) -- Га1ве 3. КОРЕНЬ(ПОСТРОИТЬ(61~, .1, 6Х„)) =- 6 4. СЛЕВА(ПОСТРОИТЬ(6Хп 1, 6Х„)) 61~ 5. СПРАВА(ПОСТРОИТЬ(оп 1, 68,)) 61„ б. ПОСТРОИТЬ<СЛЕВА~61), КОРЕНЬ<И), СПРАВА~Ы)) -- И Последнее может быть выражено словами слелуклцим образом; каждое дерево получено построением из своего корня, левым поддеревом имеет свое левое поддерево, а правым поддеревом свое правое. Перечислим некоторыс операции над деревьями. Операции заданы в самом обпк м виде, без спецификации параметров: 1.
чтение данных из узла дерева: 2, создание дерева, состоящего из ощюго корневого узла; 3, построение дерева из заданных корпя и нескольких поддеревьев: 4. присоединение к узлу нового поддерева; 5. замена поддерева на новое поддерево; 6. удаление поддерева; 7. получение узла, следующего за данным в определбнном порядке. В зависимости от решаемых задач и вида используемых деревьев могут быть предусмотрены и другис операции ~б3~.
5.9.4 Логическое описание Тип данных дерево обычно отсутствует в универсальных языках программирования, и нам придется его моделировать программно. Детали для этого моделирования, увы, не могут быть заимствованы из готового набора Юапс!агс1 Тегпр1аге Ь11эгагу: ввиду сложности и многообразия деревьев и способов их обработки не существует стандартных универсальных пакетов для этой цели.
Впрочем, для этой цели есть более подходягцис языки Лисп и Пролог. Однако, когда мы ограничены фон Неймановскими языками, процедурная реализация средств работы с деревьями не представляет особого труда. Так же, как и в списках, цепная структура дерева будет состоять из динамически порождаемых элементов, в которых предусмотрены ссылки на очередные компоненты структуры. В двунаправленных списках были указатели вперед и назад, а здесь будут 271 ссылки В'к'ВО Вниз и В1гравО Вниз, ЛинейыОе пре11Н1ествование и следОВание заменя111ся нелинейным разветвленис1м, которос может ветвиться далыпс по каждой из ветвей. Тип данных лля узла дерева внешне тот жс: Динамическая структура данных для вышеописанного дерева выражения может быть изображена так: Ввиду нелинейности дрсзвовидных структур существенно усложняется их обход.
5.10 Алгоритмы обработки деревьев 5.10.1 Понятие обхода дерева При анализе структур данных, заданных в виде дерева, применяются разные способы проСА1отра или перебора узлов дерева. Такой просмотр называется обходом дерева. Основная особенность обхода состоит в том, что просматриваются все без исключения узлы дерева в нскотпором порядка... причем каждый узел обрабатывается ровно один раз. Обход дерева предс1тавляст собой линейно упорядоченное рассмотрение всех его вершин, от предыдуще1о элех1ента к следук1щсму.
Ее!!и пройденные В11рп1ины засюсить В очередь или В Список, то этот порядок станет явной линсаризацией дерева. Из структуры двоичных деревьев вьгп-'кает три различных дисциплины упорядочсгшого прохождения вершин 163~. Суре рпос1е — псн1е; 1И111с гесогс1 1сеу: с11аг; 1, г: рпос1е; епс1; ВСгг1сС пос1е с11аг 1сс1у; ВСгпсС пос1еа 1; ВСгг1сС пос!е1 г; 5.10.2 Алгоритмы обхода двоичных деревьев Для бинарного дерева определены три способа обхода: прямой (или сверху вниз), обратный (или слева направо) и концевой (или снизу вверх).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
