19.5 Das rekursive Einfügen von Elementen

Rekursives Einfügen

Wir können den Algorithmus zum rekursiven Einfügen in einen binären Suchbaum erst mal provisorisch formulieren:

20 Flussdiagramm für das rekursive Einfügen

Schauen wir uns nun den dazugehörigen Java-Quelltext an:

21 Quelltext: rekursives Einfügen in einen Suchbaum

Es soll ein Objekt e der Klasse Element in den Suchbaum eingefügt werden. Entscheidend für das richtige Einfügen ist der Wert des Elementes, der durch die sondierende Methode getValue() geliefert wird. Der eigentliche Inhalt des Elementes ist ja durch Datenkapselung geschützt, nur mit sondierenden Methoden darf auf den Inhalt zugegriffen werden - aber das wissen Sie ja bereits alles.

Die Abfrage, ob die Wurzel des Baumes leer ist (siehe Flussdiagramm in Abb. 20), kann hier entfallen. Wir befinden uns in der insert()-Methode der Klasse Element und noch nicht in der insert()-Methode der Klasse Tree. Ein Element ist aber nach seiner Erzeugung nicht mehr leer, sondern hat bereits einen Wert. Allerdings sind die beiden Zeiger left, right "leer", da sie beide den Wert null besitzen.

Die insert()-Methode von Element kann also gleich mit der Frage beginnen, ob das neue Element einen kleineren Wert als das bisherige hat. In Zeile 20 wird diese Frage gestellt.

22 Flussdiagramm zum Einfügen eines neuen Elementes, etwas genauer

Ist das neue Element kleiner als das alte, so müssen zwei Fälle unterschieden werden:

Fall 1 - es gibt noch keinen linken Teilbaum.

Fall 2 - es ist ein linker Teilbaum vorhanden.

Im ersten Fall ist das Einfügen leicht; der left-Zeiger wird einfach auf das neue Element gesetzt. Dies geschieht in Zeile 22 des Quelltextes.

Im zweiten Fall wird rekursiv vorgegangen. Der linke Teilbaum ist ein vollständiger binärer Suchbaum, also wird jetzt einfach die insert()-Methode für diesen Teilbaum aufgerufen, und dann soll der mal zusehen, wie das neue Element untergebracht wird.

Ist das neue Element nicht kleiner als das alte, wird analog für den rechten Teilbaum des Elementes vorgegangen (Zeilen 25 - 29).

  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

Diese Webseite über Bäume wird nicht weiter entwickelt. Statt dessen können Sie die Buchversion des Skriptes gegen gleichwertiges Tauschmaterial oder einen kleinen Unkostenbeitrag Ivon mir erhalten.

Den ersten Teil der Folge 19 können Sie hier kostenlos als PDF-Datei herunterladen.

Schreiben Sie mir eine E-Mail, wenn Sie Interesse haben.

Abiturienten NRW

Gehen Sie bitte auch auf die "offizielle" BinTree-Seite!

Übung 19.7 (PC, 2 Punkte)

Bringen Sie die insert()-Methode auf Ihrem Rechner zum Laufen und testen Sie sie.

Die drei folgenden Aufgaben sind alternativ. Die eine ist mehr für die Programmier-Spezialisten, die zweite mehr für die Informatik-Spezialisten unter Ihnen. Wer Abitur im Fach Informatik machen möchte, sollte die Übung 19.8-B bearbeiten. Wer sich weder A noch von B zutraut, kann sich an der leichteren Aufgabe C versuchen.

Übung 19.8-A (PC, 6 Punkte)

Das ist eine Aufgabe nur für Programmier-Spezialisten, die die Aufgabe 19.6 erfolgreich bearbeitet haben.

Ergänzen Sie Ihr Java-Applet um ein Textfield zur Eingabe von Zahlen sowie um einen Button zum Hinzufügen neuer Elemente. Testen Sie dann die insert()-Methode aus Übung 19.7. Immer dann, wenn Sie ein neues Element hinzugefügt haben, soll der Baum mit der show()-Methode neu gezeichnet werden.

Übung 19.8-B (schriftlich, 6 Punkte)

Erkundigen Sie sich im Internet oder in der Literatur, was man unter einem "ausgeglichenen Binärbaum" oder einem "AVL-Baum" versteht, welchen Vorteil diese Bäume haben und welche besonderen Maßnahmen beim Einfügen in einen solchen Baum zu beachten sind.

Übung 19.8-C (schriftlich, 3 Punkte)

Schreiben Sie eine einfache sondierende Methode 
public boolean member(int value)

für die Klasse Tree, die feststellt, ob die angegebene Zahl im Baum vorhanden ist oder nicht. Diese Methode kann rekursiv sein, sie kann aber auch ganz "normal" programmiert werden. Wenn die Zahl im Baum vorkommt, soll member() TRUE zurückliefern, andernfalls FALSE.

Diese Webseite über Bäume wird nicht weiter entwickelt. Statt dessen können Sie die Buchversion des Skriptes gegen gleichwertiges Tauschmaterial oder einen kleinen Unkostenbeitrag Ivon mir erhalten. Schreiben Sie mir eine E-Mail, wenn Sie Interesse haben.

Die Lösungen zu den Übungen finden Sie in dem Lehrerband, den ich zur Zeit erarbeite.

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

Die Übungen der Buchversion unterscheiden sich teils erheblich von den hier veröffentlichen Übungen. Das liegt daran, dass ich die Folge 19 für die Buchversion völlig überarbeitet habe. Sehr schwere Aufgaben sind ganz herausgenommen worden, einige Aufgaben sind umformuliert worden, bei einigen Aufgaben wurde das Bewertungsschema angepasst, weil ich nämlich beim Lösen erst selbst gemerkt habe, wie schwer manche Aufgaben in Wirklichkeit sind, und einige Aufgaben sind auch ganz neu dazugekommen.

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

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