Folge 19 - Bäume
Die show()-Methode

1. Instanz - show 100

Wir starten die show()-Methode für die Wurzel des gesamten Baums und sagen, dass wir uns in der ersten Instanz von show() befinden.

In der show()-Methode wird nun getestet, ob ein linker Teilbaum der 100 existiert. Das ist der Fall, also wird jetzt rekursiv eine zweite Instanz von show() für das Element 50 - die Wurzel des linken Teilbaums - aufgerufen.

2. Instanz - show 50

Jetzt befinden wir uns in der 2. Instanz der show()-Methode. Für die neue Wurzel 50 wird jetzt wieder überprüft, ob ein linker Teilbaum existiert. Das ist wieder der Fall, allerdings besteht der linke Teilbaum hier nur aus dem einen Element mit dem Wert 30. Da ein linker Teilbaum existiert, wird jetzt für diesen die show()-Methode erneut aufgerufen.

3. Instanz - show 30

Wir befinden uns jetzt in der dritten Instanz der show()-Methode, die Wurzel hat den Wert 30.

19 In der dritten Instanz der show()-Methode

In der 3. Instanz wird überprüft, ob die 30 einen linken Teilbaum hat. Das ist nicht der Fall, der left-Zeiger des Elementes hat den Wert null.

Ein Blick auf den Quelltext der show()-Methode sagt uns, dass jetzt der Wert des Elementes in die Konsole geschrieben wird; die Zeile 35 wird ausgeführt, in der Konsole erscheint die Zahl 30.

Anschließend wird die Zeile 36 ausgeführt. Hier wird der rechte Teilbaum der 30 überprüft. Da auch dieser leer ist, wird die show()-Methode beendet. Allerdings nicht komplett, denn wir befanden uns ja in der dritten Instanz der show()-Methode. Nur diese dritte Instanz wird verlassen. Danach befinden wir uns aber immer noch in der zweiten Instanz, die ja noch nicht komplett durchlaufen wurde.

2. Instanz - show 50

Wir befinden uns wieder in der zweiten Instanz der show()-Methode. Die Zeile 34 dieser zweiten Instanz wurde bereits ausgeführt, daher habe ich die 50 in der obigen Abbildung rosa dargestellt. Rosa soll hier heißen: Der linke Teilbaum ist abgearbeitet, aber der rechte noch nicht. Grün heißt dagegen, dass beide Teilbäume abgearbeitet wurden; dies ist bei der 30 der Fall.

Jetzt wird die Zeile 35 ausgeführt und die Zahl 50 in die Konsole geschrieben. Dann wird die Zeile 36 der zweiten Instanz ausgeführt. Eine Überprüfung des rechten Teilbaums ergibt, dass ein solcher existiert. Also wird show() für den rechten Teilbaum aufgerufen

3. Instanz - show 70

Wir befinden uns in der dritten Instanz von show(). In dieser dritten Instanz wird als erstes überprüft, ob ein linker Teilbaum für das Element 70 existiert (Zeile 34). Da dies der Fall ist, wird eine vierte Instanz von show() für diesen linken Teilbaum aufgerufen.

4. Instanz - show 60

Jetzt sind wir in der vierten Instanz von show() für die Wurzel 60. Und wieder wird die Zeile 34 ausgeführt. Da ein linker Teilbaum der 60 nicht vorhanden ist, wird die Zeile 35 ausgeführt und der Wert 60 in die Konsole geschrieben. Anschließend wird die Zeile 36 ausgeführt und überprüft, ob ein rechter Teilbaum existiert. Da dies nicht der Fall ist, wird die vierte Instanz von show() verlassen und wir befinden uns wieder in der dritten Instanz - bei dem Element 70.

3. Instanz - show 70

In dieser dritten Instanz muss jetzt die Zeile 35 ausgeführt werden, die Zahl 70 wird ausgegeben. Anschließend wird die Zeile 36 der dritten Instanz ausgeführt und show() wird rekursiv für die 88 aufgerufen.

4. Instanz - show 88

Ein linker Teilbaum existiert nicht, also wird der Wert 88 ausgegeben und anschließend untersucht, ob ein rechter Teilbaum existiert. Dies ist nicht der Fall, somit wird die vierte Instanz für die 88 beendet, und wird befinden uns wieder in der dritten Instanz für die 70.

3. Instanz - show 70

In dieser dritten Instanz wurden alle Befehle abgearbeitet, also wird die dritte Instanz verlassen, und wir befinden uns jetzt in der zweiten Instanz von show.

2. Instanz - show 50

Auch in dieser zweiten Instanz wurden alle Befehle abgearbeitet, also wird auch die zweite Instanz verlassen, und wir befinden uns wiede in der ersten Instanz.

1. Instanz - show 100

Der linke Teilbaum der 100 wurde jetzt komplett abgearbeitet, also wird der Wert 100 in die Konsole geschrieben und dann show für den rechten Teilbaum aufgerufen.

2. Instanz - show 210

Noch ein letztes Photo des Baumes - und jetzt müsste eigentlich jedem klar geworden sein, wie die rekursive show()-Methode arbeitet.

zurück zu Folge 19 - Binärbäume, Teil 3

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