Dispose(p)

End;

Функция проверки, является ли стек start пустым:

function Empty (start:Stack): boolean;

Begin

Empty:=start=nil

End;

Процедура префиксного обхода дерева:

procedure PrefOrd (T: Tree);

var start: Stack; flag: boolean;

Begin

start:=nil; { очистить стек }

flag:=true;

While flag do

Begin

{ операция обработки узла дерева, например, writeln(T^.inf);}

{ перейти к следующему узлу }

if T^.L <> nil then { есть левая ветвь }

Begin

{ если правая ветвь есть, то ссылку на нее добавить в стек }

if T^.R <> nil then Push(start,T^.R);

T:=T^.L { по левой ветви вниз }

End

Else

if T^.R <> nil then { есть правая ветвь }

T:=T^.R { по правой ветви вниз }

else { нет обеих ветвей }

Begin

if Empty(start) then { если стек пуст }

flag:=false { конец обхода }

else { извлечь ветвь из стека и идти по ней }

Pop(start,T)

End

end {while}

end; { PrefOrd }

Упражнение 3.1. Описать нерекурсивную процедуру

а) инфиксного обхода дерева;

б) постфиксного обхода дерева.

3.2 Обработка узлов дерева

Рассмотрим двоичное дерево, узлы которого содержат в информационной части целые числа. Назовем их элементами дерева.

Пример 3.5. Описать процедуру вывода дерева, выделяющую каждый уровень h с помощью соответствующего отступа.

procedure PrintTree(T: Tree; h: integer);

var i: integer;

Begin

if T <> nil then

Begin

PrintTree (T^.R, h+1);

for i:=1 to h do write(‘ ‘);

writeln(T^.inf);

PrintTree (T^.L, h+1);

End

end; { PrintTree }

Здесь используется не инфиксный обход, а обход справа налево, чтобы дерево не выдавалось в зеркальном отображении.

Так как корень дерева Root находится на нулевом уровне, то обращение к процедуре PrintTree будет иметь вид