19.3 Das Einfügen von Elementen

Grundlegendes

Kommen wir jetzt zu den eher praktischen Aspekten. Wir wollen ein Programm schreiben, das einen binären Suchbaum im Computer simuliert.

Die Klasse Element

Ein Baum besteht aus einer Reihe von Elementen. Wir wollen zunächst eine Klasse definieren, die für diese Elemente zuständig ist. Dabei erinnern wir uns (hoffentlich) an die Folge 17 über Dynamische Datenstrukturen.

Ähnlich wollen wir auch den binären Suchbaum aufbauen. Allerdings müssen wir den Element-Typ etwas erweitern; ein Zeiger auf das nächste Element reicht nicht mehr aus, jedes Element benötigt einen Zeiger auf den linken Nachfolger sowie einen Zeiger auf den rechten Nachfolger, ungefähr so:

Eine Java-Klasse Element, die das Gewünschte leistet, sähe so aus:

Interessant ist hier, dass in der Zeile 4 zwei Attribute left, right der Klasse Element deklariert werden, obwohl die Klasse Element selbst noch gar nicht "fertig" ist; Zeile 4 befindet sich ja inmitten der Definition der Klasse.

Die Klasse Tree

Damit wir mit diesen Elementen arbeiten können, brauchen wir auch noch eine Klasse Tree, die ungefähr so aufgebaut ist:

Wir wollen jetzt eine Methode buildSampleTree() schreiben, die uns einen einfachen Beispiel-Baum aufbaut, den wir anschließend mit dem Objekt-Inspektor untersuchen wollen.

Der Beispiel-Baum

Hier die erste Fassung der neuen Methode:

Wenn wir das BlueJ-Projekt jetzt kompilieren und ein Objekt der Klasse Tree anlegen, können wir die Methode buildSampleTree() ausführen. Anschließend inspizieren wir das Objekt mit dem Objekt-Inspektor:

Wir sehen, dass der Baum tatsächlich aus einem Element mit dem Wert 100 besteht, und beide Zeiger left, right dieses Elementes haben den Wert null.

Wir wollen jetzt links an dieses Element ein weiteres Element anhängen. Dazu erweitern wir zunächst die Klasse Element um eine neue Methode setLeft():

und benutzen dann in buildSampleTree() diese Methode, um ein neues Element links an die Wurzel anzuhängen:

Wir sehen, dass unsere Operation gelungen ist. Der left-Zeiger des Elements 100 ist nicht mehr leer (null), sondern zeigt auf ein weiteres Element, das den Wert 50 hat.

1. Binärbäume - Allgemeines
2. Binäre Suchbäume
3. Das Einfügen von Elementen
4. Das Anzeigen von Elementen
5. Das rekursive Einfügen von Elementen
6. Das Löschen von Elementen
7. Implementierung mit Hilfe von Arrays
8. AVL-Bäume
9. B-Bäume

Abiturienten NRW

Übung 19.4 (5 Punkte) Betrachten Sie den oben abgebildeten Quelltext. a) Zeichnen Sie den Baum, der durch die Methode aufgebaut wird (1 Punkt). b) Ergänzen Sie die Klasse Element um die noch benötigten Funktionen (2 Punkte). c) Versuchen Sie, in Ihrem Projekt den gleichen Baum aufzubauen und dann mit dem Objekt-Inspektor zu inspizieren (2 Punkte). Aufgaben a) und b) können auch ohne PC erledigt werden!

Lösungshinweise zu allen Übungen der Buchversion finden Sie in dem Lehrerband, den Sie von mir gegen einen kleinen Unkostenbeitrag erhalten können.

und weiter mit Folge 19 - Binärbäume, Teil 3

Diese HTML-Seite wurde erstellt von Ulrich Helmich am 19. April 2006