Процедуры обхода дерева, использующие стек

Тип стека при нисходящем обходе.

Stack=^Zveno;

Zveno = record

next: Stack;

El: pointer;

end;

Процедура включения элемента в стек при нисходящем и смешанном обходе (Push_st) приведена в программном примере 6.10.

{ === Програмнный пример 6.10 ====}

Procedure Push_st (var st: stack; p: pointer);

Var

q: stack;

begin new(q); q^.el:=p; q^.next:=st; st:=q; end;

Функция извлечения элемента из стека при нисходящем и смешанном обходе (Pop_st) приведена в программном примере 6.11.

{ === Програмнный пример 6.11 ====}

Function Pop_st (var st: stack):pointer;

Var

e,p: stack

begin

Pop_st:=st^.el;

e:=st; { запоминаем указатель на текущую вершину }

st:=st^.next;{сдвигаем указатель стека на следующий элемент}

dispose(e); { возврат памяти в кучу }

end;

При восходящем обходе может быть предложен следующий тип стека:

point=^st;

st = record

next: point;

l: integer;

add: pointer;

end;

Процедура включения элемента в стек при восходящем обходе (S_Push) приведена в программном примере 6.12.

{ === Програмнный пример 6.12 ====}

Procedure S_Push (var st: point; Har: integer; add: pointer); Var q: point;

begin

new(q); { выделяем место для элемента }

q^.l:=Har; { заносим характеристику }

q^.add:=add; { заносим указатель }

q^.next:=st; { модифицируем стек }

st:=q;

end;

Функция извлечения элемента из стека при восходящем обходе (S_Pop) демонстрируется в программном примере 6.13.

{ === Програмнный пример 6.13 ====}

Function S_Pop (var st: point; var l: integer):pointer;

Var

e,p: point;

begin

l:=st^.l;

S_Pop:=st^.add;

e:=st; { запоминаем указатель на текущую вершину}

st:=st^.next; {сдвигаем указатель стека на след. элемент }

dispose(e); { уничтожаем выбранный элемент }

end;