public class Baum {
  // die Klasse "Baum" entspricht in ihrer Funktion einem Listenkopf;
  // Objekte der Klasse "Baum" enthalten eine Referenz auf die Wurzel
  // des eigentlichen Baums, der aus Objekten der Klasse "Knoten"
  // (siehe unten) aufgebaut ist.

  Knoten wurzel;


  public void fuegeEin(int n) {
    // füge Knoten n in den Baum ein.

    if (wurzel == null) {
      // falls Baum noch leer, lege ersten Knoten mit Wert n an.
      wurzel = new Knoten(n);
    } else {
      // anderenfalls füge n in den existierenden Baum ein.
      wurzel.fuegeEin(n);
    }
  }


  public void loesche(int n) {
    // lösche den Knoten n, falls vorhanden, aus dem Baum.

    Knoten hk;

    if (wurzel == null) {
      // Baum ist leer; n kommt also im Baum nicht vor: nichts zu tun.
    } else if (wurzel.wert == n) {
      // n ist die Wurzel des Baums.
      if (wurzel.kindL == null) {
        // falls der Baum keinen linken Unterbaum hat, ersetze ihn durch
        // seinen rechten Unterbaum.
	wurzel = wurzel.kindR;
      } else if (wurzel.kindR == null) {
        // falls der Baum keinen rechten Unterbaum hat, ersetze ihn durch
        // seinen linken Unterbaum.
	wurzel = wurzel.kindL;
      } else {
        // sonst: suche den Vorgängerknoten hk der Wurzel des Baums und
        // lösche ihn an seiner bisherigen Position.
	hk = wurzel.loescheUndLiefereNaechstKleineren();
        // ersetze die Wurzel des Baums durch hk.
	hk.kindL = wurzel.kindL;
	hk.kindR = wurzel.kindR;
        wurzel = hk;
      }
    } else {
      // sonst: lösche n unterhalb der Wurzel im Baum.
      wurzel.loesche(n);
    }
  }


  public String toString() {
    // Baumdurchlauf in infix-Reihenfolge; die beiden Unterbäume werden,
    // falls vorhanden, geklammert

    if (wurzel == null) {
      return "";
    } else {
      return "(" + wurzel.toString() + ")";
    }
  }


  public static void main(String[] argv) {
    // Testbeispiel
    Baum b = new Baum();
    b.fuegeEin(18);
    b.fuegeEin(20);
    b.fuegeEin(2);
    b.fuegeEin(0);
    b.fuegeEin(4);
    b.fuegeEin(7);
    b.fuegeEin(30);
    b.fuegeEin(3);
    b.fuegeEin(5);
    b.fuegeEin(6);
    b.fuegeEin(40);
    System.out.println(b);
    b.loesche(18);
    System.out.println(b);
  }

}


/**********************************************************************/

class Knoten {
  // Objekte der Klasse "Knoten" enthalten eine int-Markierung und
  // Referenzen auf den linken und rechten Unterbaum.

  Knoten kindL;
  Knoten kindR;
  int wert;


  Knoten(int n) {
    wert = n;
  }


  public void fuegeEin(int n) {
    // füge Knoten n in den Baum ein.

    if (n < wert) {
      // n gehört in den linken Unterbaum.
      if (kindL == null) {
        // falls linker Unterbaum noch leer, lege ersten Knoten mit Wert n an.
        kindL = new Knoten(n);
      } else {
        // anderenfalls füge n in den existierenden linken Unterbaum ein.
        kindL.fuegeEin(n);
      }
    } else if (n > wert) {
      // n gehört in den rechten Unterbaum.
      if (kindR == null) {
        // falls rechter Unterbaum noch leer, lege ersten Knoten mit Wert n an.
        kindR = new Knoten(n);
      } else {
        // anderenfalls füge n in den existierenden rechten Unterbaum ein.
        kindR.fuegeEin(n);
      }
    }
    // falls n gleich der Wurzel des Baums ist, gibt es nichts zu tun.
  }


  public void loesche(int n) {
    // lösche den Knoten n *unterhalb der Wurzel*. Falls n die Wurzel
    // des Baum ist, kann n *nicht* innerhalb dieser Methode gelöscht
    // werden; das muß bereits in der aufrufenden Methode geschehen.

    Knoten hk;

    if (n < wert) {
      // n kommt, wenn überhaupt, im linken Unterbaum vor.
      if (kindL == null) {
        // linker Unterbaum ist leer; n kommt also im linken Unterbaum
	// nicht vor: nichts zu tun.
      } else if (kindL.wert == n) {
        // n ist die Wurzel des linken Unterbaums.
        if (kindL.kindL == null) {
	  // falls der linke Unterbaum keinen linken Unterbaum hat,
	  // ersetze ihn durch seinen rechten Unterbaum.
          kindL = kindL.kindR;
        } else if (kindL.kindR == null) {
          // falls der linke Unterbaum keinen rechten Unterbaum hat,
          // ersetze ihn durch seinen linken Unterbaum.
          kindL = kindL.kindL;
        } else {
          // sonst: suche den Vorgängerknoten hk der Wurzel des linken
	  // Unterbaums und lösche ihn an seiner bisherigen Position.
          hk = kindL.loescheUndLiefereNaechstKleineren();
          // ersetze die Wurzel des linken Unterbaums durch hk.
          hk.kindL = kindL.kindL;
          hk.kindR = kindL.kindR;
          kindL = hk;
        }
      } else {
        // sonst: lösche n unterhalb der Wurzel im linken Unterbaum.
        kindL.loesche(n);
      }
    } else if (n > wert) {
      // n kommt, wenn überhaupt, im rechten Unterbaum vor.
      if (kindR == null) {
        // rechter Unterbaum ist leer; n kommt also im rechten Unterbaum
        // nicht vor: nichts zu tun.
      } else if (kindR.wert == n) {
        // n ist die Wurzel des rechten Unterbaums.
        if (kindR.kindL == null) {
          // falls der rechte Unterbaum keinen linken Unterbaum hat,
          // ersetze ihn durch seinen rechten Unterbaum.
          kindR = kindR.kindR;
        } else if (kindR.kindR == null) {
          // falls der rechte Unterbaum keinen rechten Unterbaum hat,
          // ersetze ihn durch seinen linken Unterbaum.
          kindR = kindR.kindL;
        } else {
          // sonst: suche den Vorgängerknoten hk der Wurzel des rechten
          // Unterbaums und lösche ihn an seiner bisherigen Position.
          hk = kindR.loescheUndLiefereNaechstKleineren();
          // ersetze die Wurzel des rechten Unterbaums durch hk.
          hk.kindL = kindR.kindL;
          hk.kindR = kindR.kindR;
          kindR = hk;
        }
      } else {
        kindR.loesche(n);
      }
    }
  }


  Knoten loescheUndLiefereNaechstKleineren() {
  // Loesche denjenigen Knoten, der den nächstkleineren Wert als die
  // Wurzel hat, (also den größten Knoten des linken Unterbaums) aus
  // dem Baum heraus, und liefere ihn zurück.

    Knoten hk0, hk;

    if (kindL.kindR == null) {
      // falls der linke Kindknoten keinen rechten Kindknoten hat,
      // dann ist er selbst der gesuchte nächstkleinere Knoten hk;
      // lösche ihn an seiner bisherigen Position aus dem Baum heraus
      // und gib ihn als Resultat zurück.
      hk = kindL;
      kindL = kindL.kindL;
      hk.kindL = null;
      return hk;
    } else {
      // sonst: setze hk0 auf den linken Kindknoten und laufe den
      // linken Unterbaum nach rechts herab, solange, bis wir den
      // Elternknoten des gesuchten Knotens erreicht haben.
      hk0 = kindL;
      while (hk0.kindR.kindR != null) {
        hk0 = hk0.kindR;
      }
      // der rechte Kindknoten von hk0 ist nun der gesuchte
      // nächstkleinere Knoten hk; lösche ihn an seiner bisherigen
      // Position aus dem Baum heraus und gib ihn als Resultat zurück.
      hk = hk0.kindR;
      hk0.kindR = hk0.kindR.kindL;
      hk.kindL = null;
      return hk;
    }
  }


  public String toString() {
    // Baumdurchlauf in infix-Reihenfolge; die beiden Unterbäume werden,
    // falls vorhanden, geklammert

    String s = "";

    if (kindL != null) {
      s += "(" + kindL.toString() + ")";
    }
    s += wert;
    if (kindR != null) {
      s += "(" + kindR.toString() + ")";
    }
    return s;
  }

}