Ein Binärbaum mit Java

Ein (Binär)Baum ist eine rekursive Datenstruktur. Bei jedem Knoten des Baums zeigen left und right jeweils auf einen weiteren Baum:

Die Blätter des Baums zeichnen sich dadurch aus, dass left und right auf null zeigen, also nicht auf weitere "Unterbäume" verweisen.

Mit diesen Überlegungen kann man sich die folgende Implementation in Java ansehen: https://codeberg.org/qg-info-unterricht/binaerbaum-einstieg

Es gibt nur eine Klasse Binaerbaum die eigentlich Knotenobjekte darstellt. Der Baum selbst wird repräsentiert durch das Knotenobjekt des Wurzelknotens.

Durch überladen des Konstruktors wird Polymorphie des Konstruktors erzwungen, man kann also verschiedene Knoten erzeugen:

• Innere Knoten: Erhalten als Argumente einen Datenwert und die Wurzelknoten der Unterbäume links und rechts
• Blattknoten: Erhalten einen (oder keinen) Datenwert. links und rechts wird auf null gesetzt.

Untersuche die Klasse Binaerbaum und ihre Methoden im Projekt. Erzeuge mit Hilfe der zur Verfügung stehenden Methoden den in der Abbildung gezeigten Baum mit Integer-Werten:

• Top-Down, beginnend beim Wurzelknoten
• Bottom-Up, beginnend bei den Blättern

• Verifiziere jeweils durch die Inspizieren Funktion von BlueJ, dass die Baumstruktur wie gefordert stimmt, indem due beim Wurzelknoten beginnend den Pfaden folgst.
• Teste die Methode isBlatt und verifiziere die Funktionsweise an mehreren Knoten.

Hilfestellung

Implementiere die Methoden baueBaumTopDown und baueBaumBottomUp in der Klasse Zahlenbaum, so dass der dargestellt Baum aus Integerwerten entsteht.

Lösungsvorschlag