class BinaerBaum
{ Knoten wurzel = null;
  final int INORDER   = 1;
  final int PREORDER  = 2;
  final int POSTORDER = 3;

  boolean leer()
  { return (wurzel == null); }

  void fuegeEin(Knoten ast, int wert)
  { if (wert < ast.inhalt)
         { // links einfuegen
           if (ast.links == null)
                ast.links = new Knoten(wert, ast.stufe + 1);
           else fuegeEin(ast.links, wert);
         }
    else { // rechts einfuegen
           if (ast.rechts == null)
                ast.rechts = new Knoten(wert, ast.stufe+1);
           else fuegeEin(ast.rechts, wert);
         }
  } // fuegeEin

  void fuegeEin(int wert)
  { if (leer())
         wurzel = new Knoten(wert, 1);
    else fuegeEin(wurzel, wert);
  } // FuegeEin

  void drucke(int inhalt, int stufe)
  { for (int i = 1; i <= stufe; i++)
         Out.print("     ");
    Out.println(inhalt + "(" + stufe + ")");
  }

  void inOrderMitStufe(Knoten ast)
  { if (ast != null)
         { inOrderMitStufe (ast.rechts);
           drucke(ast.inhalt, ast.stufe);
           inOrderMitStufe (ast.links);
         }
  } // inOrderMitStufe

  void inOrderMitStufe()
  { inOrderMitStufe(wurzel);
  } // inOrderMitStufe

  void inOrder(Knoten ast)
  { if (ast != null)
         { inOrder (ast.links);
           Out.print(ast.inhalt + " ");
           inOrder (ast.rechts);
         }
  } // inOrder

  void preOrder(Knoten ast)
  { if (ast != null)
         { Out.print(ast.inhalt + " ");
           preOrder (ast.links);
           preOrder (ast.rechts);
         }
  } // preOrder

  void postOrder(Knoten ast)
  { if (ast != null)
         { postOrder (ast.links);
           postOrder (ast.rechts);
           Out.print(ast.inhalt + " ");
         }
  } // postOrder

  void laufeDurch(int order)
  { if      (order == INORDER)   inOrder(wurzel);
    else if (order == PREORDER)  preOrder(wurzel);
    else if (order == POSTORDER) postOrder(wurzel);
    else return; // falsche Angabe
  } // laufeDurch

  Knoten sucheErsatz(Knoten laufAst, Knoten zielAst)
  { if (laufAst.rechts != null)
         { laufAst.rechts = sucheErsatz(laufAst.rechts, zielAst); }
    else { // Groesstes Element im Teilbaum gefunden
           // Inhalt uebertragen
           zielAst.inhalt = laufAst.inhalt;
           // Linken Teilbaum anhaengen
           setzeStufe(laufAst.links, laufAst.stufe);
           laufAst = laufAst.links;
         }
    return laufAst;
  } // sucheErsatz

  Knoten loesche (Knoten ast, int wert)
  { if (ast == null) { return null; } // nichts zu tun

    if (wert < ast.inhalt)
         { ast.links = loesche(ast.links, wert);  }
    else if (wert > ast.inhalt)
         { ast.rechts = loesche(ast.rechts, wert); }
    else { // zu loeschender Knoten gefunden
           if (ast.rechts == null) // linken Ast anhaengen
                { setzeStufe(ast.links, ast.stufe);
                  ast = ast.links;
                }
           else if (ast.links == null) // links nichts, aber rechts
                { setzeStufe(ast.rechts, ast.stufe);
                  ast = ast.rechts;
                }
           else { // Knoten mitten drin; suche Maximum im linken
                  // Teilbaum.
                  ast.links = sucheErsatz(ast.links, ast);
                }
         } // Ende zu loeschender Knoten gefunden

    return ast;
  } // loesche

  void loesche(int wert)
  {  if (wurzel == null) return;
     else wurzel = loesche(wurzel, wert);
  } // loesche

  void setzeStufe(Knoten lauf, int neuStufe)
  { if (lauf != null)
    {    lauf.stufe = neuStufe;
         setzeStufe(lauf.links, neuStufe+1);
         setzeStufe(lauf.rechts, neuStufe+1);
    }
  }
  
  boolean gefunden(Knoten ast, int zahl)
  { if (ast == null) return false;
    else if (zahl == ast.inhalt) return true;
    else if (zahl < ast.inhalt) return gefunden(ast.links, zahl);
    else return gefunden(ast.rechts, zahl);
  } // gefunden

  boolean gefunden(int zahl)
  { return gefunden(wurzel, zahl);
  } // gefunden
} // class BinaerBaum