Klassendiagramm des Binärbaums

Objektorientierte Realisierung

Wir haben jetzt eine schöne Definition des Binärbaums und sogar schon eine Idee, wie wir ihn schlussendlich benutzen können, um unsere binäre Suche auszuführen.

Was uns noch fehlt, ist eine Methode, das in Programmen umzusetzen. Deswegen wollen wir uns jetzt gemeinsam daran machen, eine praktische Umsetzung zu finden.

Wenn Du dich noch an die Konzepte objektorientierter Programmierung erinnerst, hast Du vielleicht bereits daran gedacht diese hier zu benutzen.

Zu diesem Zweck, wollen wir hier erstmal ein Klassendiagramm erstellen. Falls Du nicht genau weißt, was ich damit meine, solltest Du dir vorher (noch) einmal das Kapitel zu UML anschauen.

Natürlich besteht unser Baum einfach nur aus einer Anzahl an Knoten. Wir können also schonmal festhalten, dass wir die Klassen Baum und Knoten brauchen.

Wir wissen, dass wir in unserem Baum jedem Knoten einen Zeiger auf sein linkes und rechtes Kind mitgeben, also braucht jeder Knoten genau drei Attribute: Den Wert des Knotens selbst, sein linkes Kind und sein rechtes Kind.

Wenn jeder Knoten diese Informationen hat, braucht unser Baum eigentlich nur noch einen Zeiger auf seine Wurzel und wir können jeden Knoten wie geplant erreichen. Zusammen ergibt das folgendes: