Vorlesung Informatik 2 - Teil B: Theorie
4.2 Binärbäume
Ein Binärbaum (binary tree) ist leer oder besteht aus einer Wurzel und zwei Teilbäumen.
Binärbäume sind besonders einfach zu implementieren, da man genau zwei Teilbäume (links, rechts) hat und die Teilbäumen nicht in einer Liste verwalten muss.
Implementierung in Java:
Baum<T>:
#Inhalt:T
#vater, links, rechts:Baum<T>
+Baum(inhalt:T)
Ein Objekt vom Typ Baum ist also nichts anderes ein Knoten des Baums - das entspricht der rekursiven Definition von Bäumen.
Die Klasse sollte zunächst die folgenden Methode haben:
+ istNachkomm(k: Baum<T>): boolean liefert true, wenn es eine Pfad von k nach this gibt
+ setLinks(k: Baum<T>): void macht k zum linken Teilbaum von this
+ setRechts(k: Baum<T>): void macht k zum rechten Teilbaum von this
+ tiefe(): int liefert die Tiefe des Knotens (1 für die Wurzel)
+ getVater(): Baum<T> liefert den Vater bzw. null für die Wurzel
# loeseVomVater():void setzt in this.vater den entsprechenden Teilbaum zu null.
Die Methoden tiefe und istNachkomme sind am einfachsten rekursiv zu lösen:
- Die Tiefe eines Baumes ist 1, wenn es die Wurzel ist, ansonsten 1+vater.tiefe().
- Um zu prüfen, ob this ein Nachkomme des Knotens k ist, geht man wie folgt vor
- wenn this die Wurzel ist, gib false zurück
- Wenn k==this-vater, gib true zurück,
- ansonsten prüfe, ob vater ein Nachkomme von k ist (Rekursion)