PROGRAM BUILDTREE(INPUT,OUTPUT);                  
(* DEMONSTRATIONSPROGRAMM ZUR VERWENDUNG VON    *)
(* MEHREREN DYNAMISCHEN DATENSTRUKTUREN IN ZWEI *)
(* REKURSIVEN PROZEDUREN.                       *)
CONST CURSORBACK = 157;    (* CURSOR NACH LINKS *)
TYPE REF=^NODE;            (* DATENSTRUKTUR FUER*)
    NODE= RECORD           (* DEN BAUM          *)
            KEY: CHAR;                            
            L,R: REF                              
          END;                                    
                                                  
VAR N:    INTEGER;         (* ANZAHL DER KNOTEN *)
    ROOT: REF;             (* WURZEL DES BAUMES *)
                                                  
FUNCTION BTREE(N:INTEGER):REF;                    
(* ERZEUGE EINEN VOLLSTAENDIG AUSGEGLICHENEN    *)
(* BINAEREN BAUM MIT N KNOTEN. SPEICHERE IN     *)
(* JEDEM KNOTEN EIN EINZELNES ZEICHEN           *)
  VAR NEWNODE: REF; X: CHAR;                      
      NL, NR: INTEGER;                            
BEGIN                                             
 IF N=0 THEN BTREE:=NIL        (* BAUM IST LEER *)
 ELSE                                             
   BEGIN (* JE EINE HAELFTE LINKS UND RECHTS:   *)
     NL:= N DIV 2; NR:= N-NL-1;                   
     READ(X); NEW(NEWNODE);                       
     WITH NEWNODE^ DO                             
       BEGIN                                      
         KEY:=X; L:=BTREE(NL); R:=BTREE(NR)       
     END;                                         
     BTREE:=NEWNODE                               
   END                                            
END; (* BTREE *)                                  
                                                  
 PROCEDURE PRINTTREE(N:INTEGER;R:REF);            
 (*DRUCKT BAUM MIT N KNOTEN UND WURZEL R        *)
 (*QUELLE: ALGORITHMEN UND DATENSTRUKTUREN      *)
 (*        N. WIRTH                             *)
  CONST LWD=80;(*ZEILENBREITE DES DRUCKERS      *)
        KLN=3; (*ZEICHEN PRO SCHLUESSEL         *)
                                                  
  TYPE LINEPOSITION= 0..LWD;                      
       PREF =^PNODE;      (* LISTE ALLER KNOTEN *)
       PNODE=RECORD       (* IN JEDER DRUCKZEILE*)
               KEY:^NODE;                         
               POS:LINEPOSITION;                  
               LEFT,RIGHT,LINK:PREF               
             END;                                 
                                                  
  VAR CH:CHAR;                                    
      K :INTEGER;                                 
      ROOT,CURRENT,NEXT: PREF;                    
      Q,Q1,Q2: PREF;                              
      I: INTEGER;                                 
      LW,U,U1,U2,U3,U4: LINEPOSITION;             
                                                  
  FUNCTION TREE(Q:REF):PREF;                      
  (*BESTIMMT POSITION DER KNOTEN                *)
   VAR P:PREF;                                    
  BEGIN                                           
   IF Q=NIL THEN P:=NIL                           
   ELSE                                           
    BEGIN NEW(P);                                 
     P^.KEY:=Q;                                   
     P^.LEFT:=TREE(Q^.L);                         
     P^.POS:=INT((LW-KLN)*K/(N-1))+KLN DIV 2;     
     K:=K+1;                                      
     P^.RIGHT:=TREE(Q^.R)                         
    END;                                          
   TREE:=P                                        
  END; (* TREE *)                                 
                                                  
 PROCEDURE PRINT(C:CHAR);                         
 BEGIN WRITE(C);U:=U+1 END;                       
                                                  
 BEGIN (* PRINTTREE *)                            
  WRITELN("AUSGABE AUF DEN DRUCKER?");            
  WRITE("==>N",CHR(CURSORBACK));READLN(CH);       
  IF CH="J" THEN                                  
    BEGIN LW:=LWD;                                
     OPEN(OUTPUT,4,0);  (* AUSGABE UMLEITEN     *)
    END                                           
  ELSE LW:=RWINDOW(2);                            
  K:=0;ROOT:=TREE(R);                             
  CURRENT:=ROOT;ROOT^.LINK:=NIL;NEXT:=NIL;        
  WHILE CURRENT<>NIL DO                           
   BEGIN                                          
    (*ZUERST VERTIKALE LINIEN DRUCKEN:          *)
    FOR I:= 1 TO 3 DO                             
    BEGIN                                         
     U:=0;Q:=CURRENT;                             
     REPEAT                                       
      U1:=Q^.POS;                                 
      REPEAT PRINT(" ") UNTIL U=U1;               
      PRINT("Ý");Q:=Q^.LINK                       
     UNTIL Q=NIL;                                 
     WRITELN                                      
    END;                                          
    (*DRUCKE ZEILE MIT INFOS UND BILDE DIE LISTE*)
    (*DER NACHFOLGER (REIHENFOLGE!)             *)
    Q:=CURRENT;U:=0;                              
    REPEAT                                        
     (*ZENTRIEREN AUF Q^.POS                    *)
     U2:=Q^.POS-KLN DIV 2;U3:=U2+KLN;             
     Q1:=Q^.LEFT;Q2:=Q^.RIGHT;                    
     IF Q1=NIL THEN U1:=U2                        
     ELSE                                         
      BEGIN                                       
       U1:=Q1^.POS  ;Q1^.LINK:=NEXT;NEXT:=Q1      
      END;                                        
     IF Q2=NIL THEN U4:=U3                        
     ELSE                                         
      BEGIN                                       
       U4:=Q2^.POS+1;Q2^.LINK:=NEXT;NEXT:=Q2      
      END;                                        
     (*DRUCKE LINIEN UND SCHLUESSEL             *)
     WHILE U<U1 DO PRINT(" ");                    
     IF U<U2 THEN PRINT("°");                     
     WHILE U<U2 DO PRINT("À");                    
     (*EVTL. ANPASSEN:                          *)
     WRITE("(",Q^.KEY^.KEY,")");U:=U3;            
     WHILE U<U4-1 DO PRINT("À");                  
     IF U<U4 THEN PRINT("®");                     
     Q:=Q^.LINK                                   
    UNTIL Q=NIL;                                  
    WRITELN;                                      
    (*INVERTIERE NAECHSTE LISTE UND MACHE SIE   *)
    (*ZUR LAUFENDEN LISTE:                      *)
    CURRENT:=NIL;                                 
    WHILE NEXT<>NIL DO                            
     BEGIN                                        
      Q:=NEXT;NEXT:=Q^.LINK;                      
      Q^.LINK:=CURRENT;CURRENT:=Q                 
     END                                          
   END;                                           
  CLOSE(OUTPUT)                                   
 END; (* PRINTTREE *)                             
                                                  
BEGIN                                             
 WRITELN("DIESES PROGRAMM ERSTELLT EINEN VOLL-"); 
 WRITELN("STAENDIG AUSGEGLICHENEN  BINAERBAUM "); 
 WRITELN("UND GIBT DEN BAUM ANSCHLIESSEND     "); 
 WRITELN("FORMATIERT AUS.");                      
 WRITELN;                                         
 WRITELN("WIEVIELE KNOTEN HAT DER BAUM ?");       
 WRITE("===>8",CHR(CURSORBACK)); READLN(N);       
 WRITELN("GEBEN SIE JETZT BITTE",N," ZEICHEN");   
 WRITELN("EIN, DIE ZEICHENWEISE IM BAUM ABGE-");  
 WRITELN("LEGT WERDEN:");                         
 (* BAUM MIT ZEICHEN FUELLEN:   *)                
 ROOT:= BTREE(N);READLN;                          
 (* DRUCKE DEN BAUM FORMATIERT:*)                 
 PRINTTREE(N, ROOT);                              
END.