inorder vs. preorder vs. postorder (oder: zu blöd für wikipedia)

[AoM]

Hallo.

Ich verstehe einfach inorder vs. preorder vs. postorder nicht.

wikipedia habe ich schon probiert.

Insbes. beisse ich mich an folgender Aufgabe fest (Lösung bekannt, aber nicht Lösungsweg)

Der Inorder-Durchlauf eines binären Baums liefert folgende Reihenfolge der Knoten:

A, D, C, G, B, H, E, F, I

Der Preorder-Durchlauf desselben binären Baums liefert folgende Reihenfolge der Knoten:

C, D, A, F, G, H, B, E, I

Geben Sie die Reihenfolge der Knoten an, die sich bei einem Postorder-Durchlauf durch diesen binären Baum ergeben.

Mir gelingt es schon gar nicht, den Baum zu zeichnen, denn ich komme zu zwei verschiedenen Bäumen, je nachdem welche Durchlaufsreihenfolge ich zum Zeichnen verwende :confused:

Relativ sicher scheint mir zu sein, dass C die Wurzel ist, da sie beim preorder-Durchlauf vorn ist (und - in der Postorder-Lösung - ganz hinten).

Relativ sicher scheint mir zu sein, dass der linke Teilbaum aus D und A besteht (falls Wurzel oben in der Zeichung ist A das unterste Element, oder)

Das Problem ist der rechte Teilbaum bzw. mein mangelndes Verständnis von

inorder vs. preorder vs. postorder :confused::beagolisc:eek

Kann mir jemand den Baum zeichnen, bzw. die Postorder-Reihenfolge ( A, D, B, E, H, G, I, F, C ) erklären?

Danke & Tschüß

[flashpixx]

schau Dir doch mal den Pseudocode unter Binärbaum ? Wikipedia an (die Traversierung ist wirklich sehr gut erklärt)

Kann mir jemand den Baum zeichnen, bzw. die Postorder-Reihenfolge ( A, D, B, E, H, G, I, F, C ) erklären?

Nein, denn damit mache ich Deine Arbeit

Phil

[kingofbrain]

Servus,

also ich habe versucht, auf eine Lösung zu kommen - allerdings ist mein Wissen über B-Bäume aus dem Studium ein wenig eingeschlafen. Ich habe allerdings auch keine Lösung gefunden, die beide gegebenen Ordnungen widerspiegelt.

Ich denke auch nicht, dass der Threadersteller hier seine Hausaufgaben gelöst haben möchte. Dazu hat er schon zu viel Engagement gezeigt.

Ich komme mit der Angabe so weit:

Wurzel: C, Kind links: D, Kind rechts: F

D, Kind links: A, Kind rechts: none

F, Kind links B oder G; Hier stecke ich fest und denke, dass die Angabe falsch ist. Aber besser ist es, wenn noch jemand, dessen Baumwissen frischer ist, drüber schaut.

Peter

[flashpixx]

So wie ich das sehe, geht beides nicht, denn:

es sind je 9 Elemente (Knoten + Blätter) und ich damit keinen vollbesetzten B-Baum erzeugen, denn entweder müssten es 7 bzw 15 Elemente sein, d.h. 3 Knoten und 4 Blätter oder 7 Knoten und 8 Blätter.

Es fehlt hier die Information, ob es leere Blätter geben kann / darf und / oder ob nur die Blätter bzw. Knoten eine Bezeichnung tragen

HTH Phil

P.S.: die Problematik, die Du (@kingofbrain) beschreibst kommt nämlich daher

[kingofbrain]

Servus,

ich denke, es ist bei dieser Art von Aufgabe die Grundvoraussetzung, dass der Baum nicht voll besetzt ist. Ansonsten wäre sie zu einfach zu lösen. Ich habe mir diese Wikipedia-Seite angesehen, um mein Wissen aufzufrischen, und dort ist etwas ähnliches auch mit einem unvollständig gefüllten Baum zu sehen: Tree traversal - Wikipedia, the free encyclopedia

Peter

[bpfitzner]

Bei dieser Aufgabe muss man aus dem Inorder- UND dem Preorder-Durchlauf den binären Baum bilden. Nur anhand eines Inorder- oder Preorder-Durchlaufes lässt sich kein eindeutiger Baum ermitteln.

(Bin auch erst durch den Hinweis einer Mitstudentin draufgekommen)

Somit sollte sich dann folgender Baum ergeben:

___________C_________________

__________ /_\_______________

_________ /___\____________

________ D____ F______________

_______ /____ /__\_____________

_______A____G___ I___________

_____________\_____________

______________H_____________

_____________ / \_____________

_____________B__E___________

Bei diesem Baum erhalte ich beim Postorder-Durchlauf die Folge:

A-D-B-E-H-G-I-F-C

Bitte korrigiert mich falls ich irgendwo falsch liege.

Bearbeitet 7. August 2008 von bpfitzner

[kingofbrain]

Sehr cool, das sieht sehr richtig aus. ich bin bei dem G gehangen, weil ich dort nicht daran gedacht habe, dass es statt einer linken auch eine rechte ohne eine linke Seite geben kann.

Peter

[SoL_Psycho]

*applaudiert bpfitzner*

[Klotzkopp]

Bei dieser Aufgabe muss man aus dem Inorder- UND dem Preorder-Durchlauf den binären Baum bilden. Nur anhand eines Inorder- oder Preorder-Durchlaufes lässt sich kein eindeutiger Baum ermitteln.

Richtig.

Bitte korrigiert mich falls ich irgendwo falsch liege.

Nein, das sieht gut aus.

Die Vorgehensweise ist eigentlich ganz einfach. Man benutzt die Preorder-Reihenfolge, um den Wurzelknoten zu ermitteln (im ersten Schritt C), denn der steht bei Preorder immer am Anfang. Dann ermittelt man mit der Inorder-Reihenfolge die Teilbäume (denn da steht die Wurzel dazwischen). Also haben wir im ersten Schritt AD im linken und GBHEFI im rechten Teilbaum. Damit verfährt man jetzt genauso weiter wie im ersten Schritt.

[Panke]

Ein Binärbaum und ein B-Baum sind zwei versch. paar Schuhe. Nur um Mißverständnissen vorzubeugen.