Д. Кнут - Искусство программирования том 1 (1119450), страница 88
Текст из файла (страница 88)
[20] Придумайте систеллу обозначений для узлов бинарного дерева, аналогичную десятичной системе обозначений Дьюи для узлов деревьев 16. [20] Нарисуйте схемы, аналогичные изображенным на рис 21 которые соответствуют следующим арифметическим выражениям (а) 2(а — 6/с), (Ъ) а+ 6+ бс 17. [01) Если представленную на рис 19 структуру рассматривать как лес Г, то какому узлу будет соответствовагь узел-родитель множества поддеревьев (К[1 2,2])» 18. [0В] Каким элементам в Списке (3) соответствуют обозначения А[5 1, Ц и 2[3 Ц» 19. [15] Создайте схему Списка, аналогичную схеме (7), лля Списка б = (а, (б)) Калим элементам »тола Списка соответствуют обозначения А[2) и Ц2 1, Ц» ь 20.
[М21) Пусть 0-2-дерево обозначает дерево в котором каждый узел не имеет ни одного потомка нли имеет двух детей (Формально О-2-дерево состоит из одного узла — -корня, плюс О или 2 непересекающихся О-2-деревьев ) Покажите, что каждое О-2-дерево имеет нечетное число узлов, и установите взанчно однозначное соответствие между биварнычи деревьями с и узлачи и (упорядоченнымн) О-2-деревьями с 2и+ 1 узлами 21. [М22] Если дерево имеет п~ узлов степени 1, и» узлов с»олени 2, и и, узлов степени т, го сколько в неч содержи»ля концевых узлов» ь 22. [21) Используемые в Европе стандартные форматы страниц АО, А1, А2,, Ап, представляют собой прямоугольники с соотношением сторон л/2 к 1 и площадью 2 квадратных четров Следовательно, при разрезании пополам страницы формата Ап получич две страницы формала А(а+ 1) Используя данный принцип, создайте графичел кое представление бинарных деревьев и проиллюстрируйте эту идею на приллере структуры 2 3 1 — (1) из следующего раздела 2.3.1.
Обход бинарных деревьев Прежде чем продолжить изучение деревьев, необходимо тщательно рассмотреть свойства бинарных деревьев, поскольку деревья общего типа обычно представляются внутри компьютера в виде некоторого эквивалентного бинарного дерева Бинарное дерево определено выше как конечное множество узлов, которое может либо быть пустым, либо состоять из корня вместе с двумя другими бинарными деревьями. Это определение наводит на мысль о естественном способе представления бинарных деревьев внутри компьютера: каждый узел имеет связи 1ь1вК и Н.1МК, а также переменную связи Т, которая явлиется указателем дерева. Если дерево пусто, то Т = Л; в противном случае Т является адресом корневого узла этого дерева, а 111МК(Т), К11КК(Т) †указателя на левое и правое поддеревья этого корня соответственно.
Данные правила рекурсивно определяют представление в памяти любого бинарного дерева. Например, дерево может быть представлено таким образом: (2) Это простое и естественное представление дерева в памяти компьютера и объясняет особую важность бинарных древовидных структур Как показано в разделе 2.3.2, деревья общего типа очень удобно представлять в виде бинарных деревьев. Более того, многие деревья в приложениях сами по себе являются бинарными, поэтому они представляют особый интерес. Существует достаточно много алгоритмов работы с древовидными структурами, в которых наиболее часто встречается понятие обхода (1гасегзтд) дерева или "прохода" по дереву.
При таком методе исследования дерева каждый узел посещается в точности один раз, а полный обход дерева задает линейное упорядочение узлов, что позволяет упростить алгоритм, так как при этом можно использовать понятие "следующий" узел, т. е. узел, который располагается перед данным узлом в таком упорядочении или после него.
Для обхода бинарного дерева можно применить один из трех принципиально разных способов: е прямом порядке (ргеагдег), в центрироаанном порядке (тагдег) или е обратном порядке (раз1огдег). Эти три метода определяются рекурсивно. Если бинарное дерево пусто, то для его "обхода" ничего делать не потребуется, в противном случае обход выполняется в три этапа. Центрированный порядок обхода Пройти левое поддерево Попасть в корень Пройти правое поддерево Прямой порядок обхода Попасть в корень Пройти левое поддерево Пройти правое поддерево Обратный порядок обхода Пройти левое поддерево Пройти правое поддерево Попасть в корень Если применить эти определения к бинарному дереву (1) и (2), то при прямом порпдке обхода узлов получим последовательность А В Р С Е С Е Н Х (Сначала следует корень А, затем — левое поддерево в прямом порядке, и, наконец, правое поддерево в прямом порядке.) При центрированном порядке обхода корень посещается после обхода узлов одного из деревьев точно так, как если бы узлы дерева "проектировались" на горизонтальную прямую с образованием последовательности (4) Р В А Е С С Н Е Х Аналогично обратный порядок обхода позволяет получить последовательность Р В С Е Н Х Е С А.
(5) Как будет показано ниже, эти три способа упорядочения узлов бинарного дерева в виде линейной последовательности чрезвычайно важны, поскольку они тесно связаны с большинством компьютерных методов обработки деревьев. Названия прямой, пенглрированнмй н обратный происходят, конечно, от расположения корня по отношению к поддеревьям. Во многих приложениях бинарных деревьев понятия левого и правого поддеревьев совершенно симметричны, и в таких случаях термин симметричный порядок используется в качестве синонима понятия центирированнмй порядок.
Центрированный порядок, при котором корень располагается посередине, образует симметрию относительно левой и правой сторон: при отражении бинарного дерева относительно вертикальной оси получается простое обращение симметричного порядка. Для применения в компьютерных вычислениях предложенные выше рекурсивные определения трех основных способов обхода придется сформулировать несколько иначе. Наиболее общие методы такой переформулировки рассматриваются в главе 8. Обычно для этого используется вспомогательный стек, например так, как в показанном ниже алгоритме.
Рис. 23. Алгоритм Т для симметричного обхода. Алгоритм Т (Обход дерева в симметричном порядке). Пусть Т вЂ” указатель на бинарное дерево с представлением (2). Тогда в этом алгоритме (рис. 23) все узлы бинарного дерева обходятся в симметричном порядке с помощью вспомогательного стека А.
Т1. [Инициализация.] Опустошить стек А и установить переменную связи Р ~- Т. Т2. [Р = А?[ Если Р = Л, перейти к шагу Т4. ТЗ. [Стек ~ Р.[ (Теперь Р указывает на непустое бинарное дерево, которое нужно пройти.) Установить А ~=- Р, т. е.
вставить (протолкнуть) значение Р в стек А (см, раздел 2.2.1). Затем установить Р ~- ЕЕ1МК(Р) и вернуться к шагу Т2. Т4. [Р с.= Стек.[ Если стек А пуст, выполнение алгоритма прекращается; в противном случае угтановить Р ~ А. Х5.[Попасть в Р.[ Попасть в узел МООЕ(Р). Затем установить Р +- Ы.1МК(Р) и вернуться к шагу Т2. 1 На заключительном шаге этого алгоритма слово "попасть" означает, что по мере обхода дерева прн попадании в узел выполняется заранее предусмотренная обработка узлов.
Алгоритм Т по отношению к другим действиям основной программы выполняется как сопрограмма, т. е, основная программа вызывает эту сопрограмму для перехода от одного узла к другому в заданном симметричном порядке. Конечно, так как эта сопрограмма вызывает основную процедуру только в одном месте, она не очень отличается от подпрограммы (см. раздел 1.4.2).
В алгоритме Т предполагается, что в результате выполнения внешних действий в данном дереве не удаляется нн узел МООЕ(Р), ни любой друтой его узел-предшественник. Чтобы понять идею, лежащую в основе этого алгоритма, читатель может в качестве полезного упражнения применить алгоритм Т к бинарному дереву (2). По достижении шага ТЗ следует приступить к обходу бинарного дерева с корнем, на который указывает Р. При этом основная идея заключается в сохранении указателя Р в стеке с последующим обходом левого поддерева. После выполнения этих действий необходимо вернуться к шагу Т4 и найти прежнее значение Р в стеке.
После обхода корня МОРЕ(Р) на шаге Т5 остается только совершить обход правого поддерева. Алгоритм Т типичен для многих других алгоритмов. которые будут рассмотрены ниже, поэтому' имеет смысл привести формальное доказательство утверждений из предыдущего абзаца. Докажем с помощью метода индукции, что алгоритм Т позволяет совершить обход бинарного дерева с и узлами в симметричном порядке. Наша цель будет достигнута, если доказать справедливость несколько более общего утверждения. Начиная с шага Т2 с указателем Р на бинарное дерево с п узлами и стеком А, содержащим элементы А [Ц...
А[т3 для некоторого т > О, эта процедура на шагах Т2-Т5 совершит обход бинарного дерева в симметричном порядке, а затем вернется к шагу Т4 с возвратом стека А в его исходное состояние А П]... А [т3 Для и = О это утверждение очевидно выполняется, как следствие шага Т2.
Если и > О, пусть Ро нвляется значением указателя Р в начале шага Т2. Так как Ре ~ Л, выполним шаг ТЗ, что для стека А означает его изменение с приведением к новому состоянию с элементами АП]...А[т]Ро, а Р равняется ЕЕ1МК(ре). Теперь левое поддерево имеет меньше и узлов, а потому по индукции выполним обход левого подлерева в симметричном порядке и перейдем к шагу Т4 со стеком, содержание которого равно А П3... А [т] Ре. На шаге Т4 стек возвращается в исходное состояние А П3 ...
А [т3, а Р «- Ре. На шаге Т5 выполняется обход узла МОВЕ(ро) и устанавливается значение Р «- ЕЕ1МК(ре). Теперь правое поддерево имеет менее п узлов и по индукции совершаем обход правого поддерева в симметричном порядке с переходом к шагу Т4. Таким образом выполнен обход всего дерева в симметричном порядке согласно определению этого порядка. Доказательство завершено.
Практически идентичный алгоритм можно сформулировать для обхода бинарных деревьев в прямом порядке (см. упр. 12). Несколько сложнее выглядит алгоритм обхода в обратном порядке (см. упр. 13), а потому подобный порядок не имеет такого большого значения, как два других. Для указания узлов-последователей и узлов-предшественников в алгоритмах обхода бинарных деревьев удобно применять следующие обозначения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
