In der Klasse BinSuchBaum erfolgt eine spezialisierte Ableitung der Klasse BinBaum. Hier wird die abstrakte Methode fuegeEin nun implementiert.
Dabei arbeiten wir wieder mit einer public- und einer private-Methode. Die public-Methode fügt ausgehend von der Wurzel einen Knoten ein, während die private-Methode das wieder an einem Knoten konkret macht.
public class BinSuchBaum extends BinBaum
{
public void fuegeEin(Object wert)
{
wurzel = fuegeEin(wurzel, wert);
}
private Knoten fuegeEin(Knoten aktuell, Object wert)
{
if(aktuell == null)
aktuell = new Knoten(wert);
else{
if (wert.toString().compareTo(aktuell.getInhalt().toString())<0)
{
aktuell.setLinks(fuegeEin(aktuell.getLinks(),wert));
}
else
aktuell.setRechts(fuegeEin(aktuell.getRechts(),wert));
}
return aktuell;
}
}
In UML sieht dann die Klassenstruktur folgendermaßen aus:
Das eigentliche Einfügen geschieht so, dass ein neuer Knoten erzeugt wird, der den einzutragenden Wert trägt.
aktuell = new Knoten(wert);
Benutzt wird dabei der Knoten-Konstruktor, der es erlaubt, auch gleich einen Wert in die Knoteninstanz einzutragen.
Nun ergibt sich noch das Problem, die richtige Stelle für den Eintrag des
Knotens zu finden. Dazu verwenden wir wieder eine rekursive Methode (die private
fuegeEin).
Wir müssen dabei zwei Fälle unterscheiden:
Beim ersten Eintrag in einen leeren Baum ist es die Wurzel, die den Wert bekommt. Das passiert in der public-Methode fuegeEin. Hierzu wird die private-Methode fuegeEin mit dem Parametern wurzel und wert aufgerufen.
Da aktuell - die Wurzel des Baumes - noch null ist, wird ein neuer Knoten erzeugt, der den übergebenen Wert enthält. Am Ende wird aktuell an die public-Methode zurückgegeben, wo in der Wert in der Variable wurzel abgelegt wird. Damit haben wir einen Baum, in dessen Wurzel ein Wert eingetragen ist, der aber keine weitere Knoten hat.
Tragen wir nun einen Knoten in einen nicht leeren Baum ein, dann hat die Wurzel immer schon einen Wert. Damit ist bei Aufruf der private-Methode durch die public-Methode die if-Bedingung falsch. Dann wird der einzutragende Wert mit dem Wert des aktuellen Knoten verglichen. Ist er kleiner erfolgt die Eintragung im Knoten am Ende der linken Kante sonst am Ende der rechten Kante.
Diese Eintragungen erfolgen rekursiv, d.h. fuegeEin wird für den linken bzw. rechten Nachfolgeknoten aufgerufen. Dieses rekursive Durchwandern des Baums erfolgt solange bis der beim Aufruf der rekursiven Methode übergebene linke bzw. rechte Knoten den Wert null hat, d.h. der Wert, den man im Baum unterbringen will, also in einen neuen Knoten eingetragen wird. Jeder neu eingetragene Knoten wird dann über return zurückgegeben. Der Eintrag ist somit erfolgt.
Nach dem rekursiven Durchlaufen des Baums, wird stufenweise wieder zurückgegangen und für jeden rekursiven Aufruf wird mit return ein Verweis auf eine entsprechende Eintragung zurückgegeben. Beim letzten return wird wieder der Verweis auf die Wurzel zurückgegeben und damit haben wir wieder den ganzen Baum über die Wurzel im Zugriff.
© Ralph-Erich Hildebrandt, 14. Mai 2005