Traversieren von Bäumen

[Frank Schönmann]

hi!

Das bedeutet also, wenn ich das anwende, um beispielsweise alle Unterverzeichnisse
von C: anzuzeigen, das die Anwendung erst zum zweiten Unterverzeichnis des
obersten Verzeichnisses (C:) kommt, wenn alle (Unter-)Unterverzeichnisse des ersten
Unterverzeichnisses abgearbeitet wurden ?! Alles klar? :-) . Wäre dann nicht-rekursiv,
wenn erst alle Verzeichnisse der obersten Ebene, dann alle Verzeichnisse des ersten
Verzeichnisses des obersten Verzeichnisses, dann alle des zweiten des obersten
usw. betrachtet würden ?

Nein.

Man kann unterscheiden zwischen rekursiven und iterativen Algorithmen, um einen
Baum zu traversieren. Der Unterschied ist der gleiche wie bei allen anderen Algorithmen
auch: rekursiv bedeutet, dass die Traversierungs-Funktion sich selbst aufruft, iterativ
bedeutet, dass sie Schleifen verwendet.

Anschließend kann man noch unterscheiden zwischen pre-order, post-order und in-
order traversal. pre-order bedeutet, dass auf der aktuellen Ebene eine Operation
angewendet wird, bevor die Kindknoten traversiert werden (zb. die Anzeige der Dateien
in deinem Verzeichnis-Beispiel), post-order bedeutet, dass erst die Kindknoten
traversiert werden, bevor die Operation durchgeführt wird. in-order heißt bei einem
Binärbaum, dass zuerst der linke Kindknoten traversiert wird, dann die Operation
ausgeführt und anschließend der rechte Kindknoten traversiert.

Was du oben gemeint hast, eine Traversierung bei der zuerst alle Knoten auf der ersten
Ebene, dann alle auf der zweiten Ebene, und so weiter besucht werden, ist aus
Effizienzgründen sinnlos, da der Speicherbedarf exponentiell anwachsen würde, im
Endeffekt aber das gleiche Ergebnis geliefert wird wie bei der anderen Variante.

Eine Anwendung beider Varianten kann sinnvoll sein, wenn man einen Baum nicht
traversiert, sondern etwas darin sucht (was sich insbesondere darin unterscheidet, dass
nicht alle Knoten betrachtet werden). Dann nennt man die Methode, ebenenweise den
Baum zu durchsuchen Breitensuche (breadth-first search), die Methode, einen Ast bis
zum Ende zu verfolgen Tiefensuche (depth-first search). Tiefensuche ist problematisch,
wenn der Baum unendlich tief ist; Breitensuche kann eine Lösung dafür sein, da Bäume
mit unendlicher Breite im Gegensatz zu Bäumen mit unendlicher Tiefe eher selten sind.
Daneben gibt es zb. auch verschiedene Kombinationen der beiden Suchverfahren.

Welches sind die Vorteile von rekursiver bzw nicht-rekursiver Traversierung?

Rekursion kann problematisch sein, wenn die Rekursionstiefe oder die Stackgröße
beschränkt ist. Allerdings braucht man beim iterativen Verfahren zusätzliche Infos
in den Knoten (parent references), wodurch hier der Speicherbedarf für die
Datenstruktur ansteigt. Die Vor- oder Nachteile sind also problemabhängig.

Und ist das dann nicht auch etwas gefährlich, wenn einem nicht bekannt ist, wie
viele Unterverzeichnisse (Ebenen) der Baum hat ? Ich stelle mir mal einen Baum vor,
der alle möglichen Züge einer Schachpartie darstellen soll... Ein solches Programm
würde ja nie - nie = alles, was über zehn milliarden Jahre dauert ;-) - zu einem Ende
kommen.

Das ist ungefähr richtig. Schachspielen ist allerdings ein Suchproblem und kein
Traversierungsproblem. Hier kämen also eher die von mir genannten Suchverfahren
zum Tragen. Tiefen- und Breitensuche sind allerdings für diesen Zweck ungeeignet,
da ineffizient. Zum Schachspielen werden wohl eher heuristische Suchverfahren
eingesetzt, bei denen es von den Erfolgsaussichen abhängig ist, wie weit ein Ast des
Baums nach unten verfolgt wird.

Ich hoffe, ich konnte das trotz so später Stunde einigermaßen verständlich erklären... ;)

bye, Frank!