Veröffentlicht 5. Februar 200718 j 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?
5. Februar 200718 j 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.
5. Februar 200718 j Danke für die Hilfe. Wie wäre es denn, wenn nur das Pre-Order vorgegeben ist? Oder geht das alleine nicht?
5. Februar 200718 j Danke auch hierfür. Hätte noch eine Frage bezüglich Quicksort. Kannst du mir erklären wie der Quicksort funktioniert?
5. Februar 200718 j Quicksort - Wikipedia Für weitere Fragen mach aber bitte einen neuen Thread auf. Ein Thema - ein Thread
Archiv
Dieses Thema wurde archiviert und kann nicht mehr beantwortet werden.