Traversieren von Bäumen

[vielfrager]

Hallo an alle Selfhtml-ler,

ich lese in tutorials immer wieder etwas von rekursiver oder nicht rekursiver traversierung von (binär-)Bäumen. Was bedeutet das ? Kennt jemand ein verständliches Tutorial darüber ?

Grüsse,

vielfrager

[at]

Hallo.

ich lese in tutorials immer wieder etwas von rekursiver oder nicht rekursiver traversierung von (binär-)Bäumen. Was bedeutet das ?

Das geordnete Durchgehen eines solchen Baumes. Rekursiv wird dieser Vorgang, wenn sich der Vorgang an jeder Abzweigung auf der nächsten Ebene in gleicher Form fortsetzt, um nach Abschluss des Durchgangs dieser Ebene auf die vorherige zurückzukehren und den dort unterbrochenen Durchgang fortzusetzen.
MfG, at

[flo]

Hallo.
MfG, at

hallo, warum heisst das eigentl. "binär- baum" für mich ist das ein "baum" objekt

gruß flo

[Götz]

Hallo flo!

hallo, warum heisst das eigentl. "binär- baum" für mich ist das ein "baum" objekt

Wenn jeder Knoten in einem Baum nur 2 Kindknoten/Blätter hat, ist es ein Binärbaum.
Es gibt natürlich noch diverse andere Bäume, deswegen ist es schon sinnvoll, auch Binärbaum zu schreiben, wenn man Binärbaum meint.
Siehe auch http://de.wikipedia.org/wiki/Binärbaum.

MfG
Götz

[flo]

Götz

hallo, danke! so viel text und dabei ist das eher als reduktion gemeint.. ich habe bisher immer soetwas (mit multidimensional) verbunden.  ( http://www.calacademy.org/research/informatics/taf/proceedings/ballew/sld005.htm  - extrem hilfreich gewesen! )

[at]

Hallo.

hallo, warum heisst das eigentl. "binär- baum" für mich ist das ein "baum" objekt

Ja, und der Binärbaum ist nur eine dessen Sonderformen.
MfG, at

[vielfrager]

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 ?
Welches sind die Vorteile von rekursiver bzw nicht-rekursiver Traversierung?
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. (Folglich könnte ich mir vorstellen, das Schachprogramme eher nicht-rekursiv arbeiten, wenn ich das recht verstanden habe..)

Grüsse und danke für die prompten Antworten
vielfrager

[at]

Hallo.

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 ?!

Yep.

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 ?

Yep.

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

Der Vorteil der Rekursion liegt darin, dass du alles in einem Durchgang machen kannst, du also jede Stelle eines Verzeichnisses nur einmal durchsuchen musst. Die andere Methode zwingt dich entweder dazu mehrfach anzusetzen oder dir alle Stellen zu merken, and denen du in ein Unterverzeichnis wechseln kannst. Vorteilhaft kann dies sein, wenn die oberste Ebene sehr wenige Verzeichnisse enthält, die Unterverzeichnisse pro Verzeichnis aber von Ebene zu Ebene mehr werden und du dir sicher bist, dass die von dir gesuchte Datei relativ nah am Stammverzeichnis lag.

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. (Folglich könnte ich mir vorstellen, das Schachprogramme eher nicht-rekursiv arbeiten, wenn ich das recht verstanden habe..)

Komplexe Schleifen kombinieren gern beide Möglichkeiten, nutzen integrierte Sicherheitsmechanismen etc. Aber das führt doch ein wenig zu weit. Vielleicht hat ja noch jemand einen guten Buchtipp für dich.
MfG, at

[vielfrager]

OK, Danke, at.

vielfrager

[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!