rekursives Anzeigen

Die show-Methode

Wir wollen nun eine Methode betrachten, welche alle Knoten eines binären Suchbaums einer noch zu implementierenden Klasse BinTree der Reihe nach anzeigt, zuerst den allerkleinsten, am Ende dann den größten Knoten.

Ganz bewusst wird Ihnen das Programmieren einer solchen Methode nicht als Aufgabe gestellt, denn im Internet existieren bereits sehr viele Lösungen für dieses Problem, so dass dies keine echte Herausforderung für Sie mehr wäre. Wir wollen hier lieber eine bewährte Ausgabe-Methode ansehen und besprechen.

public void show()
{
   showR(root);   
}
	
private void showR(Element p)
{
   if (p != null)
   {
      showR(p.left);
      p.show();
      showR(p.right);
   }
}

Wir sehen hier zwei Methoden, die in einer engen Beziehung stehen, die show-Methode und die showR-Methode. Die eigentliche Arbeit wird von showR geleistet, einer rekursiven Methode, die vor dem Benutzer versteckt werden soll (information hiding, siehe auch die Seite zum rekursiven Einfügen).

Arbeitsweise der rekursiven show-Methode

In diesem Abschnitt wollen wir einmal die Arbeitsweise der rekursiven show-Methode eingehend betrachten.

Ebene 1 - die Wurzel

Wir starten mit der rekursiven Methode in der ersten Rekursionsebene. Der Hilfszeiger p zeigt auf die Wurzel 50 des gesamten Baums. Da die Bedingung (p != null) erfüllt ist, wird showR(p.left) aufgerufen, und wir landen bei der 20, der Wurzel des linken Teilbaums der 50.

Ebene 2 - linker Teilbaum der 50

In der zweiten Rekursionsebene passiert das Gleiche wie in der ersten Ebene. Der Hilfszeiger p zeigt auf die Wurzel 20 des linken Teilbaums. Da die Bedingung (p != null) erfüllt ist, wird showR(p.left) aufgerufen, und wir landen bei null.

Ebene 3 - linker Teilbaum der 20

Hier ist nun die Bedingung (p != null) nicht erfüllt, so dass die drei Zeilen

   showR(p.left);
   p.show();
   showR(p.right);

der if-Bedingung übersprungen werden. Damit ist die dritte Ebene auch schon wieder beendet - passiert ist hier nichts.

Zurück in Ebene 2

private void showR(Element p)
{
   if (p != null)
   {
      showR(p.left);
      p.show();
      showR(p.right);
   }
}

In der Rekursionsebene 2 der rekursiven Methode wurde der erste Befehl der if-Bedingung bereits abgearbeitet; jetzt ist der zweite (rot markierte) Befehl an der Reihe, nämlich p.show(). Wenn dieser Befehl ausgeführt wird, erscheint die Zahl 20 in der Konsole. Anschließend wird der Befehl showR(p.right) ausgeführt, der uns wieder in die dritte Rekursionsebene führt.

Wieder in Ebene 3 - rechter Teilbaum der 20

Auch hier ist die Bedingung (p != null) nicht erfüllt, so dass die Ebene gleich wieder beendet wird.

Abermals in Ebene 2

Wir sind jetzt wieder in Ebene 2, aber jetzt sind alle Befehle der if-Bedingung abgearbeitet, und somit können wir die Ebene 2 beenden.

Zurück in Ebene 1

Der Zeiger p steht wieder auf der 50, aber jetzt ist der showR(p.left)-Befehl beendet, und der p.show()-Befehl ist an der Reihe. Also wird die Zahl 50 in der Konsole ausgegeben. Dann kommt der showR(p.right)-Befehl an die Reihe.

In Ebene 2 - rechter Teilbaum der 50

Wir sind jetzt bei der 70. Die Bedingung (p != null) ist erfüllt, also wird der showR(p.left)-Befehl ausgeführt, der uns zur 60 bringt.

Der Rest in Kurzform

Wir sind jetzt bei der 60. Die Bedingung (p != null) ist erfüllt, also wird der showR(p.left)-Befehl ausgeführt, der uns zur null bringt. Jetzt ist die Bedingung (p != null) erfüllt, daher passiert nichts und wir sind wieder bei der 60, die nun ausgegeben wird. Auch der rechte Teilbaum der 60 ist leer, also wird diese Rekursionsebene ganz schnell beendet und wir sind wieder zurück bei der 60.

Da die 60 nun komplett abgearbeitet worden ist, landen wir wieder bei der 70, die jetzt ausgegeben wird. Anschließend wird in den rechten Teilbaum der 70 herabgestiegen. Hier passiert das Gleiche wie im linken Teilbaum der 70: Die 90 wird kurz angeschaut, dann wird der linke Teilbaum der 90 besucht, der aber leer ist. Zurück bei der 90 wird diese ausgegeben, dann wird der rechte Teilbaum besucht, der aber auch leer ist. Damit ist die 90 beendet, und wir sind wieder bei der 70. Diese ist auch beendet, damit sind wir zurück bei der Wurzel, und schließlich ist die gesamte rekursive show-Methode beendet.