28.16 Die Klasse BinSuchBaum |
|
Download: BinSuchBaum. java |
Der
binäre Suchbaum zeichnet sich durch die besondere Arte des Einfügens von
Daten aus. |
#1 |
|
Kommentar | Das
eigentliche Einfügen geschieht so, dass ein neuer Knoten erzeugt wird, der
den einzutragenden Wert trägt. Dies passiert an der mit Gelb unterlegten
Stelle in Zeile #10:
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.
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. |
Fussnoten | |
Man beachte, die beiden Methoden tragen den gleichen Namen unterscheiden sich aber in der Signatur. [zurück] | |
Dass man
den Wert nicht direkt in die Wurzel einträgt sondern über einen
neuerzeugten Knoten aktuell
geht, liegt daran, dass wir diese Programmzeile auch für Neueintragungen
benötigen, wenn diese nicht mehr in der Wurzel stattfindet.
[zurück] |
|
zu | 28.17 Eine Testklasse |
zur Startseite | www.pohlig.de (C) MPohlig 2004 |