4. способы повышения эффективности алгоритмов

begin
COT  1;
INOR (RT);
end
Рекурсия дает несколько преимуществ и прежде всего простоту программ. Если бы приведенный выше алгоритм не был записан рекурсивно, надо было бы строить явный механизм для прохождения дерева. Двигаться вниз по дереву нетрудно, но чтобы обеспечить возможность вернуться к предку, надо запомнить всех предков в стеке, а операторы работы со стеком усложнили бы алгоритм.

а) б)
Рис.4.1. СА с рекурсией для внутреннего порядка:

а - собственно алгоритм; б - процедура INOR.


procedure INOR (ND)
begin
if LES[ND]  0 then INOR (LES[ND]);
NUM[ND]  COT;
COT  COT + 1;
if RIS[ND]  0 then INOR (RIS[ND])
end

Рассмотрим возможный вариант того же алгоритма, но без использования рекурсии.

Алгоритм 4.2. Вариант алгоритма 4.1. без рекурсии.
ВХОД. Тот же, что и у алгоритма 4.1.
ВЫХОД. Тот же, что и у алгоритма 4.1.
МЕТОД. При прохождении дерева в стеке запоминаются все узлы, которые еще не были занумерованы и которые лежат на пути из корня в узел, рассматриваемый в данный момент. При переходе из узла v к его левому сыну узел v запоминается в стеке. После нахождения левого поддерева для v узел v нумеруется и выталкивается из стека. Затем нумеруется правое поддерево для v.
При переходе из v к его правому сыну узел v не помещается в стек, поскольку после нумерации правого поддерева мы не должны возвращаться в v, а должны вернуться к тому предку узла v, который еще не занумерован (т.е. к ближайшему предку w узла v такому, что v лежит в левом поддереве для w). Этот алгоритм приведен на рис. 4.2.


begin
COT  1 ;
ND  RT;
STK  0 ;
L : while LES[ND]  0 do
begin
PUSH; (* затолкнуть узел в стек *)
ND  LES[ND]