Главная Промышленная автоматика.

Рассмотрим определение прохождения двоичного дерева во внутреннем порядке, данное в разд. 2.4. При создании алгоритма, который присваивает узлам номера в соответствии с внутренним порядком, хорошо было бы отразить в нем определение прохождения во внутреннем порядке. Один из таких алгоритмов приведен ниже. Заметим, что он рекурсивно обращается к себе для нумерации поддерева.

Алгоритм 2.1. Нумерация узлов двоичного дерева в соответствии с внутренним порядком

Вход. Двоичное дерево, представленное массивами ЛЕВЫЙ-СЫН и ПРАВЫЙСЫН.

Выход. Массив, называемый НОМЕР, такой, что HOMEP[t] - номер узла i во внутреннем порядке.

Метод. Кроме массивов ЛЕВЫЙСЫН, ПРАВЫЙСЫН и НОМЕР, алгоритм использует глобальную переменную СЧЕТ, значение которой - номер очередного узла в соответствии с внутренним порядком. Начальным значением переменной СЧЕТ является 1. Параметр УЗЕЛ вначале равен корню. Процедура, изображенная на рис. 2.9, применяется рекурсивно.

Сам алгоритм таков:

begin

СЧЕТ - 1;

ВНУТПОРЯДОК(КОРЕНЬ) end □

Рекурсия дает несколько преимуществ и прежде всего простоту программ. Если бы приведенный выше алгоритм не был записан рекурсивно, надо было бы строить явный механизм для прохождения дерева. Двигаться вниз по дереву нетрудно, но чтобы обеспечить возможность вернуться к предку, надо запомнить всех предков в стеке, а операторы работы со стеком усложнили бы алгоритм.

procedure ВНУТПОРЯДОК(УЗЕЛ): begin

1. if ЛЕВЫЙСЫН[УЗЕЛ]0 then

ВНУТП0РЯД0К(ЛЕВЫЙСЫН1УЗЕЛ));

2. НОМЕР[УЗЕЛ]-СЧЕТ;

3. СЧЕТ-СЧЕТ+ 1;

4. if ПРАВЫЙСЫН[УЗЕЛ]0 then

ВНУТПОРЯДОК(ПРАВЫЙСЫНУЗЕЛ])

Рис. 2.9. Рекурсивная процедура для анугреннего порядка.



Вариант того же алгоритма, не содержащий рекурсии, мог бы быть таким:

Алгоритм 2.2. Вариант алгоритма 2.1 без рекурсии

Вход. Тот же, что у алгоритма 2.1. Выход. Тот же, что у алгоритма 2.1.

Метод. При прохождении дерева в стеке запоминаются все узлы, которые еще не были занумерованы и которые лежат на пути из корня в узел, рассматриваемый в данный момент. При переходе из узла V к его левому сыну узел v запоминается в стеке. После нахождения левого поддерева для v узел v нумеруется и выталкивается из стека. Затем нумеруется правое поддерево для у.

При переходе из и к его правому сыну узел v не помещается в стек, поскольку после нумерации правого поддерева мы не хотим возвращаться в у; более того, мы хотим вернуться к тому предку

begin СЧЕТ-н-1; УЗЕЛ*-КОРЕНЬ; СТЕК*-пустой; левый: while ЛЕВЫЙСЫН[УЗЕЛ] 0 do begin

затолкнуть УЗЕЛ в СТЕК; УЗЕЛ ЛЕВЫЙСЫН[УЗЕЛ] end;

центр: НОМЕР[УЗЕЛ1*-СЧЕТ; СЧЕТСЧЕТ+1; К ПРАВЫЙСЫН[УЗЕЛ[ then begin

УЗЕЛ ПРАВЫЙСЫН1УЗЕЛ]; goto левый

end;

if СТЕК не пуст then begin

УЗЕЛ <-элемент в вершине СТЕКа; вытолкнуть из СТЕКа; goto центр

Рис. 2.10. Алгоритм без рекурсии для внутреннего порядка.



узла V, который еще не занумерован (т. е. к ближайшему предку w узла V, такому, что v лежит в левом поддереве для w). Этот алгоритм приведен на рис. 2.10. □

Корректность варианта с рекурсией легко доказать индукцией по числу вершин в двоичном дереве. Корректность варианта без рекурсии также можно доказать, но здесь предположение индукции не столь прозрачно и возникают дополнительные трудности в связи с работой со стеком и правильным прохождением двоичного дерева. С другой стороны, платой за рекурсию может оказаться увеличение постоянных множителей у временной и емкостной сложностей.

Естественно выяснить теперь, как перевести алгоритмы с рекурсией в команды РАМ. В свете теоремы 1.2 достаточно рассмотреть построение РАСП-программы, так как рАсП можно моделировать с помощью РАМ с замедлением не более чем в постоянное число раз. Обсудим довольно прямолинейный способ реализации рекурсии. Он пригоден для всех программ, о которых идет речь в этой книге, но не охватывает всех случаев, которые могут встретиться.

В основе реализации процедуры о рекурсией лежит стек, где хранятся данные, участвующие во всех вызовах процедуры, при которых она еще не завершила свою работу. Иными словами, в стеке находятся все неглобальные данные. Стек разбит на фрагменты стека, представляющие собой блоки последовательных ячеек (регистров). Каждый вызов процедуры использует фрагмент стека, длина которого зависит от вызываемой процедуры.

Пусть сейчас выполняется процедура А, а стек выглядит, как на рис. 2.11. Если А вызывает процедуру В, происходит следующее:

1. В вершину стека помещае1х:я фрагмент стека нужного размера. В него входят в порядке, известном процедуре В,

(а) указатели фактических параметров этого вызова процедуры

(б) пустое место для локальных переменных, участвующих в процедуре В,

(в) адрес РАСП-команды в подпрограмме А, которую следует выполнить после того, как данный вызов В кончит работу (адрес возврата) ). Если В - функция, вырабатывающая некоторое значение, то во фрагмент стека для В также помещается указатель ячейки во фрагменте стека для А, в которую надлежит поместить это значение (адрес значения).

1) Если фактическим параметром является выражение, го его значение вычисляется во фрагменте стека процедуры А, а указатель помещается во фрагмент для В. Если фактическим параметром является структура (например, массив), то достаточно будет указателя на ее первое слово.

Мы берем здесь РАСП в качестве модели именно из-за этих скачков к адресам возврата, доставляющих нам неудобства (хотя, конечно, преодолимые) при использовании РАМ.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 [20] 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021