Дискретная математика (998286), страница 43
Текст из файла (страница 43)
Пример представления выражения а + Ь * с показан на рис. 9.7 слева. 2. Для представления блочной структуры программы и связанной с ней структуры областей определения идентификаторов часто используется ориентированное дерево (может быть, неупорядоченное, так как порядок определения переменных в блоке в большинстве языков программирования считается несущественным). На рис. 9.7 в центре показана структура областей определения идентификаторов а, Ь, с,д, е, причем для отображения структуры дерева использована альтернативная техника.
3. Для представления иерархической структуры вложенности элементов данных и/или операторов управления часто используется техника отступов, показанная на рнс. 9.7 справа. Рис. 9.7. Примеры иэображения деревьев в программировании 4. Структура вложенности каталогов и файлов в современных операционных системах является упорядоченным ориентированным деревом. ОТСТУПЛЕНИЕ Это отражается даже в терминологии — «корневой каталог диска«.
5. Различные «уравиовешенные скобочиые структурыь (например (а(Ь)(с(д)(е)))) являются ориентированными упорядоченными деревьями. 242 Глава 9. Деревья здмичднии Общепринятой практикой при изображении деревьев является соглашение о том, что корень находится наверху и асе стрелки дуг ориентированы сверху вниз, поэтому стрелки можно не изображать. Таким образом, диаграммы свободных, ориентированных и упорядоченных деревьев оказываются графически неотличимыми, и требуется дополнительное указание, дерево какого класса изображено па диаграмме.
В большинстве случаев это ясно из контекста. Пример На рис. 9.8 приведены три диаграммы деревьев, которые внешне выглядят различными. Обозначим дерево слева — (1), в центре — (2) и справа — (3). Как упорядоченные деревья, они все различны: (1) -,~ (2), (2) ф (3), (3) ф (1). Как ориентированные деревья (1) = (2), но (2) ф (3). Как свободные деревья, они все изоморфны: (1) = (2) = (3). Рис. 9.8. Диаграммы деревьев 9.2.4. Бинарные деревья Бинарное дерево — это конечное множество узлов, которое либо пусто, либо состоит нз корня и двух непересекающихся бинарных деревьев — левого и правого. Бинарное дерево ие является упорядоченным ордеревом. Пример На рис.
9.9 приведены две диаграммы деревьев, которые изоморфны как упорядоченные, ориентированные и свободные деревья, но не изоморфны как бинарные деревья. Рис. 9.9. Два различных бинарных дерева 243 9,3. Представление деревьев в ЗВМ 9.3. Представление деревьев в ЭВМ Обсуждению представлений деревьев можно предпослать в точности те же рассуждения, что были предпосланы обсуждению представлений графов (см. раздел 7.4).
Кроме того, следует подчеркнуть, что задача представления деревьев в программе встречается горазда чаще, чем задача представления графов общего вида, а потому методы ее решения оказывают еще большее влияние на практику программирования. 9.3.1. Представление свободных, ориентированных и упорядоченных деревьев Всякое свободное дерево можно ориентировать, назначив один из узлов корнем, Всякое ордерево можно произвольно упорядочить. Всякое упорядоченное дерево можно представить бинарным деревом, проведя правую связь к старшему брату, а левую — к младшему сыну.
Пример На рис. 9.10 приведены диаграммы упорядоченного и соответствующего ему бинарного деревьев. Рис. 9.10. Упорядоченное и бинарное деревья Таким образом, достаточно рассмотреть представление в ЭВМ бинарных деревьев. ЗАМЕЧАНИЕ Из данного представления следует, что множество бинарных деревьев взвимноаднозначно соответствует множеству упорядоченных лесов упорялоченных деревьев. 244 Глене 9.
Деревья 9.3.2. Представление бинарных деревьев Обозначим через я(р) объем памяти, занимаемой представлением бинарного дерева, где р — число узлов. Наиболее часто используются следующие представления бинарных деревьев. 1. Списочные структуры: каждый узел представляется записью типа Ф, содержащей два поля (1 и г) с указателями на левый и правый узлы и еще одно поле 1 для хранения указателя на информацию об узле. Дерево представляется указателем на корень. Тип А' обычно определяется следующим образом: 1т' = гесоп1 г': юи,го; 1, г:Т Ю епй геена.
Для этого представления п(р) = Зр. ЗАМЕЧАНИЕ Поскольку в бинарном дереве, как н в любом другом, 9 = р — 1, то нз 2р указателей, отводимых для хранения дуг, р+ 1 всегда хранит значение яй, то есть половина связей не используется. 2. Упакованные массивы: все узлы располагаются в массиве, так что все узлы поддерева данного узла располагаются вслед за этим узлом. Вместе с каждым узлом хранится индекс узла, который является последним узлом поддерева данного узла. Дерево Т обычно определяется следующим образом: Т: аггау [1..р] оГ гесогп 1: Ыуо, й: 1..р епо георга. Для этого представления п(р) = 2р.
3. Польская запись: аналогично, но вместо связей фиксируется еразмеченная степень каждого узла (например, 0 означает, что это лист, 1 — есть левая связь, но нет правой, 2 — есть правая связь, но нет левой, 3 — есть обе сю(зн). Дерево Т определяется следующим образом: Т: аггау (1..р] оГ георга 1: ж~о, Н: 0..3 епй гесогй, Для этого представления н(р) = 2р. Если степень узла известна из информации, хранящейся в самом узле, то можно не хранить и степень. Такой способ представления деревьев называется польской записью и обычно используется для представления выражений. В этом случае представление дерева оказывается наиболее компактным: объем памяти п(р) = р. 9.3.3.
Обходы бинарных деревьев Большинство алгоритмов работы с деревьями основаны на обходах. Возможны следующие основные обходы бинарных деревьев: Прямой (левый) обход: попасть в корень, обойти левое поддерево, обойти правое поддерево. Обратный (симметричный) обход: обойти левое поддерево, попасть в корень, обойти правое поддерево. Концевой (правый) обход: обойти левое поддерево, обойти правое поддерево, попасть в корень. 245 9.3. Представление деревьев э ЭПМ Кроме трех основных, возможны еще три соответствующих обхода, отличающихся порядком рассмотрения левых и правых поддеревьев. Этим исчерпываются обходы, если в представлении фиксированы только связи «отец-сын», ЗАМЕЧАНИЕ Если кроме связей «отец-сын» в представлении есть другие связи, то возможны и другие (более эффективные) обходы.
*Деревья», в которых пустые поля «и г в сгруктуре )ь' используются для хранения дополнительных связей, называются прожитыми де)«ееьями. Пример Концевой обход дерева выражения а+Ь*с дает обратную польскую запись этого выражения: аЬс «+, ОТСТУПЛЕНИЕ Польская запись выражений (прямая или обратная) применяется в некоторых языках программирования непосредственно и используется в качестве внутреннего представления программ во многих трансляторах н интерпретаторах. Причина заключается в том, что такая форма записи допускает очень эффективную интерпретацию (вычисление значения) выражений. Например, значение выражения в обратной польской записи может быль вычислено при однократном просмотре выражения слева направо с использованием одного стека.
В таких языках, как ГоггЬ и Роз«Бспрк обратная польская запись используется как основная. 9.Э.4. Алгоритм симметричного обхода бинарного дерева Реализация обходов бинарного дерева с помощью рекурсивной процедуры не вызывает затруднений. В некоторых случаях из соображений эффективности применение явной рекурсии оказывается нежелательным. Следующий очевидный алгоритм реализует наиболее популярный симметричный обход без рекурсии, но с использованием стека.
Алгоритм 9.1. Алгоритм симметричного обхода бинарного дерева Вход: бинарное дерево, представленное списочной структурой, г — указатель на корень. Выход: последовательность узлов бинарного дерева в порядке симметричного обхода. Т: = я«; р: = г ( вначале стек пуст и р указывает на корень дерева ) М: ( анализирует узел, на который указывает р ) Е р = вй тйев Е Т = е ФЬеп асор ( обход закончен ) еп«( Е р»- Т ( левое поддерево обойдено ) у«еГ«« р ( очередной узел прн симметричном обходе ) р: = р, г ( начинаем обход правого поддерева ) Глава 9.
Деревья 246 еЬе р -+ Т ( запоминаем текущий узел... ) р: = рд ( ... н начинаем обход левого полдерева ) епг( К його М 9.4. Деревья сортировки В этом разделе обсуждается одно конкретное применение деревьев в программировании, а именно деревья сортировки. При этом рассматриваются как теоретические вопросы, связанные, например, с оценкой высоты деревьев, так и практическая реализация алгоритмов, а также целый ряд прагматических аспектов применения деревьев сортировки и некоторые смежные вопросы. 9.4.1. Ассоциативная память В практическом программировании для организации хранения данных и доступа к ним часто используется механизм, который обычно называют ассоциативной палгятью. При использовании ассоциативной памяти данные делятся на порции (называемые записями), и с каждой записью ассоциируется ключ. Ключ — это значение из некоторого вполне упорядоченного множества„а записи могут иметь произвольную природу и различные размеры.
Доступ к данным осуществляется по значению ключа, которое обычно выбирается простым, компактным и удобным для работы. Пример Ассоциативная память используется во многих областях жизни. 1. Толковый словарь или энциклопедия: записью является словарная статья, а ключом — заголовок словарной статьи (обычно его выделяют жирным шрифтом). 2. Адресная книга: ключом является имя абонента, а записью — адресная информация (телефон(ы), почтовый адрес и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
