Inorder, Postorder

[Gratwanderer]

Hallo,

ich sitze gerade an folgender Aufgabe und würde gerne wissen ob meine Lösung richtig ist.

Gegeben ist die Inorder eines Binärbaumes mit

A,L,I,E,V,R,L,M,G,S

und die Postorder

L,A,E,I,L,G,M,S,R,V

Man soll nun den Baum rekonstuieren und die Preorder angeben.

Habe dazu folgendes raus:

___________V______________

__________ /_\_____________

_________ /___\____________

________ I____ R___________

_______ /_\_____\__________

_______A__E_____S_________

________\_______/__________

_________L_____M__________

______________/_\__________

_____________L___G_________

Die Preorder wäre somit

V,I,A,L,E,R,S,M,L,G

Ist das so richtig?

Gruß, Gratwanderer

Bearbeitet 12. Juli 2010 von Gratwanderer

[Klotzkopp]

Sieht gut aus.

[lupo49]

Wie konstruiert man den Baum denn aus den gegebenen Reihenfolgen?

Bearbeitet 12. Juli 2010 von lupo49

[Klotzkopp]

Wie konstruiert man den Baum denn aus den gegebenen Reihenfolgen?

In Postorder-Reihenfolge steht die Wurzel ganz rechts (V). Bei Inorder steht die Wurzel zwischen dem linken und dem rechten Teilbaum. Der linke Teilbaum besteht also aus A, L, I, E, der rechte aus R, L, M, G, S. Auf die Teilbäume wendet man dann dieselbe Vorgehensweise an.