PROGRAM suchbaum;

TYPE Baum = ^Knoten;

     Knoten = RECORD
                wert   : INTEGER;
                links  : Baum;
                rechts : Baum;
              END;

VAR b : Baum;

PROCEDURE preorder(b:Baum);
BEGIN
  IF b <> NIL THEN BEGIN
    write(b^.wert:3);
    preorder(b^.links);
    preorder(b^.rechts);
  END;
END;

PROCEDURE inorder(b:Baum);
BEGIN
  IF b <> NIL THEN BEGIN
    inorder(b^.links);
    write(b^.wert);
    inorder(b^.rechts);
  END;
END;

PROCEDURE postorder(b:Baum);
BEGIN
  IF b <> NIL THEN BEGIN
    postorder(b^.links);
    postorder(b^.rechts);
    write(b^.wert:3);
  END;
END;


FUNCTION maximum_auschneiden(VAR b:Baum) : Baum;  (* b <> NIL vorausgesetzt! *)
VAR ersatz: Baum;
BEGIN
  IF b^.rechts = NIL THEN BEGIN
    ersatz := b;
    b := b^.links;
    maximum_auschneiden := ersatz;
  END
  ELSE
    maximum_auschneiden := maximum_auschneiden(b^.rechts);
END;

PROCEDURE loeschen(x:INTEGER; VAR b:Baum);
VAR ersatz, opfer, temp : Baum;
BEGIN
  IF b <> NIL THEN
    IF x > b^.wert THEN
      loeschen(x,b^.rechts)
    ELSE IF x < b^.wert THEN
      loeschen(x,b^.links)
    ELSE BEGIN
      opfer := b;
      IF (b^.links = NIL) OR (b^.rechts = NIL) THEN
        IF b^.links = NIL THEN
          b := b^.rechts
        ELSE
          b := b^.links
      ELSE BEGIN
        b := maximum_auschneiden(b^.links);
        b^.links := opfer^.links;
        b^.rechts := opfer^.rechts;
      END;
      Dispose(opfer);
    END;
END;


BEGIN
  b := NIL;
END.