ZU 4)                                                                           
                                                                                
PROGRAM INF84;                                                                  
                                                                                
TYPE TINFO=....;                                                                
     TZEIGER=^KNOTEN;                                                           
     KNOTEN=RECORD                                                              
             INFO:TINFO;                                                        
             L,R:TZEIGER                                                        
            END;                                                                
VAR  W:TZEIGER;                                     (*WURZEL DES BAUMES       *)
                                                                                
 PROCEDURE SWAPR(Q:TZEIGER);                        (*REKURSIV:               *)
  VAR H:TZEIGER;                                                                
                                                                                
 BEGIN                                                                          
  IF Q<>NIL THEN                                                                
     WITH Q^ DO                                                                 
      BEGIN                                                                     
       SWAPR(R);SWAPR(L);                           (*BEARBEITE TEILBAEUME    *)
       H:=R;R:=L;L:=H                               (*TAUSCHE DIE KNOTEN      *)
      END                                                                       
 END;(*SWAPR*)                                                                  
                                                                                
 PROCEDURE SWAPI(Q:TZEIGER);                        (*ITERATIV:               *)
  CONST MAXT=20;                                    (*MAXIMALE BAUMTIEFE      *)
  TYPE TWEG=(LINKS,RECHTS,ZURUECK);                                             
  VAR STACK=ARRAY[0..MAXT]OF RECORD                 (*STACK ZEICHNET DEN BIS- *)
                              Z:TZEIGER;            (*HERIGEN WEG DURCH DEN   *)
                              W:TWEG;               (*BAUM AUF                *)
                             END;                                               
      P:INTEGER;                                    (*STAPELZEIGER            *)
      H:TZEIGER;                                                                
      WEG:TWEG;                                     (*LFD. WEGRICHTUNG IM BAUM*)
                                                                                
  PROCEDURE PUSH(Z:TZEIGER;W:TWEG);                                             
  BEGIN STACK[P].Z:=Z;STACK[P].W:=W;P:=P+1 END;                                 
                                                                                
  PROCEDURE PULL(VAR Z:TZEIGER;VAR W:TWEG);                                     
  BEGIN P:=P-1;Z:=STACK[P].Z;W:=STACK[P] END;                                   
                                                                                
 BEGIN                                                                          
  P:=0;PUSH(NIL,LINKS);WEG:=LINKS;                  (*MARKE AUF DEN STACK     *)
  REPEAT                                                                        
   CASE WEG OF                                      (*GEHE VON Q IN RICHTUNG  *)
                                                    (*'WEG'                   *)
    LINKS   :IF Q^.L=NIL THEN WEG:=SUCC(WEG) ELSE   (*MERKE KNOTEN, RICHTUNG  *)
              BEGIN PUSH(Q,WEG);WEG:=LINKS END;     (*BEHANDELE NACHFOLGER,BE-*)
                                                                                
    RECHTS  :IF Q^.R=NIL THEN WEG:=SUCC(WEG) ELSE   (*GINNE MIT RICHTUNG LINKS*)
              BEGIN PUSH(Q,WEG);WEG:=LINKS END;     (*ANALOG FUER NACHFOLGER R*)
    ZURUECK :BEGIN                                                              
              H:=Q^.L;Q^.L:=Q^.R;Q^.R:=H;           (*TAUSCHE KNOTEN UND GEHE *)
              PULL(Q,WEG);WEG:=SUCC(WEG)            (*AUF GESPEICHERTEM WEG   *)
             END;                                   (*ZUM VORGAENGER ZURUECK  *)
   END;(*CASE*)                                                                 
  UNTIL Q=NIL                                       (*BIS RUECKKEHR VON DER   *)
 END;(*SWAPI*)                                      (*WURZEL DES BAUMES       *)
                                                                                
BEGIN                                                                           
 NEW(W);                                                                        
 (*BAUM AUFBAUEN*)                                                              
 SWAPR(W);                                                                      
 SWAPI(W);                                                                      
END.