Wie rekonstruiere ich einen Baum mit Pre- und Inorder?

[BlueMoon92]

Hallo,

ich habe eine Aufgabe mit den Werten von Pre-Order und In-Order bekommen und weiß nicht, wie ich den Baum rekonstruieren kann. Ich weiß, dass der erste Wert von Pre-Order der Wurzel ganz oben sein soll, also die 5. Dadurch das ich den Wurzel habe, kann ich dann auch die Einteilung bei In-Order machen, also alles was links von der 5 ist, gehört zum linken Teilbaum und alles, was rechts von der 5 ist, gehört zum rechten Teilbaum. Wie gehe ich aber dann weiter vor?

Aufgabe: Rekonstruiere diesen Baum:

Pre-Order (W–L–R): 5 1 4 3 11 2 3 8 10 6 9

In-Order (L-W-R): 3 4 11 1 2 5 8 6 10 3 9

Mein bisheriger Ansatz:

Hauptwurzel (ganz oben): 5

Linker Teilbaum: 3 4 11 1 2

Rechter Teilbaum: 8 6 10 3 9

Das ist keine Hausaufgabe. Ich will das nur erklärt bekommen, damit ich es in der Klausur lösen kann. Würde mich über Hilfe freuen.

[flashpixx]

Ist zwar schon etwas älter, aber anbei noch die Hilfestellung: Binärbaum

Die 3 Traversierung (pre-, in- und post-Order) sind im Grunde von der Art des Durchlaufens durch den Baum gleich. Das was sie unterscheidet ist, wann das "print" / die Ausgabe des Inhaltes des Kontens aufgerufen wird.

Bei Pre-Order geben wir direkt, wenn man in einen Knoten hineingeht das Element als erstes aus und dann durchläuft man die unterhalb hängenden Teilbäume. Bei in-Order gehe ich in einen Knoten hinein, durchlaufe den linken Teilbaum, gebe das Element aus und dann durchlaufe ich den rechten Teilbaum.

Mein Tipp: Einmal den Baum aufmalen und dann würdest Du bei Pre-Order direkt die erste Zahl in das oberste Element schreiben und danach gehst Du in das linke Element unter der Wurzel und arbeitest Dich rekursiv durch. Bei der In-Order gehest Du zuerst an das tiefste linkeste Blatt und trägst dort die Zahl ein und dann steigst Du ein Element auf trägst dort die Zahl ein und gehst in den rechten Teilbaum komplett hinunter und arbeitest dann rekursiv durch.