PROGRAM baum(input,output,eingabe);

{ Uebernimmt aus einer Eingabedatei ganzzahlige Datenwerte, sortiert sie in }
{ einen binaeren Baum und schreibt sie dann sortiert wieder in die Datei.   }

{.pl71}

{$B-}

{$A-}

TYPE baumzgr = ^binbaum;
     binbaum = RECORD
                 daten  : integer;
                 rechts : baumzgr;
                 links  : baumzgr
               END;
     stapelzgr     = ^stapelelement;
     stapelelement = RECORD
                       bzgr  : baumzgr;
                       stzgr : stapelzgr
                     END;

VAR eingabe           : text;
    wurzel, knoten, p : baumzgr;
    spitze            : stapelzgr;

{-----------------------------------------------------------------------------}

PROCEDURE machknoten;

{ Liest eine ganze Zahl aus der EINGABE-Datei und erzeugt einen neuen, }
{ voll initialisierten, Knoten.                                        }

BEGIN { machknoten }
  new (knoten);
  knoten^.rechts := NIL;
  knoten^.links  := NIL;
  IF eof (eingabe)
    THEN
      knoten^.daten := 0
    ELSE
      readln (eingabe, knoten^.daten)
END;  { machknoten }

{-----------------------------------------------------------------------------}

PROCEDURE machbaum (anfang : baumzgr);

VAR p,q : baumzgr;

BEGIN { machbaum }
  p := anfang;
  q := anfang;
  IF knoten^.daten < q^.daten
    THEN                     { im linken Zweig suchen }
      BEGIN
        p := q^.links;
        IF p = NIL
          THEN               { an leeren linken Zweig anfuegen }
            q^.links := knoten
          ELSE               { weitersuchen }
            machbaum (p)
      END
    ELSE                     { im rechten Zweig suchen }
      BEGIN
        p := q^.rechts;
        IF p = NIL
          THEN               { an leeren rechten Zweig anfuegen }
            q^.rechts := knoten
          ELSE               { weitersuchen }
            machbaum (p)
      END
END;  { machbaum }

{-----------------------------------------------------------------------------}

PROCEDURE baumdrucken;

{ Uebernimmt die Knoten in geordneter Folge und schreibt sie auf die Datei. }

VAR stapel : stapelzgr;

BEGIN { baumdrucken }
  WHILE p <> NIL DO
    BEGIN                    { nach links durcharbeiten }
      new (stapel);
      stapel^.bzgr := p;
      stapel^.stzgr := spitze;
      spitze := stapel;
      p := p^.links
    END;
  IF spitze <> NIL
    THEN                     { ausschreiben und nach rechts gehen }
      BEGIN
        p := spitze^.bzgr;
        spitze := spitze^.stzgr;
        writeln (eingabe, p^.daten);
        p := p^.rechts;
        baumdrucken
      END
END;  { baumdrucken }

{-----------------------------------------------------------------------------}

BEGIN { baum }
  assign (eingabe, 'eingabe.dat');
  {$I-}
  reset (eingabe);
  {$I+}
  machknoten;
  wurzel := knoten;
  machknoten;
  WHILE knoten^.daten <> 0 DO  { Daten = 0 bezeichnet dad Ende }
    BEGIN                      { Baum aufbauen }
      machbaum (wurzel);
      machknoten
    END;
  rewrite (eingabe);
  spitze := NIL;
  p := wurzel;
  baumdrucken;
  close (eingabe)
END.  { baum }