Work ( q ); { процедура обработки дерева-О}
Recurs_Tree( q^.left );{уход по левой ветви-Л}
Recurs_Tree( q^.right );{уход по правой ветви-П}
End;
End;
{ обход дерева по варианту ЛОП }
Procedure Recurs_Tree ( q : nd );
Begin
If q <> nil
Then begin
Recurs_Tree( q^.left );{уход по левой ветви-Л}
Work ( q ); { процедура обработки дерева-О}
Recurs_Tree( q^.right );{уход по правой ветви-П}
End;
End;
{ обход дерева по варианту ЛПО }
Procedure Recurs_Tree ( q : nd );
Begin
If q <> nil
Then begin
Recurs_Tree( q^.left );{уход по левой ветви-Л}
Recurs_Tree( q^.right );{уход по правой ветви-П}
Work ( q ); { процедура обработки дерева-О}
End;
End;
Рекурсия в этой программе действует точно так же, как и в рекурсивных процедурах работы со списками: создается цепочка процедур, каждая из которых рекурсивно обращается к себе и затем ожидает завершения вызванной процедуры. Потенциально бесконечный процесс рекурсивного вызова останавливается с помощью «ограничителя рекурсии», в данном случае им становится нарушение условия ( q <> nil ), когда при обходе обнаруживается «нулевая» ссылка вместо реального адреса. При этом начинается последовательное завершение вызванных процедур с возвратом управления в вызывающую. Способ обхода меняется с изменением порядка обращений к процедурам.
Иллюстрация
