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