Preorder eines Baumes

[Amtrak2004]

Hallo,

habe ein Problem mit Preorder und Inorder-Folgen

Folgende Aufgabe haben wir bekommen:

Zeichnen Sie den Binärbaum, der durch die folgenden zwei Folgen beschrieben ist:

Preorder-Folge: x1 x2 x3 x4 x5 x6 x7 x8

Inorder-Folge: x2 x4 x3 x1 x6 x5 x7 x8

Wie muss der Baum zu dieser Aufgabe aussehen??

Und woran erkenne ich, was wo in dem Baum angeordnet sein muss?

[Klotzkopp]

Die 1 ist der Wurzelknoten, weil sie bei Preorder an erster Stelle steht. Der linke Teilbaum besteht aus 2, 3 und 4, weil die in bei Inorder vor der 1 stehen, der rechte Teilbaum aus 5, 6, 7 und 8.

Die jeweils ersten Knoten dieser Teilbäume in Preorder sind die Kindknoten von 1, also links 2 und rechts 5.

Die 2 hat in ihrem Teilbaum keinen Vorgänger in Inorder, also hat sie keinen linken Kindknoten. Der rechte Teilbaum enthält also 3 und 4. Der erste Knoten von diesen beiden in Preorder ist der rechte Kindknoten von 2, also 3.

Und da 4 bei Inorder vor der 3 steht, muss 4 der linke Kindknoten von 3 sein.

Für 5, 6, 7 und 8 geht das analog.

[Amtrak2004]

Danke für die Hilfe.

Wie wäre es denn, wenn nur das Pre-Order vorgegeben ist? Oder geht das alleine nicht?

[Klotzkopp]

Nein, du brauchst schon beide Informationen, um den Baum zu rekonstruieren.

[Amtrak2004]

Danke auch hierfür. Hätte noch eine Frage bezüglich Quicksort.

Kannst du mir erklären wie der Quicksort funktioniert?

[Klotzkopp]

Quicksort - Wikipedia

Für weitere Fragen mach aber bitte einen neuen Thread auf. Ein Thema - ein Thread