Aerin - So 10.12.06 15:32
Titel: DFS bzw preorder Durchlauf

---

Ich suche ja hier [http://www.delphi-forum.de/topic_Minimalen+binaeren+Spannbaum+bestimmen_67368.html&sid=39ea5a9b40f26778822f230c8f5db577] nach einer Lösung um einen minimalen binären Spannbaum zu finden, da allerdings noch keiner eine Lösung beschrieben, hat wollte ich mal anders an das Problem herangehen. Ich brauche den binären Baum eigentlich nur, weil ich einen Preorder Durchlauf machen will.
Da kam mir grade die Idee, ist es vielleicht möglich einen Preorder Durchlauf für einen nicht binären Baum zu machen?

Heiko - So 10.12.06 15:52

---

@Spannbaum: Dir schon einmal die beiden Algorithmen [http://de.wikipedia.org/wiki/Spannbaum] angeguckt von Prim [http://de.wikipedia.org/wiki/Algorithmus_von_Prim] bzw. von Kruskal [http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal] angeguckt?

@Preorder: Na klar geht das. Erst die Wurzel ausgeben und danach die Kindern von rechts nach links durchgehen. Inorder würde nicht richtig gehen, da man ja nich wüsste, wann die Wurzel ausgegeben werden soll... .

Aerin - So 10.12.06 16:01

---

Heiko hat folgendes geschrieben:

@Spannbaum: Dir schon einmal die beiden Algorithmen [http://de.wikipedia.org/wiki/Spannbaum] angeguckt von Prim [http://de.wikipedia.org/wiki/Algorithmus_von_Prim] bzw. von Kruskal [http://de.wikipedia.org/wiki/Algorithmus_von_Kruskal] angeguckt?

ja, den minimalen spannbaum zum graphen findet mein programm schon, und zwar mit kruskal.
das problem war nur das der nicht binär ist, aber wenn ich für dfs keinen binären baum brauch, dann ist das ja egal;)

Heiko hat folgendes geschrieben:

@Preorder: Na klar geht das. Erst die Wurzel ausgeben und danach die Kindern von rechts nach links durchgehen. Inorder würde nicht richtig gehen, da man ja nich wüsste, wann die Wurzel ausgegeben werden soll... .

gut, so hatte ich mir das auch gedacht (nehme mal an das rechts nach links is nen tippfeheler uns soll links nach rechts heißen?).
dann sollte der graph ja so durchlaufen werden oder (angenommen die wurzel hat 4 söhne) ?:
wurzel, linken teilbaum, halblinken teilbaum, halbrechten teilbaum, rechten teilbaum

Gausi - So 10.12.06 16:08

---

Ist es wichtig, welcher Teilbaum links oder "halblinks" ist? Wie wird das überhaupt festgestellt? Bei nem binären Suchbaum ist das klar, aber was hast du da für eine Struktur, bzw. was für Daten liegen an den Knoten?

Heiko - So 10.12.06 17:02

---

So hier noch einmal den Post,. den ich vor Gausi geschrieben hatte, aber im flaschem Threag (hab bei den ganzen FF-Tabs nicht mehr durchegesehen ;) ):

Wikipedia hat folgendes geschrieben:

Es gibt verschiedene Möglichkeiten, die Knoten von Binärbäumen zu durchlaufen. Man unterscheidet hier in * pre-order (W–L–R): wobei zuerst die Wurzel (W) betrachtet wird und anschließend zuerst der linke (L), dann der rechte (R) Teilbaum durchlaufen wird, * in-order (L–W–R): wobei zuerst der linke (L) Teilbaum durchlaufen wird, dann die Wurzel (W) betrachtet wird und anschließend der rechte (R) Teilbaum durchlaufen wird und * post-order (L–R–W): wobei zuerst der linke (L), dann der rechte (R) Teilbaum durchlaufen wird und anschließend die Wurzel (W) betrachtet wird. * level-order Beginnend bei der Wurzel, werden die Ebenen von links nach rechts durchlaufen.

Bei 4 SubNodes der Wurzel (und Kind1 hat 2 SubNodes) würde es so aussehen

Wuzel :arrow: Kind_1 :arrow: Kind_1_1 :arrow: Kind_1_2 :arrow: Kind_2 :arrow: Kind_3 :arrow: Kind_4

Jack Falworth - So 10.12.06 21:38

---

in diesem Skript SML-Skript [http://www.ps.uni-sb.de/~smolka/Programmierung/2006-11-07.pdf] wird u.a. Bäume sehr gut abgehandelt. Kapitel 7 geht über Bäume (Ordnung, Begriffe, etc.) auch mit Beispielen und Bildern. Das sollte dir weiterhelfen.

Gruß JackF