Д. Кнут - Искусство программирования том 1 (1119450), страница 96
Текст из файла (страница 96)
2.3.1 — 25 показано, как порядок следования данных в отдельных узлах бинарного дерева может быть расширен до линейного упорядочения всех бинарных деревьев При наличии естественного соответствия аналогично можно получить упорядочение всех деревьев. Переформулируйте данное в этом упражнении определение для деревьев. 9. [МЕХ] Покажите, что существует простая связь между общим количеством неконцевых узлов леса и общим количеством правых связей, которые равны Л в соответствующем непрошнтом бинарном дереве.
10. [МОЯ] Пусть Р— это лес деревьев, узлы которых упорядочены в прямом порядке обхода иы им, .., и„, а Р" — лес деревьев, узлы которых упорядочены в прямом порядке обхода и[, вэ,..., в'„. Введем обозначение 4(в) для степени (количества детей) узла и. На основании этих понятий сформулируйте н докажите теорему, аналогичную теореме 2.3.1А. 11. [15) Нарисуйте схему деревьев, аналогичную схеме (7), которая соответствует формулеу = е *. 12. [МО1] Предложите спецификации для программы 01РР(83 (операция "7"), которые опущены при описании алгоритма дифференцирования в данном разделе. ь 13. [20] Создайте для компьютера М1Х подпрограмму СОРУ (которая в программе из данного раздела находится в строках 063-104).
[Подсказка. Адаптируйте алгоритм 2.3.1С для правопрошитого бинарного дерева с соответствующими начальныл~и условиями ) ь 14. [МО!] Сколько времени потребуется программе из упр 13 лля копирования дерева с и узлами7 15. [ЕЗ] Создайте для компьютера М1Х подпрограмму ОТР, соответствующую 01РР(73.
(Эта программа располагается в строке 217 описанной в разделе программы.) 16. [04] Создайте для компьютера М1Х подпрограмму РКК, соответствующую 01РР[83 из упр. 12. (Эта программа располагается после программы, приведенной в решении к упр. 15 ) 17.
[М40] Создайте программу для упрощения алгебраических выражений, которая позволяет упростить, например, выражения (20) и (21) и привести их к виду (22). [Указание. Включите в каждый узел новое поле, которое представляет его коэффициент (для слагаемых) или степень (для сомножителей). Примените такие алгебраические тождества, как замена выражения (п(и 7 о) выражением г!пи сокращения операторов —, /, 7 и пеб за счет выполнения эквивалентных им операций сложения и умножения тогда, когда это только возможно. Преобразуйте бинарные операторы "+" и "х" в п-арные. Приведите подобные члены, сортируя их операнды в древовидном порядке (упр. 8) Некоторые суммы и произведения сократятся до нуля или единицы, позволяя выполнить дальнейшие упрощения.
Разумеется, что здесь следует использовать и другие упрощения, например сумму логарифмов можно заменить логарифмом произведения ) ь 18. [35] Ориентированное дерево, указанное с помощью и связей РХКЕИТ[1] для 1 < 1 < и, неявно определяет упорядоченное дерево, если узлы в каждой семье упорядочены по адресам, Создайте эффективный алгоритм, который конструирует дважды связанный циклический список. содержащий узлы этого упорядоченного дерева в прямом порядке обхода.
Например, при условии 1=12345678 РХКЕМТ[1] = 3 8 4 О 4 8 3 4 такой алгоритм позволяет получить ШЕЕ[1] = 3 8 4 6 7 2 1 5 811МК[1] = 7 6 1 3 8 4 5 2 а также указать, чго корневым является узел 4. 19. [Муб[ Назовем свободной решеткой (/гее 1абйсе) математическую систему, которая (в зтом упражнении) может быть достаточно просто определена как множество формул, состоящих из переменных и двух абстрактных бинарных операторов "Ч" и "Л". Отношение "Х >- У" определяется в свободной решетке между некоторыми формулами Х и У согласно следующим правилам: !) ХЧУ >- ИгЛЯ тогда и только тогда, когда ХЧУ г- Иг или ХЧУ >.
Я, или Х >. ИГЛЕ, или У >. Иг Л Я, й) Х Л У >. Х тогда и только тогда, когда Х ~ 2 и У >. Я; й1) Х >. 1' Ч 2 тогда и только тогда, когда Х ~ У и Х >. Я; ~т) х г У Л Я тогда н только тогда, когда х >. У или х )- 2, где х является переменной; т) Х Ч У ~. х тогда и только тогда, когда Х >- х или У с.
х, где х является переменной, з ~) х ь 9 тогда и только тогда, когда х = 9, где х и 9 являютгя переложенными. Например, находим а Л (Ь Ч с) ~ (а Л Ь) Ч (о Лс) ~ а Л (ЬЧс) Создайте алгоритм, с помощью которого можно установить, выполняется ли отноше- ние Х с 1" для двух заданных формул Х и 1' в свободной решетке ° 20. [Мйй] Докажите, что если и и с — узлы леса, то узел и является предком узла е тогда и только тогда, когда и располагается перед узлом е в прямом порядке обхода и и располагается за узлом с в обратном порядке.
21. [Йб) Алгоритм П управляет процессам дифференцирования выражений с бинарными, унарными и нуль-арными операторами, которые могут быть представлены деревьями с узлами со степенями 2, 1 и О. Но в нем явным образом не указан способ управления тернарными операторами и операторами с более высокой степенью. (Например, в упр. 17 предполагается, что операции сложения и умножения выполняются для любо! о количества операндов.) Можно ли предтожить достаточно простой способ расширения алгоритма гз, чтобы его можно было применять для дифференцирования выражений с операторами, узлы которых имеют степени вы~не 2? ° 22. [Мйб) Положим, дерево Т мелеет быть вставлено в дерево Т', что обозначается как Т С Т', егли существует такое взаимно однозначное отображение ) узлов дерева Т на узлы дерева Т', при котором сохраняются прямой и обратный порядки. (Иначе говоря, к предшествует е прн примом порядке обхода дерева Т тогда и только тогда, когда узел У(и) предшествует узлу )(и) в прямом порядке обхода узлов дерева Т', причем то же самое верно и для обратного порядка обхода (рис.
25).) Рис. 25. Пример одного дерева, вставленного в другое. Если Т имеет более одного узла, допустим, что 1(Т) является крайним слева под- деревом корня дерева Т, а г(Т) — остальной частью дерева Т, т. е. деревом Т без 1(Т). Докажите, что Т может быть вставлено в дерево Т', если (!) Т имеет только один узел яли (й) оба дерева Т и Т' имеГот более одного узла и либо Т С 1(Т'), либо Т С г(Т'), или (1(Т) С 1(Т') и г(Т) С г(Т~)).
Справедливо ли обратное утверждение? 2.3.3. Другие представления деревьев Кроме описанного в предыдущем разделе метода, основанного на указателях 1.1.1МК- й?.1МК (левый ребенок — правый брат (или сестра)), существует много других способов представления древовидных структур. Как обычно, наиболее подходящий способ в значительной мере зависит от типа операций, выполняелгых нгд этими деревьями. В данном разделе рассматривается несколько методов представления деревьев, которые на врактике доказали свою целесообразность. Сначала рассмотрим методы последоеагаельного распределения памяти. Как и в случае линейных списков, этот способ распределения наиболее удобен для компактного представления древовидной структуры, размер и форма которой во время выполнения программы не претерпевает значительных динамических изменений. Существует множество ситуаций, в которых для организации ссылок внутри программы необходимо использовать именно постоянные таблицы данных с древовидной структурой.
А необходимая форма этих деревьев в памяти компьютера зависит от способа доступа к данным из этой таблицы. Наиболее популярный тип последовательного представления деревьев (и лесов) соответствует устранению полей ШМК и использованию вместо ннх метода последовательной адресации. Рассмотрим, например, следующий лес. который уже упоминался в предыдущем разделе: Схематически его можно представить так; (2) При использовании последовапзельного предсгпаалгния а прямом порядке (ргеогдег гедчепба1 ггргегеп1амоп) узлы располагаются в прямом порядке с полями 1МРО, ШТМК и 1.?аС в каждом узле: АВСКРЕНЕ~~6 Ш1МК 1МРО ?.ТяС (3) Здесь непустые связи М1.1МК обозначены стрелками, а ?.ТаС = 1 (для концевых узлов) — символом ")".
Связи Ы.1МК не нужны, поскольку они либо пусты, либо указывают на следующий объект последовательности. Читателю будет полезно сравнпть (1) с (3). Это представление обладает сразу несколькими интересными свойгтвами. Вопервых, все поддеревья узла располагаются сразу за самим узлом, а потому все полдеревья внутри исходного леса находятся в последовательных блоках. (Сравните это с представлением на основе "вложенных скобок" в (1) и на рис.
20, (Ь).] Во-вторых, обратите внимание иа то, что стрелки связей МЬ1ИК на схеме (3) никогда не пересекаются. Это справедливо и в общем случае, так как в бинарном дереве все узлы, находящиеся между Х и М11ИК(Х), при прямом порядке обхода располагаются в левом поддереве Х, а потому из этой части дерева не выходят никакие стрелки. В-третьих, можно заметить, что поле 1.ТАС, которое указывает, будет ли узел концевым, является лишним, так как символ ")" располагается только в конце леса и только перед каждой направленной вниз стрелкой.
Действительно, из этих замечаний следует, что даже. поле Ж.1ИК также почти излишне и на самом деле для представления такой структуры необходимы поля ЕТАС и ЕТАС. Следовательно, схему (3) можно получить на основе меньшею объема данных: 1ИРО А В С К Р Е Й Е д С . (4) ЬТАС 1 1 ~ ! ! При считывании представления (4) слева направо узлы с полями МТАС ф "1" соответствуют непустым значениям й11ИК. Тогда для восстановления связей ЕЬ1ИК нужно каждый раз после прохождения узла с полем ЬТАС = ")" проводить связь к текущему узлу от ближайшего предшествующего узла с невосстановленной связью МЕ1ИК. (Например, после прохождения узла В с ЬТАС = ")" связь к текущему узлу С следует проводить от узла В. затем после прохождения узла К связь к текущему узлу Р необходимо проводить от узла .4 (поскольку связь й1.1МК в узле В уже восстановлена) и т.
д. — Прим. перев.) Следовательно, ячейки с невосстаиовленными, т. е. ненулевыми, значениями связей МЕ1ИК можно хранить в стеке. Таким образом, снова доказана теорема 2.3.1А. Тот факт, что поля И.1МК и 1.ТАС являются избыточными в представлении (3), не имеет большого значения, за исключением случая, когда нужно полностью выполнить последовательный обход всего дерева, поскольку для получения недостающей информации потребуются дополнительные вычисления. Значит, чаще всего нужны все данные представления (3). Однако очевидно, что при этом значительная часть памяти расходуется очень неэкономно, например в рассмотренном здесь частном примере леса больше половины полей МЕТИМ равны Л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
