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

ПРОЦЕДУРЫ ОБХОДА ДЕРЕВА, ИСПОЛЬЗУЮЩИЕ СТЕК.

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

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;