19.4 Das Anzeigen von Elementen
Eine rekursive Methode
Betrachten Sie folgenden Quelltext:
17 Rekursive show()-Methode der Klasse Element
Mit dieser show()-Methode kann man den Inhalt des gesamten Binärbaums in der Konsole anzeigen. Dabei werden die Zahlen geordnet ausgegeben, erst die kleinen, dann die großen.
Wie funktioniert diese Methode, und warum ist der Quelltext so kurz? Analysieren wir sie Zeile für Zeile.
Die Zeile
if (left != null) left show();
kann folgendermaßen übersetzt werden:
Wenn ein linker Teilbaum vorhanden ist, zeige diesen linken Teilbaum.
18 Ein Beispielbaum
Wir wollen die Methode show() für die Wurzel (100) des in Abbildung 18 gezeigten Baumes ausführen. Zunächst wird gefragt, ob ein linker Teilbaum vorhanden ist. Das ist hier der Fall, und die Zahl 50 (eigentlich: "Das Element mit dem Wert 50") ist die Wurzel des linken Teilbaums.
Also wird jetzt die show()-Methode rekursiv für den linken Teilbaum aufgerufen.
- Binärbäume - Allgemeines
- Binäre Suchbäume
- Das Einfügen von Elementen
- Das Anzeigen von Elementen
- Das rekursive Einfügen von Elementen
- Das Löschen von Elementen
- Implementierung mit Hilfe von Arrays
- AVL-Bäume
- 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!
Betrachten Sie folgenden Quelltext noch einmal sehr genau:
19 Rekursive show()-Methode der Klasse Element, zum genauen Betrachten
Wenn Sie sich schon öfters mit rekursiven Funktionen beschäftigt haben, müsste Ihnen die Funktionsweise dieser show()-Methode eigentlich klar sein. Haben Sie dagegen Schwierigkeiten mit rekursiven Funktionen, besuchen Sie bitte die Spezialseite zur show()-Methode, die ich für Sie - und für mich - geschrieben habe.
Ich selbst habe nämlich auch immer Probleme, mir rekursive Funktionen klar zu machen, daher habe ich die Arbeitsweise der show()-Methode einmal Schritt für Schritt dokumentiert.
Diese Art des Durchsuchens eines Baums trägt übrigens die Bezeichnung "inorder". Erst wird der jeweils linke Teilbaum abgearbeitet, dann wird der Wert der aktuellen Wurzel ausgegeben, und danach wird der rechte Teilbaum untersucht. Die Ausgaberoutine steht inmitten der beiden rekursiven Aufrufe, daher der Name "inorder"-Ausgabe.
Übung 19.5 (2 Punkte)Bringen Sie die show()-Methode auf Ihrem Rechner zum Laufen und testen Sie, ob der Baum, den Sie aufgebaut haben, korrekt ausgegeben wird. |
Übung 19.6 (6 Punkte)Das ist eine Aufgabe nur für Spezialisten.Schreiben Sie eine show()-Methode, die a) im Graphik-Modus arbeitet und b) die Elemente des Baumes ähnlich wie in den Abbildungen auf dieser Seite in Baumform ausgibt. Testen Sie Ihre Show-Methode mit einem Java-Applet, das Sie natürlich auch noch schreiben müssen. (4 Punkte für die baumartige Ausgabe der Elemente, 2 Punkte für korrekte Pfeile zwischen den Knoten). Wer diese Übung in Angriff nimmt, darf auf keine Hilfe von mir rechnen - ich selbst habe diese graphische Show-Methode nämlich noch nicht in Java programmiert. Einen kleinen Tipp kann ich Ihnen aber geben, an den ich mich noch aus den Zeiten der CRT-Programmierung und Pascal erinnere. Die Baum-Elemente werden als Quadrate dargestellt, in denen die Zahlen stehen. Jedes Quadrat hat eine X- und eine Y-Koordinate. Die Y-Koordinate ist leicht zu berechnen, sie hängt nämlich ausschließlich von der Ebene ab, in der sich das Element befindet. Schwieriger zu berechnen ist die X-Koordinate. Am besten rechnen Sie intern mit negativen Zahlen; die X-Koordinate der Wurzel kann dann nämlich einfach 0 sein. Die linke Nachfolgerknoten hat dann z.B. die X-Koordinate -200, der rechte +200. Die horizontalen Abstände zwischen den Knoten müssen mit jeder Ebene immer kleiner werden, sonst überlagern sich die Knoten recht schnell. Wenn Sie sich nun noch die Koordinaten aller Knoten in einem eigenen Array merken, so können Sie nach dem Zeichnen der Knoten auch die Knoten durch Pfeile verbinden (2 Punkte). |
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.
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.
und weiter mit Folge 19 - Binärbäume, Teil 4
Diese HTML-Seite wurde erstellt von Ulrich Helmich am 19. April 2006