AOP_Tom1 (1021736), страница 90
Текст из файла (страница 90)
[М21) Пчсть 0-2-дерево обозначает дерево в котором каждый узел не имеет ни одного потомка или имеет двух детей (чормально О-2-дерево состоит из одного узла — корня, плюг О или 2 непересекающихся О-2-деревьев ) Покажите, что каждое 0-2-дерево имеет нечетное чисао узлов, и чстановите взшгино однозначное соответствие между бинарнычи деревьями с и узлами и (упорядоченными) О-2-деревьями с 2п + 1 узлами 21. [М22) Если дерево имеет п~ узлов степени 1, пэ узлов степени 2, и и, узлов степени т, го сколько в нем содержте я концевых узловч ь 22.
[21] Используемые в Европе стандартные форматы страниц АО, А1, А2,, Ап, представляют собой прямочгольники с соотношением сторон чГ2 к 1 н площадью 2 квадратных метров Следовательно, при разрезании пополам страницы формата Ап получим две страницы формата А(п -ь 1) Используя данный принцип, создайте графическое представление бинарных деревьев н проиллюстрируйте эту идею на црнмере структчры 2 3 1-(1) из следующего раздела 2.3.1. Обход бинарных деревьев Прежде чем продолжить изучение деревьев, необходимо тщательно рассмотреть свойства бинарных деревьев, поскольку деревья общего типа обычно представляются внутри компьютера в виде некоторого зквиваленгного бинарного дерева Бинарное дерево определено вьппе как конечное множество узлов, которое может либо быть пустым, либо состоять из корня вместе с двумя другими бинарными деревьями. Это определение наводит на мысль о естественном способе представления бинарных деревьев внутри компьютера: каждый узел имеет связи 11.1МК и К1.1МК, а также переменную связи Т, которая являетгя указателем дерева.
Если дерево пусто, то Т = Л; в противном случае Т является адресом корневого узла этого дерева, а 1.11МК(Т), М1.1МК(Т) — указателями на левое и правое подлеревья этого корня соответственно. Данные правила рекурсивно определяют представление в памяти любого бинарного дерева. Например, дерево может быть представлено таким образом: (2) Это простое и естественное представление дерева в памяти компьютера и объясняет особую важность бинарных древовидных структур Как показано в разделе 2.3.2, деревья общего типа очень удобно представлять в виде бинарных деревьев.
Более того, многие деревья в приложениях сами по себе являются бинарными, поэтому они представляют особый интерес. Существует достаточно много алгоритмов работы с древовидными структурами, в которых наиболее часто встречается понятие обхода (1гаеегюпу) дерева или "прохода" по дереву. При таком методе исследования дерева каждый узел посещается в точности один раз, а полный обход дерева задает линейное упорядочение узлов, что позволяет упростить алгоритм,так как при этом можно использовать понятие "следующий" узел, т, е, узел, который располагается перед данным узлом в таком упорядочении нли после него. Для обхода бинарного дерева можно применить один из трех принципиально разных способов: в прямом порядке (ргеогг1ег), в центрированком порл0ке (ьпогйег) или в обратном порядке (роз1оп1ег).
Эти три метода определяются рекурсивно. Если бинарное дерево пусто, то для его "обхода" ничего делать не потребуется, в противном случае обход выполняется в три этапа. Центрированный порядок обхода Пройти левое поддерево Попасть в корень Пройтн правое поддерево Прямой порядок обхода Попасть в корень Пройти левое поддерево Пройти правое поддерево Обратный порядок обхода Пройти левое поддерево Пройти правое поддерево Попасть в корень Если применить эти определения к бинарному дереву (1) и (2), то при прямом порядке обхода узлов получим последовательность А В Р С Е С Г Н Х (Сначала следует корень А, затем — левое поддерево в прямом порядке, и, наконец, правое поддерево в прямом порядке.) При центрированном порядке обхода корень посещается после обхода узлов одного из деревьев точно так, как если бы узлы дерева "проектировались" на горизонтальную прямую с образованием последовательности (4) Р В А Е С С Н Е Х Аналогично обратный порядок обхода позволяет получить последовательность Р В С Е Н 1 Г С А.
(5) Как будет показано ниже, эти три способа упорядочения узлов бинарного дерева в виде линейной последовательности чрезвычайно важны, поскольку они тесно связаны с большинством компьютерных методов обработки деревьев. Названия прямой, ценелрированный и обратный происходят, конечно, от расположения корня по отношению к поддеревьям. Во многих приложениях бинарных деревьев понятия левого н правого поддеревьев совершенно симметричны, и в таких случаях термин симметричный порядок используется в качестве синонима понятия центрированный порядок. Центрированный порядок, при котором корень располагается посередине, образует симметрию относительно левой и правой сторон: при отражении бинарного дерева относительно вертикальной оси получается простое обращение симметричного порядка. Для применения в компьютерных вычислениях предложенные выше рекурсивные определения трех основных способов обхода придется сформулировать несколько иначе. Наиболее общие методы такой переформулировки рассматриваются в главе 8.
Обычно для этого используется вспомогательный стек, например так, как в показанном ниже алгоритме. е - ллтяк(е) Рис. 23. Алгоритм Т лля симметричного обхода. Алгоритм Т (Обход дерева в сомме<прочном порядке). Пусть Т вЂ” указатель на бинарное дерево с представлением (2). Тогда в этом алгоритме (рис. 23) все узлы бинарного дерева обходятся в симметричном порядке с помощью вспомогательного стека А.
Т1. (Инициализация.] Опустошить стек А и установить переменную связи Р < — 1. Т2. ]Р =- Л".] Если Р = Л, перейти к шагу Т4, ТЗ. (Стек ~ Р.] (Теперь Р указывает на непустое бинарное дерево, которое нужно пройти,) Установить А ~ Р, т. е. вставить (протолкнуть) значение Р в стек А (сч. раздел 2.2.1). Затем установить Р < — ЕЕ1НК(Р) и вернуться к шагу Т2. Т4. ]Р ~ Стек.] Если стек А пуст, выполнение алгоритма прекращается; в против- ном случае установить Р <.= А. Т5. [Попасть в Р.] Попасть в узел НОРЕ(Р).
Затем установить Р < — ЕЕ1НК(Р) и вернуться к шагу Т2. к На заключительном шаге этого алгоритма слово "попастья означает, что по мере обхода дерева при попадании в узел выполняется заранее предусмотренная обработка узлов. Алгоритм Т по отношению к другим действиям основной программы выполняется как сопрограмма, т. е. основная программа вызывает эту сопрограл<му для перехода от одного узла к другому в заданном симметричном порядке.
Конечно, так как эта сопрограмма вызывает основную процедуру только в одном месте, она не очень отличается от подпрограммы (см. раздел 1.4.2). В алгоритл<е Т предполагается, что в результате выполнения внешних действий в данном дереве не удаляется ни узел НООЕ(Р), ни любой другой его узел-предшественник. Чтобы понять идею, лежащую в основе этого алгоритл<а, читатель может в качестве полезного упражнения применить алгоритм Т к бинарному дереву (2). По достижении шага ТЗ следует приступить к обходу бинарного дерева с корнем, на который указывает Р. При этом основная идея заключается в сохранении указателя Р в стеке с последующим обходом левого поддерева.
После выполнения этих действий необходимо вернуться к шагу Т4 и найти прежнее значение Р в стеке. После обхода корня НОРЕ(Р) на шаге Т5 остаегся только совершить обход правого поддерева. Алгоритм Т типичен лля многих других алгоритмов, которые будут рассмотрены ниже, поэтому имеет смысл привести форл<альное доказательство утверждений из предыдущего абзаца, Докво<сем с помощью метода индукции, .что алгоритм Т позволяет совершить обход бинарного дерева с и узлами в симметричном порядке.
Наша цель будет достигнута, если доказать справедливость несколько более общего утверждения. Начиная с шага Т2 с указателем Р иа бинарное дерево с и узлами н стеком А, содержащим элементы А [Ц... А [т3 для некоторого т > О, э»в процедура иа шагах Т2-Тб совершит обход бинарного дерева в симметричном порядке, а затем вернется к шагу Т4 с возвратом стека А в его исходное состояние А [Ц ... А [т]. Р* — адрес Рэ — адрес Р» — адрес ьР— адрес ЗР— адрес »Р — адрес узла-последователя МООЕ(Р) При обходе в прямом порядке; узла-последователя МООЕ(Р) при обходе в симметричном порядке; узла-последователя МОВЕ(Р) при обходе в обратном порядке; узла-предшественника МОВЕ(Р) при обходе в прямом порядке; узла-предшественника МООЕ(Р) при обходе в симметричном порядке; узла-предшественника МОРЕ(Р) при обходе в обратном порядке. (6) Если узел ИООЕ(Р) не имеет узлов-предшественников и узлов-последователей, то обычно используется обозначение ЕОС(Т), где Т вЂ” это внешний указатель на данное дерево.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
