Hey Leute,
Kann mir mal bitte jemand das „Postorder-system“ erklären.
Das ist sehr wichtig, ich schreibe morgen eine Klausur und glaube ich habe das nicht ganz verstanden.
vll. könnte mich ja jemand, der das erklären kann und nen moment Zeit hat mich ja mal bei ICQ anschreiben
ICQnr. : 311 883 082
Ansonsten könnt ihr ja bitte eine Antwort auf diesen Post schreiben.
Also ich möchte einfach erklärt haben, wie ich einen Binärbaum nach dem postorder-system ordne.
MFG:
Tobias M.
Holla.
Kann mir mal bitte jemand das „Postorder-system“ erklären.
Funktion Postorder(Baum)
W NULL //Existiert ein linker Unterbaum?
L NULL //Existiert ein rechter Unterbaum?
R
Diese rekursive Funktion sucht zunächst den linken, dann den rechten Ast des Binärbaums ab und **ganz am Schluß** die Wurzel. Deswegen ist die gelieferte Rückgabeliste im Postorder-Verfahren auch L,R,W.
Preorder dagegen liefert W,L,R und Inorder L,W,R.
Gruß Eillicht zu Vensre
Funktion Postorder(Baum)
W NULL //Existiert ein
linker Unterbaum?
L NULL //Existiert ein
rechter Unterbaum?
R
Diese rekursive Funktion sucht zunächst den linken, dann den
rechten Ast des Binärbaums ab und ganz am Schluß die
Wurzel. Deswegen ist die gelieferte Rückgabeliste im
Postorder-Verfahren auch L,R,W.
Das hab ich bei Wikipedia auch gefunden, aber das vestehe ich nicht tut mir leid!
Hallo,
Das hab ich bei Wikipedia auch gefunden, aber das vestehe ich
nicht tut mir leid!
Was genau verstehst du denn nicht?
Pre/In/Postorder sind einfach nur Möglichkeiten, jedes Element eines Baums zu besuchen.
Dabei geht man in allen Fällen von der Wurzel aus, und gibt z.B. jedes Element des Baums irgendwann auf den Bildschirm aus. Man besucht jeweils die beiden Unterbäume eines Elements, sowie die Daten, die darin gespeichert sind (Hat Eillicht iirc. „Wurzel“ genannt).
Schau dir diesen Baum hier an:
http://moritz.faui2k3.org/images/btree.png
Wenn du an einem Baum in Preorder durchläufst gibst du erst die Daten aus, und gehst dann erst in den linken, dann in den rechten Teilbaum.
Für die Ausgabe bedeutet das anschaulich, dass du von der Wurzel (oben) nach links unten läufst, dann ganz unten das zweite von links nimmst und dich so immer weiter nach rechts durcharbeitest.
Damit erhältst du als Reihenfolg der Elemente
1 2 4 5 3 5 7
In Postorder besuchst du erst den linken, dann den rechten Teilbaum und ganz am Ende gibts du die Daten aus.
D.h. für die Ausgabe bedeutet das, dass du ganz links unten im Baum mit dem ausgeben anfängst, dann das zweite Element von links, und dann den Knoten, der über den beiden Elementen liegt. Dann geht es wieder unten los, insgesammt kommt dabei heraus:
4 5 2 6 7 3 1
Wie man das rekursiv programmiert hat Eillicht ja schon geschrieben, geh das einfach Schritt für Schritt durch, dann verstehst du das schon.
Grüße,
Moritz
Hm…
Also unser Lehrer hat uns das irgendwie so erklärt,
Man hat einen Ungeordneten Baum und den kann man mit postorder „ordnen“
Dazu verschiebt man im right shell die großen „Namen/Zahlen“ aufwärts
und im left shell abwärts, nur irgendwie komm ich da nicht zu dem ergebniss zu dem ich kommen soll glaub ich und da dachte ich dass mir das jemand noch mal so … „excel like“ erklären kann,
also im unterricht haben wir in excel einen binärbaum „gemal“ und da die Namen reingeschrieben und dann sollten wir die mit postorder ordnen.
Das was ihr mir erklärt hört sich irgendwie nach was anderem an … oder weiß jemand was ich meine und kann mit dabei helfen??
Trotzdem danke für eure Hilfe und Gedult
MFG:
Tobias M.
