class Knoten  // --------------------------------------
{  int inhalt;
   Knoten links;
   Knoten rechts;
   Knoten(int wert)
   { this.inhalt = wert;
     this.links  = null;
     this.rechts = null;
   }
} // class Knoten


class BinaerBaum // -----------------------------------
{
  Knoten wurzel = null;


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


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


  void FuegeEin (int wert)
  { if (wurzel == null)
         wurzel = new Knoten(wert);
    else rekFuegeEin(wurzel, wert);
  } // FuegeEin


  void rekLaufeDurch (Knoten ast)
  { if (ast != null)
         { rekLaufeDurch (ast.links);
           Out.print(ast.inhalt); Out.println();
           rekLaufeDurch (ast.rechts);
         }
  } // rekLaufeDurch


  void laufeDurch ()
  { if (wurzel != null)
         { rekLaufeDurch (wurzel.links);
           Out.print(wurzel.inhalt); Out.println();
           rekLaufeDurch (wurzel.rechts);
         }
  } // 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
           laufAst = laufAst.links;
         }
    return laufAst;
  } // sucheErsatz


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

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

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

} // class BinaerBaum


class BinaerBaumLoeschBsp // ----------------------------
{
  static BinaerBaum baum;


  public static void main(String[] arg)
  { int zahl = 0;
    String muell;
    baum = new BinaerBaum();
    Out.print("Bitte Zahlen eingeben. Ende mit -1."); Out.println();
    while (zahl != -1)
    { Out.print("Bitte Zahl eingeben: ");
      zahl = In.readInt();
      muell = In.readLine();
      baum.FuegeEin(zahl);
    } // while
    baum.laufeDurch();

    while (!baum.leer())
    { Out.print("Welche Zahl soll geloescht werden? ");
      zahl = In.readInt();
      muell = In.readLine();    // CR/LF lesen
      baum.loesche(zahl);
      if (!baum.leer()) baum.laufeDurch(); // Kontrolle
    } // while
    Out.print("Der Baum ist leer."); Out.println();
  } // main

} // class BinaerBaumLoeschBsp