AOP_Tom1 (1021736), страница 98
Текст из файла (страница 98)
[22] Какая существует связь между десятичной системой обозначений дьюи для узлов леса и прямым и обратным порядками обхода этих узлов? 4. [19) Справедлива ли следующее утверждение: "Концевые узлы дерева встречаются в одних и тех же относительных позициях при обходе как в прямом, так и в обратном порядках"? б. [22) Другое соответствие леса и бинарных деревьев можно определить с помощью И.ТИК(Р), который указывает на крайнего справа ребенка узла ИООЕ(Р), а также с помощью ШИК(Р), который указывает на крайнего слева ребенка узла. Пусть Р является лесом, который, таким образом, соответствует бинарному дереву В.
Какой порядок узлов бинарного дерева В соответствует (а) прямому и (Ь) обратному порядкам обхода леса Р'? 6. [25] Пусть Т является непустым бинарным деревом, в катарам каждый узел имеет 0 или 2 детей. Если рассматривать Т как бинарное дерево, оно соответствует (на основе естественного соответствия) другому бинарному дереву Т'. Существует ли какая-либо простая связь между прямым, симметричным и обратным порядками обхода узлов дерева Т (согласно их определениям для бинарных деревьев) и теми же порядками обхода узлов дерева Т'? 7. [М20) Лес может рассматриваться как частично упорядоченный, если считать, что каждый узел дерева расположен перед его последователями.
Можно ли утверждать, что узлы рассортированы в топалагическом порядке (согласно определению в разделе 2.2.3), если они находятся: (а) в прямом порядке, (Ь) в обратном порядке, (с) в реверсивном прямому порядке и (д) в реверсивном обратному порядке? 20б 207 202 209 2Н 210 211 212 212 1Н 2Ц 215 21б 8Н 217 9Н БТ1 *+2(0:г) ЕИТ1 0,2 ЕИТ2 ь 1.РА АЧА П. БТА 0,2(ШИК) БТ2 АЧА11. ЛИР 8Р ЕИТА Т1МЕБ ЕИТХ 0,2 ЛНР ТЕЕЕ2 ЕИТ2 э 3МР 8. [М80] В упр. 2.3.1 — 25 показано, как порядок следования данных в отдельных узлах бинарного дерева может быть расширен до линейного упорядочения всех бинарных деревьев При наличии естественного соответствия аналогично можно получить упорядочение всех деревьев. Переформулируйте данное в этом упражнении определение для деревьев. 9.
[МЕХ] Покажите, что существует простая связь между общим количеством неконцевых узлов леса и общим количеством правых связей, которые равны Л в соответствующем непрошитом бинарном дереве. 10. [МЯЯ] Пусть à — это лес деревьев, узлы которых упорядочены в прямом порядке обхода иы иг,..., и„, а Р" — лес деревьев, узлы которых упорядочены в прямом порядке обхода им и~э,..., и'„. Введем обозначение 4(и) для степени (количества детей) узла и. На основании этих понятий сформулируйте и докажите теорему, аналогичную теореме 2.3.1А, 11. [15] Нарисуйте схему деревьев, аналогичную схеме (7), которая соответствует фор- 2 муле у = е 12.
[МЯ1] Предложите спецификации для программы О1РР[8) (операция "7"), которые опущены при описании алгоритма дифференцирования в данном разделе. ь 13. [20] Создайте для компьютера И1Х подпрограмму СОРТ (которая в программе из данного раздела находится в строках Об3-104). ~Подсказка. Адаптируйте алгоритм 2.3.1С для правопрошитого бинарного дерева с соответствующими начальными условиями ] ь 14.
[М21] Сколько времени потребуется программе из упр 13 для копирования дерева с и узлами? 15. [ЕУ] Создайте для компьютера И1Х подпрограмму О17, соответствующую О1РР[7). (Эта программа располагается в строке 217 описанной в разделе программы.) 16. [24] Создайте для компьютера ИХХ подпрограмму РИК, соответств1чзщую О1РР(8) из упр.
12. (Эта программа располагается после программы, приведенной в решении к упр. 15 ) 17. [М40] Создайте программу для упрощения алгебраических выражений, которая позволяет упростить, например, выражения (20) и (21) и привести их к виду (22). [Указание. Включите в каждый узел новое поде, которое представляет его коэффициент (для слагаемых) или степень (для сомножителей). Примените такие алгебраические тождества, как замена выражения )п(и 7 е) выражением г Ига сокращения операторов —, /, 7 и пеб за счет выполнения эквивалентных им операций сложения и умножения тогда, когда это только возможно.
Преобразуйте бинарные операторы "+" и "х" в и-арные. Приведите подобные члены, сортируя их операнда~ в древовидном порядке (упр. 8) Некоторые суммы и произведения сократятся до нуля или единицы, позволяя выполнить дальнейшие упрощения. Разумеется, что здесь следует использовать и другие упрощения, например сумму логарифмов можно заменить логарифмам произведения ] ь 18.
[25] Ориентированное дерево, указанное с помощью и связей РАКЕИТ[7] для 1 < 1 < и, неявно определяет упорядоченное дерево, если узлы в каждой семье упорядочены по адресам. Создайте эффективный алгоритм, который конструирует дважды связанный циклический список, содержащий узлы этого упорядоченного дерева в прямом порядке обхода. Например, при условии 1=12345б78 РАКЕИТ[1] = 3 8 4 О 4 8 3 4 такай алгоритм позволяет получить АИКЦ = 3 8 4 б 7 2 1 5 И.1ИК[1] = 7 б 1 3 8 4 5 2 а также указать, что корневым является узел 4.
19. [МЯЬ[ Назовем свободной решепзкой (/гее (азйге) математическую систему, которая (в зтом упражнении) может быть достаточно просто определена как множество формул, состоящих из перемен нык и двух абстрактных бинарных операторов "Ч" и "Л". Отношение "Х > У" определяется в свободной решетке межлу некоторыми формулами Х и У согласно следующим правилала !) ХЧ1 г И Лг тогда и толька тогда, когда ХЧУ )- И' или ХЧ1 ~ г, Х ~ И ЛЯ, У~-1 лг. и) Х Л 1 г. Е тогда и только тогда, когда Х г.
Я и 1' 'г. Я; й1) Х >. 1' Ч Я тогда и только тогда, когда Х > 1' и Х >- Я; (т) х >. У Л Я тогда и только тогда, когда х ~ У или х >. Я, где х является переменной; т) Х Ч У >" х тогда и только тогда, когда Х >. х или У >. х, где х является переменной, зт) х >- у тогда и только тогда, когда х = у, где х и у являются переменными. Например, находим а Л (ЬЧ с) ~ (а Л Ь) Ч(а Л с) ~ а Л (ЬЧ с) Создайте алгоритм, с помощью которого можно установить, выполняется ли отноше- ние Х ~ 1 для двух заданных формул Х и У в свободной решетке ь 20. [Мак[ Докажите, что если и и о — узлы леса, то узел и является предком узла в тогда и только тогда, когда и располагается перед узлом в в прямом порядке обхода и и располагается за узлом о в обратном порядке.
21. [л5] Алгоритм О управляет процессом дифференцирования выражений с бинарными, унарными и нуль-ариыми операторами, которые могут быть представлены деревьями с узлами со степенями 2, 1 и б. Но в нем явным образом не указан способ управления тернарными операторами и операторами с более высокой степенью. (Например, в упр. 17 предполагается, что операции сложения и умножения выполняются для любгко количества операндов.) Можно ли предтожить достаточно простой способ расширения алгоритма П, чтобы его можно было применять для дифференцирования выражений с операторами, узлы которых имек>т степени выше 2? ь 22. [МЯб[ Положим, дерево Т может Ьмгль всшаолено в дерево Т', что обозначается как Т С Т', если существует такое взаимна однозначное отображение 7' узлов дерева Т на узлы дерева Т', при котором сохраняются прямой и обратный порядки.
(Иначе говоря, н предшествует е при прямом порядке обхода дерева Т тогда и только тогда, когда узел /(и) предшествует узлу 7(о) в прямом порядке обхода узлов дерева Т, причем то же самое верна и для обратного порядка обхода (рис. 2Ь).) Рис. 25. Пример одного дерева, вставленного в другое. Если Т имеет более одного узла, допустим, что ((Т) является крайним слева под- деревом корня дерева Т, а г(Т) — остальной частью дерева Т, т. е. деревом Т без ((Т). Докажите, что Т может быть вгтавлеио в дерево Т', если (Г) Т имеет только один узел или (й) оба дерева Т и Т' имеют более одного узла и либо Т С ЦТ'), либо Т С г(Т'), или (1(Т) С 1(Т') и г(Т) С г(Т')). Справедливо ли обратное утверждение? 2.3.3.
Другие представления деревьев Кроме описанного в предыдущем разделе метода, основанного на указателях 1.1,1МК- й?.1МК (левый ребенок — правый брат (или сестра)), существует много других способов представления древовидных структур. Как обычно, наиболее подходящий способ в значительной мере зависит от типа операций, выполняемых над этими деревьями. В данном разделе рассматривается несколько методов предгтавления деревьев, которые на практике доказали свою целесообразность. Сначала рассмотрим методы последовательного распределения памяти. Как и в случае линейных списков, этот способ распределения наиболее удобен для компактного представления древовидной структуры„размер и форма которой во время выполнения программы не претерпевает значительных динамических изменений.
Существует множество ситуаций, в которых для организации ссылок внутри программы необходимо использовать именно постоянные таблицы данных с древовидной структурой. А необходимая форма этих деревьев в памяти компьютера зависит от способа доступа к данным из этой таблицы. Наиболее популярный тип последовательного представления деревьев (и лесов) соответствует устранению полей 1.1.1МК и использованию вместо них метода последовательной адресации. Рассмотрим, например, следующий лгс. который уже упоминался в предыдущем разделе: Схематически его можно представить так; (2) При использовании последовательного представления а прямом порядке (ргеогдег эеааепба! Гсргеэепгапап) узлы располагаются в прямом порядке с полями 1МР0, йьХМК и Г.ТА0 в каждом узле: à — — ~ А В С К Р Е Н г' ~~6' йй1МК 1Мг0 Г.ТАС (3) Здесь непустые связи И.1МК обозначены стрелками, а 1.ТАС = 1 (для концевых узлов) — символом ")".
Связи 1.1.1МК не нужны, поскольку оии либо пусты, либо у.казывают на следующий объект последовательности. Читателю будет полезно сравнить (1) с (3). Это представление обладает сразу несколькими интересными свойгтвами. Вопервых, все поддгревья узла располагаются сразу за самим узлом, а потому все поддеревья внутри исходного леса находятся в последовательных блоках. (Сравните это с представлением на основе "вложенных скобок" в (1) и на рис. 20, (Ь).] Во-вторых, обратите внимание на то, что стрелки связей ЕЕ1ИК на схеме (3) никогда не пересекаются.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
