#1
#2
#3
#4
#5
#6
#7
#8
#9
#10
#11
#12
#13
#14
#15
#16
#17
#18
#19

package adt;



public class BinSuchBaum extends BinBaum {

    

  public void fuegeInBaum(Object wert){

    wurzel = fuegeInBaum(wurzel, wert);

  }                                    



  private Knoten fuegeInBaum(Knoten aktuell, Object wert){

    if(aktuell == null) aktuell = new Knoten(wert);

    else{

      if (wert.toString().compareTo(aktuell.getWert().toString())<0){

        aktuell.setLinks(fuegeInBaum(aktuell.getLinks(),wert));

      }

      else  aktuell.setRechts(fuegeInBaum(aktuell.getRechts(),wert));

    }

    return aktuell;

  }

}

aktuell = new Knoten(wert);

Benutzt wird dabei derjenige Knoten-Konstruktor, der es erlaubt, auch gleich einen Wert in die Knoteninstanz einzutragen.

Was bleibt, ist die eigentliche Frage, wie implementiert man die Bedingung dafür wo der neue Knoten in den Baum eingefügt wird. Schauen wir uns dazu den rekursiven Algorithmus genauer an. Die Klasse, die einen Eintrag vornehmen will, wir werden sie BinSuchBaumDemo nennen,  ruft die Methode fuegeInBaum(Object wert) auf und übergibt dabei den Wert, der in den Baum eingetragen werden soll. Unterscheiden wir die Fälle: Zum einen, der Eintrag in einen leeren  Baum und zum zweiten der Eintrag in einen Baum, in den schon Werte eingetragen sind.

• Beim ersten Eintrag in einen leeren Baum ist es die Wurzel, die den Wert bekommt. Dies geschieht in den Zeilen #6 und #10. In #6 wird dazu die Methode fuegeInBaum(Knoten aktuell, Object wert)¹⁾ mit dem Parametern wurzel und wert aufgerufen. Was macht diese Methode in diesem Fall? Da aktuell (es handelt sich in diesem Fall um die übergebene Wurzel) noch null ist, wird ein neuer Knoten erzeugt, der den übergebenen Wert enthält (vgl. dazu Zeile #10). In Zeile #17 wird aktuell an den Aufrufer zurückgegeben, wo in Zeile #6 dieser Wert schließlich in wurzel abgelegt wird.²⁾ Wir haben somit einen Baum angelegt, in dessen Wurzel ein Wert eingetragen ist; weitere Knoten hat der Baum noch nicht.
• Betrachten wir jetzt den Fall, dass eine Eintragung in einen nicht leeren Baum vorgenommen werden soll. Da die Wurzel in einem nicht leeren Baum immer einen Wert trägt, ist die Bedingung in der Zeile #10 false.  Der einzutragende Wert, wird mit dem Wert des aktuellen Knoten verglichen (vgl. dazu Zeile #12). Ist er kleiner erfolgt die Eintragung im Knoten am Ende de linken Kante sonst am Ende der rechten Kante. Dieses Eintragen erfolgt rekursiv, d.h. fuegeInBaum(...) wird für den linken bzw. rechten Nachfolgeknoten aufgerufen (vgl. Zeilen #13 bzw. #15). Dieser rekursive Abstieg erfolg solange bis der beim Aufruf der rekursiven Methode übergebene linke bzw. rechte Knoten den Wert null hat, der Wert, den man im Baum unterbringen will, alo in einen neuen Knoten eingetragen wird (vgl. dazu wieder Zeile #10). Dieser neue Knoten wird über return zurückgegeben. Der Eintrag ist somit erfolgt. Sind wir damit am Ende? Nein! Was ist mit der Wurzel, die bekommt doch in Zeile #6 eine Referenz zugewiesen. Welche Referenz ist es? Nun, vergessen wir nicht, nach dem rekursiven Abstieg, gehen wir den ganzen Weg wieder zurück und für jeden rekursiven Aufruf wird mit return ein Verweis auf eine entsprechende Eintragung zurückgegeben. Man mache sich klar, dass beim letzten return der Verweis auf die Wurzel zurückgegeben wird und damit haben wir wieder den ganzen Baum 'in der Hand'.

Dieser Abschnitt war nicht leicht. Wer die Geduld und Energie aufgebracht und es schließlich geschafft hat, jedes Detail dieser Klasse zu verstehen, wird damit belohnt, dass ihr/ihm die Eleganz und Ästhetik des Algorithmus'  offensichtlich werden. In nicht gerade informatischen Kategorien gesprochen, kann man einem solchen Programm eine gewisse Poesie nicht absprechen.

¹⁾

²⁾