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.

Ein Implementation in Java

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.