Traversierung (Binärbaum)

[Snake87]

Hallo Leute,

ich habe eine Frage zur Traversierung:

Erstmal folgender Code:

Es gibt mir dabei nur um die Logik, also der Code ist so nicht ausführbar!

void preOrder(Knoten<E> k){
if (k != null){
tuWas(k.inhalt); // kann den Inhalt z.B. in eine Liste schreiben 
preOrder(k.links);
preOrder(k.rechts);
}

Angenommen wir haben folgenden Baum:
a
/
b
/ \
c d

Der Algorithmus in Worten:

1. Schritt: a wird gelesen
2. Schritt: Funktion wird rekursiv [ preOrder(k.links); ] aufgerufen und "Cursor" steht bei b
3. Schritt: b wird gelesen
4. Schritt: Funktion wird rekursiv [ preOrder(k.links); ] aufgerufen und "Cursor" steht bei c
5. Schritt: c wird gelesen
!!!6. Schritt: Funktion wird rekursiv [ preOrder(k.links); ] aufgerufen und "Cursor" steht bei NULL !!!!

Nun ist k == 0 und nach meiner Verständnis würde preOrder(k.rechts); niemals aufgerufen.

Nur leider ist dies ja nicht der Fall, also wo liegt mein Denkfehler?

LG

 

[Ark]

Vergleich's mal damit:

void preOrder(Knoten<E> k){
	tuWas(k.inhalt); // kann den Inhalt z.B. in eine Liste schreiben 
	if(k.links != null) preOrder(k.links);
	if(k.rechts != null) preOrder(k.rechts);
}

Ark

 

[Snake87]

So macht es für mich Sinn! Und du willst mir sicher sagen das die Methode von mir das selbe macht wie deine....???:L
Nur für mich macht deine Methode was anderes als meine.
Könntest du mir den Zusammenhang der beiden Methoden bitte mal erläutern?

Danke schon im vorraus!

 

[iMpsMight]

Rekursionen sind im Allgemeinen ein etwas konfuses Thema!

Ich versuche das hier mal zu umschreiben, warum die beiden Schnipsel egtl das gleiche aussagen:

Du startest, indem du preOrder(a-Knoten) aufrufst, dort wird das Coding bis zum Befehl preOrder(linkerKnotenVonA) ausgeführt. An dieser Stelle springen wir aus dem Coding vom preOrder(a-Knoten) zum preOrder(b-Knoten) ab. Der Teil mit dem Aufruf des rechten Teilbaums von a aus(in deinem Beispiel ist hier einfach kein Knoten) steht noch zur Bearbeitung aus.
Auch beim b-Knoten wird das Coding nun ausgeführt, bis preOrder(linkerKnotenVonB) augerufen wird. An dieser Stelle wird wie schon beschrieben "abgesprungen" und erst ein mal weiter preOrder(c-Knoten) abgearbeitet.
Nun wird es interessant und hoffentlich wird dir an dieser Stelle nun deutlich, dass sich die beiden Lösungen inhaltlich nichts tun:
Die Ausführung von preOrder(c-Knoten) versucht nun preOrder(linkerKnotenVonC) aufzurufen, welcher allerdings erstmals schon bei der null-Kontrolle scheitert. Dadurch wird kein weiterer Aufruf mehr gestartet und es wird der Aufruf preOrder(rechterKnotenVonC) ausgeführt. Da auch dies zu keinem weiteren Aufruf mehr führt sind nun beide Aufrufe für den c-Knoten durchgeführt und das Programm macht weiter in der preOrder(b-Knoten) in der ja noch der Aufruf der rechten Seite offen ist. Für den d-Knoten ist dann der Verlauf wie beim c-Knoten beschrieben. Nachdem der d-Knoten fertig abgearbeitet ist, sind beide rekursiven Aufrufe auch für den b-Knoten abgearbeitet und das Programm bearbeitet nun den Aufruf des rechten Teilbaums vom a-Knoten aus. Da auch hier kein weiterer Knoten ist ist die Abarbeitung des Baums abgeschlossen.

Ich hoffe das Prinzip ist auch in dieser langen Umschreibung deutlich geworden!

Viele Grüße,
iMpsMight