PROGRAM KUNDENBAUM (INPUT, OUTPUT);                         
(* VERWALTUNG DER KUNDENDATEN IN EINEM NACH NAMEN         *)
(* GEORDNETEN BINAERBAUM.                                 *)
                                                            
  CONST LEN = 10;               (* LAENGE EINES NAMENS    *)
                                                            
  TYPE STRING = STRING[LEN];                                
       KUNDENZEIGER = ^ KUNDE;                              
       KUNDE  = RECORD                                      
                  NAME     : STRING;                        
                  KNUMMER  : INTEGER;                       
                  L, R     : KUNDENZEIGER;                  
                END;                                        
                                                            
  VAR WURZEL: KUNDENZEIGER;     (* WURZEL DES BAUMES      *)
      CH    : CHAR;             (* FUNKTIONS-AUSWAHL      *)
                                                            
  PROCEDURE DRUCKE(Z: KUNDENZEIGER);                        
  (* DRUCKE DEN INHALT DES REFERENZIERTEN RECORDS         *)
  BEGIN                                                     
   WITH Z^ DO                                               
     WRITELN("NAME:",NAME:LEN+2,"  NUMMER:",KNUMMER:5)      
  END; (* DRUCKE *)                                         
                                                            
  PROCEDURE EINGABE;                                        
  (* EINGABE EINES NEUEN KUNDENRECORDS                    *)
    VAR K: KUNDE;                                           
                                                            
    PROCEDURE EINFUEGEN(NEU:KUNDE; VAR Z:KUNDENZEIGER);     
    (* FUEGE NEU AN DER KORREKTEN POSITION IM TEILBAUM MIT*)
    (* DER WURZEL Z EIN.                                  *)
    BEGIN                                                   
      IF Z=NIL THEN           (* TEILBAUM IST LEER:       *)
        BEGIN                 (* FUEGE NEU ALS BLATT EIN  *)
          NEW(Z);Z^:= NEU;    (* BELEGE Z^ MIT NAME  UND  *)
          Z^.L:= NIL;         (* KUNDENNUMMER. Z^ HAT     *)
          Z^.R:= NIL          (* KEINE NACHFOLGER !       *)
        END                                                 
      ELSE                                                  
        BEGIN                 (* VERGLEICH DER SCHLUESSEL:*)
          IF NEU.NAME=Z^.NAME THEN                          
            WRITELN(NEU.NAME," IST BEREITS KUNDE!")         
          ELSE                                              
            IF NEU.NAME<Z^.NAME THEN                        
              EINFUEGEN(NEU,Z^.L) (* IM LINKEN  ODER      *)
            ELSE                                            
              EINFUEGEN(NEU,Z^.R) (* IM RECHTEN TEILBAUM  *)
        END                       (* EINFUEGEN            *)
    END; (* EINFUEGEN *)                                    
                                                            
  BEGIN  (* EINGABE *)                                      
    WRITE("NAME:"); READLN(K.NAME);                         
    WRITE("KUNDENNUMMER:"); READLN(K.KNUMMER);              
    EINFUEGEN(K, WURZEL);     (* K IM BAUM EINFUEGEN      *)
  END; (* EINGABE *)                                        
                                                            
  PROCEDURE INORDER(Z: KUNDENZEIGER);                       
  (* DRUCKE IN ALPHABETISCHER REIHENFOLGE DIE KNOTEN DES  *)
  (* TEILBAUMES MIT WURZEL Z.                             *)
  BEGIN                                                     
    IF Z<>NIL THEN            (* TEILBAUM IST NICHT LEER: *)
      BEGIN                                                 
        INORDER(Z^.L);        (* DRUCKE LINKEN TEILBAUM   *)
        DRUCKE (Z);           (* DIE WURZEL SELBST UND    *)
        INORDER(Z^.R)         (* DANN DEN RECHTEN TEILBAUM*)
      END                                                   
  END; (* TABELLE *)                                        
                                                            
  PROCEDURE LOESCHE;                                        
    VAR NAME: STRING;                                       
                                                            
    PROCEDURE ENTFERNE(N: STRING; VAR Z: KUNDENZEIGER);     
    (* ENTFERNE DEN KUNDEN MIT NAME N AUS DEM TEILBAUM    *)
    (* MIT DER WURZEL Z                                   *)
                                                            
      PROCEDURE HOLEHOCH(VAR Z1: KUNDENZEIGER);             
      (* ERSETZE Z DURCH DEN GROESSTEN WERT IM LINKEN     *)
      (* TEILBAUM Z^L                                     *)
      BEGIN                                                 
        IF Z1^.R=NIL THEN                                   
          BEGIN               (* KOPIERE FELDER NACH Z^   *)
            Z^.NAME   := Z1^.NAME;                          
            Z^.KNUMMER:= Z1^.KNUMMER;                       
            Z1:=Z1^.L         (* ERSETZE Z1 DURCH SEINEN  *)
                              (* LINKEN NACHFOLGER        *)
          END                                               
        ELSE                  (* RECHTS WEITERSUCHEN:     *)
          HOLEHOCH(Z1^.R)                                   
      END; (* HOLEHOCH *)                                   
                                                            
    BEGIN  (* ENTFERNE *)                                   
      IF Z=NIL THEN                                         
        WRITELN(N," IST NICHT GESPEICHERT!")                
      ELSE                                                  
        IF N=Z^.NAME THEN     (* ERSETZE Z DURCH EINEN    *)
          BEGIN               (* SEINER NACHFOLGER        *)
            IF Z^.L= NIL THEN Z:=Z^.R ELSE                  
            IF Z^.R= NIL THEN Z:=Z^.L                       
            ELSE  HOLEHOCH(Z^.L)                            
          END                                               
        ELSE                  (* SUCHE IN DEN TEILBAEUMEN *)
          IF N<Z^.NAME THEN ENTFERNE(N,Z^.L)                
                       ELSE ENTFERNE(N,Z^.R)                
    END;(* ENTFERNE *)                                      
                                                            
  BEGIN (* LOESCHE *)                                       
    WRITE("NAME:"); READLN(NAME);                           
    ENTFERNE(NAME,WURZEL)     (* LOESCHE KUNDEN IM BAUM   *)
  END; (* LOESCHE *)                                        
                                                            
BEGIN (* HAUPTPROGRAMM *)                                   
  WURZEL:= NIL;               (* BAUM IST LEER            *)
  REPEAT                      (* EINGABESCHLEIFE          *)
    WRITELN("T ABELLE");                                    
    WRITELN("E RWEITERN");                                  
    WRITELN("L OESCHEN");                                   
    WRITELN("X BEENDEN");                                   
    READLN(CH);                                             
    CASE CH OF                                              
      "T": INORDER(WURZEL);   (* DRUCKE GESAMTEN BAUM     *)
      "E": EINGABE;                                         
      "L": LOESCHE;                                         
      "X": ;                                                
     ELSE WRITELN("UNGUELTIGE WAHL")                        
    END;                                                    
  UNTIL CH="X";                                             
END.