Две другие программы DIV и PWR выглядят аналогично, и читателю предлагается самостоятельно создать их в качестве упражнения (см. упр. 15 и 16).

УПРАЖНЕНИЯ

► 1. [20] В Этом разделе приводилось формальное определение бинарного дерева B{F), соответствующего лесу F. Дайте формальное определение с обратным смыслом, т. е. определите лес F{B), который соответствует бинарному дереву В.

► 2. [20] Обозначение дерева в десятичной системе обозначений Дьюи дано в разделе 2.3, а обозначение бинарных деревьев - в упр. 2.3.1-5. Таким образом, узел "J" в (1) представлен в виде "2.2.1", а в эквивалентном бинарном дереве (3)-в виде "НОЮ". Если это возможно, предложите правило, которое непосредственно выражает естественное соответствие между деревьями и бинарными деревьями на основе десятичной системы обозначений Дьюи.

3. [22] Какая существует связь между десятичной системой обозначений Дьюи для узлов леса и прямым и обратным порядками обхода этих узлов?

4. [19] Справедливо ли следующее утверждение: "Концевые узлы дерева встречаются в одних и тех же относительных позициях при обходе как в прямом, так и в обратном порядках" ?

5. [23] Другое соответствие леса и бинарных деревьев можно определить с помощью RLINK (Р), который указывает на крайнего справа ребенка узла NODE(P), а также с помощью LLINK (Р), который указывает на крайнего слева ребенка узла. Пусть F является лесом, который, таким образом, соответствует бинарному дереву В. Какой порядок узлов бинарного дерева В соответствует (а) прямому и (Ь) обратному порядкам обхода леса F?

6. [25] Пусть Т является непустым бинарным деревом, в которо.м каждый узел имеет О или 2 детей. Если рассматривать Т как бинарное дерево, оно соответствует (на основе естественного соответствия) другому бинарно.му дереву Т. Существует ли какая-либо простая связь между прямым, симметричным и обратным порядками обхода узлов дерева Т (согласно их определениям для бинарных деревьев) и теми же порядками обхода узлов дерева Г?

7. [М20] Лес может рассматриваться как частично упорядоченный, если считать, что каждый узел дерева расположен перед его последователями. Можно ли утверждать, что узлы рассортированы в топологическом порядке (согласно определению в разделе 2.2.3), если они находятся: (а) в прямом порядке, (Ь) в обратном порядке, (с) в реверсивном прямому порядке и (d) в реверсивном обратному порядке?

8. [М20] В упр. 2.3.1-25 показано, как порядок следования данных в отдельных узлах бинарного дерева может быть расширюн до линейного упорядочения всех бинарных деревьев При наличии естественного соответствия аналогично можно получить упорядочение всех дерювьев. Переформулируйте данное в этом упражнении определение для деревьев.

9. [М21] Покажите, что существует простая связь между общим количеством неконцевых узлов леса и общим количеством правых связей, которые равны Л в соответствующем непрошитом бинарном дереве.

10. [М23] Пусть F - это лес деревьев, узлы которых упорядочены в прямом порядке обхода ui, U2,... , Ип, а F - лес деревьев, узлы которых упорядочены в прямом порядке обхода Tii, иг,..., . Введем обозначение d(u) для степени (количества детей) узла и. На основании этих понятий сформулируйте и докажите теорему, аналогичную теореме 2.3.1 А.

11. [15] Нарисуйте схему деревьев, аналогичную схеме (7), которая соответствует фор-муле у = е .

12. [М21] Предложите спецификации для программы DIFF[8] (операция "t"), которые опущены при описании алгоритма дифференцирования в данном разделе.

► 13. [26] Создайте для компьютера MIX подпрогра.мму COPY (которая в программе из данного раздела находится в строках 063-104). [Подсказка. Адаптируйте алгоритм 2.3.1С для правопрошитого бинарного дерева с соответствующи.ми начальными условиями ]

► 14. [М21] Сколько времени потребуется программе из упр 13 для копирования дерева с п узлами?

15. [2S] Создайте для компьютера MIX подпрограмму DIV, соответствующую DIFFC73. (Эта программа располагается в строке 217 описанной в разделе програ.ммы.)

16. [24] Создайте для компьютера MIX подпрограмму PWR, соответствующую DIFF[8] из упр. 12. (Эта программа распааагается после программы, приведенной в решении к упр. 15 )

17. [М4О] Создайте программу для упрощения алгебраических выражений, которая позволяет упростить, напри.мер, выражения (20) и (21) н привести их к виду (22). [Указание. Включите в каждый узел новое поле, которое представляет его коэффициент (для слагаемых) или степень (для сомножителей). Примените такие алгебраические тождества, как замена выражения ln(u f v) выражением vliiu сокращения операторов -, /, t и neg за счет выполнения эквивалентных и.м операций сложения и умножения тогда, когда это только возможно. Преобразуйте бинарные операторы "+" и "х" в п-арные. Приведите подобные члены, сортируя их операнды в древовидном порядке (упр. 8) Некоторые суммы и произведения сократятся до нуля или единицы, позволяя выполнить дальнейшие упрощения. Разумеется, что здесь следует использовать и другие упрощения, например сумму логарифмов можно заменить логарифмом произведения ]

► 18. [25] Ориентированное дерево, указанргое с помощью п связей PARENT[j] для 1 < j < п, неявно определяет упорядоченное дерево, если узлы в каждой семье упорядочены по адресам. Создайте эффективный алгоритм, который конструирует дважды связанный циклический список, содержащий узлы этого упорядоченного дерева в прямом порядке обхода. Например, при условии

j=12345678 PARENT[j] = 38404834 такой алгоритм позволяет получить

LLINKL;] = 38467215 RLINK[j] = 76138452

а также указать, что корневым является узел 4.

19. [Л55] Назовем свободной решеткой {free lattice) математическую систему, которая (в этом упражнении) может быть достаточно просто определена как множество формул, состоящих из переменны: и двух абстрактных бинарных операторов "V" и "Л". Отнощение "-Y > Y" определяется в свободной рещетке между некоторыми формулами X и¥ согласно cлeдJЮщим правилам:

i) XVY yW AZ тогда и только тогда, когда ЛVY >: W lumXVY У Z, шт X yWAZ, или YWaZ,

ii) X AY У Z тогда и только тогда, когда X >: Z itY У Z;

iii) X yY V Z тогда и только тогда, когда X УУ и X У Z;

iv) X yY А Z тогда и только тогда, когда х У¥ или х У Z, где х является переменной;

v) А V У г тогда и только тогда, когда X У z или Y У z, где z является переменной,

vi) X у у тогда и только тогда, когда х = у, где х и у являются переменными.

Например, находим о Л (Ь V с) У (о Л Ь) V (о Л с) о Л (Ь V с)

Создайте алгоритм, с помощью которого можно установить, выполняется ли отношение А >: У для двух заданных формул X hY в свободной решетке

► 20. [М22] Докажите, что если и и v-узлы леса, то узел и является предком узла t; тогда и только тогда, когда и располагается перед уз аом t; в прямом порядке обхода и и располшается за узлом t; в обратном порядке.

21. [25] Алгоритм D управляет процессом дифференцирования выражений с бинарными, унарными и нуль-арными операторами, которые могут быть представлены дерювьями с узлами со степенями 2, 1 и 0. Но в нем явным образом не укадан способ управления тернарными операторами и операторами с более высокой степенью. (Например, в упр. 17 предполагается, что операции сложения и л-множения выполняются для любого количества операндов.) Можно ли п1)едтожить достаточно простой способ расширения алгоритма D, чтобы его можно было применять для дифференцирования выражений с операторами, узлы которых и.меют степени выше 2?

► 22. [М26] Положим, дерево Т моо/сет быть вставлено в дерево Т, что обозначается как Т СТ, если существует такое взаимно однозначное отображение / узлов дерюва Т на узлы дерева Т, при котором сохраняются прямой и обратный порядки. (Иначе говоря, и предшествует t; при прямом порядке обхода дерева Т тогда и только тогда, когда узел f{u) предшествует узлу f{v) в прямом порядке обхода узлов дерева Т, причем то же самое верно и для обратного порядка обхода (рис. 25).)

Рис. 25. Пример одного дерева, вставленного в другое.

Если Г имеет более одного узла, допустим, что 1{Т) является крайним слева поддеревом корня дерева Г, а г(Г)-осга-чьной частью дерева Т, т. е. деревом Г без 1{Т).