РАЗДЕЛ 2.3.2

1. Если В - пустое дерево, то F{B) - пустой лес. В противном случае лес F{B) состоит из дерева Т и леса F(npaBoe поддерево(В)), где корень(Т) = корень(В) и поддеревья(Т) = F(пoддepeвo(B)).

2. Количество нулей в двоичном формате представления деревьев соответствует количеству десятичных разделительных знаков в десятичной системе обозначений. Точная формула такого соответствия выглядит так:

ai.a2.---.ak ГОГ-О ... 01"«~\

где 1" обозначает а расположенных подряд единиц.

3. Рассортируем в лексикографическом порядке обозначения узлов в десятичной системе обозначений Дьюи (слева направо, как в словаре), размещая более короткую последовательность ai. - - - .ак перед ее расщирениями ai. - - .ак. - - .аг для прямого порядка обхода и после расширений - для обратного порядка обхода узлов. Таким образом, при сортировке C7I0B, а не последовательностей чисел, для прямого порядка обхода потребовалось бы разместить слова кат и катаракта в обычном порядке следования слов в словаре. А для получения обратного порядка обхода придется обратить исходное расположение слов: катаракта, кат. Эти правила легко доказать методом индукции по размеру дерева.

4. Да, справедливо, и это легко доказать методом индукции по количеству узлов дерева.

5. (а) Симметричный. (Ь) Обратный. Формулировка строгого доказательства эквивалентности этих алгоритмов обхода на основе метода индукции представляет собой довольно интересную задачу.

6. Прямой порядок обхода дерева Т = прямой порядок обхода дерева Т, обратный порядок обхода дерева Т = симметричный порядок обхода дерева Т, даже если Т имеет узлы только с одним ребенком. Остальные два порядка не имеют простой взаимосвязи, например корень дерева Т находится в конце в одном случае и приблизительно в середине - в другом случае.

7. (а) Да, (Ь) нет, (с) нет, (d) да. Обратите внимание, что порядок, реверсивный прямому порядку обхода леса, эквивалентен обратному порядку правопрошитого реверсивного леса (как при зеркальном отражении).

8. Т Ч Т означает, что либо info (корень(Т)) -< info (корень(Т)), либо информация, содержащаяся в корнях, эквивалентна и выполняется следующее условие: предположим, что Tl,..., Т„ являются поддеревьями корня дерева Т, а,Т[,... ,Т, - поддеревьями корня дерева Т, и допустим, что к > О такое максимально возможное, что Tj эквивалентно Т-для 1 < j < к. Тогда либо к = п, либо к < п и Tk+i < Tj.

9. В непустом лесу количество неконцевых узлов на один меньше количества правых связей, равных Л, потому что все пустые правые связи соответствуют крайнему справа ребенку каждого неконцевого узла, а также корню крайнего справа дерева в этом лесу. (На основании данного факта можно привести еще одно доказательство упр. 2.3.1-14, так как количество пустых левых связей, очевидно, равно количеству концевых уз.пов.)

10. Эти леса подобны тогда и только тогда, когда п = п п d{uj) = d{Uj) для 1 < i < п; они эквивалентны тогда и только тогда, когда, кроме того, info(wj) = info(Mj), 1 < i < п-Это доказательство выполняется аналогично предыдущему доказательству на основе обобщения леммы 2.3.IP, где следует допустить, что /(и) = d{u) - 1.

12. Если INFO(Ql) ф О, установить R к- COPY(Pl); если TYPE(P2) = О и INF0(P2) ф 2, установить R <- TREECt" ,TREE(INFO(Р2) - 1)); если TYPE(Р2) # О, установить R •(- TREECt" ,R, TREE("-",C0PY(P2),TREE(1))); затем установить Q1 4-MULT(Q1 ,MULT(C0PY(P2) ,R)).

Если INFO(Q) ф О, установить Q 4- TREECx" , MULT (TREE ("In" ,C0PY(P1)) ,Q) ,TREE("t" . C0PY(P1).C0PY(P2))).

Наконец, перейти к шагу DIFF [4] .

13. Приведенная ниже программа реализует алгоритм 2.3.1С с регистрами гИ = Р, г12 = Q, г13 = R и соответствующим образом изменяет условия инициализации и прекращения выполнения.

Сохранить содержимое регистров г13, rl2. Cl. Инициализация. Начать с создания узла NODE(U) с

RLINK(U) = Л. Нулевая константа инициализации. Установить Р 4- LLIM(P) = Р*. R AVAIL.

064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089 090 091 092 093 094

ST3 6F(0:2)

ST2 7F(0:2)

ENT2 8F

JMP IF 8H CON 0 4H LDI 0,1(LLINK) IH LD3 AVAIL

J3Z OVERFLOW

LDA 0,3(LLINK)

STA AVAIL

ST3 0,2(LLINK)

ENNA 0,2

STA 0,3(RLIMT)

INCA SB

ENT2 0,3

JAZ C3

C2 LDA JAN LD3 J3Z LDA STA LDA STA ST3

C3 LDA STA IDA STA

C4 LDA JANZ

0,1 C3

AVAIL OVERFLOW 0,3(LLINK) AVAIL

0,2(RLINKT) 0,3(RLINKT) 0.2(RLINKT) 1.1 1.2

0.1(TYPE) 0,2(TYPE) 0,1(LLINK) 4B

LLIM(Q) R.

RLINK (R) <- Q, RTAG(R) 1.

rA <- LOC(иcxoдный узел) - Q.

Установить Q «- R = Q*.

Перейти к шагу СЗ впервые.

С2. Есть ли узел справа?

Если RTAG(P) = 1, выполнить переход.

R <= AVAIL.

Установить RLINKT(R) <-RLINKT(Q). RLINK (Q) R, RTAG(Q) <- 0.

C3. Копирование данных, т. е. поля INFO. Поле INFO скопировано.

Поле TYPE скопировано. С4. Есть ли узел слева? Если LLINK (Р) ф Л, выполнить переход.

LLINK(Q) 4- Л.

C5. Продвинуться. Q (--RLINKT (Q).

P •(- RLIM(P).

Если RTAG(Q) равно 1, то совершить переход. Q <- -Q.

Сб. Проверка завершения.

rll <- адрес первого созданного узла.

Восстановить индексные регистры.

095 STZ 0,2(LLIM)

096 С5 LD2N 0,2(RLIMT)

097 LDl 0,1(RLINK)

098 J2P С5

099 ENN2 0,2

100 С6 J2NZ С2

101 LD1 8В(LLINK)

102 6Н ENT3 *

103 7Н ENT2 * I

14. Пусть а - количество скопированных неконцевых узлов (т. е. узлов с операторами). Попыток выполнения разных строк из предыдущей программы будет столько: 064-067, 1; 069, а; 070-079, а + 1; 080-081, п-1; 082-088, п - 1 - а; 089-094, п; 095, п - а; 096-098, п + 1; 099-100, п - а; 101-103, 1. Общее время равняется (Збп + 22)и, при этом около 20% времени уходит на поиск свободных узлов, около 40% - на обход и около 40% - на копирование данных из полей INFO и LIM.

15. Читателю предлагается в качестве упражнения самостоятельно изучить этот код.

16. Читателю предлагается в качестве упражнения самостоятельно изучить этот код.