Wie löst man diese Aufgabe? Bereich: Informatik!?

Question

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.

Robert · Answer

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

5  -  1 4 [3] 11 2  -  3 8 10 6 [9] 
[3] 4 11 1 2  -  5  -  8 6 10 3 [9]

Zeile 1: 5 Wurzel
Zeile 2: die 5 (Wurzel) trennt links von rechts
Die Zahlen in den eckigen Klammern stehen ganz links oder rechts.

5  -  (1 4 [3]) 11 2  -  (3) 8 10 6 [9] 
[3] 4 11 (1) 2  -  5  -  8 6 10 (3) [9]

Zeile 1: (1 4 3) der Weg nach links; 11 und 2 zeigen nach rechts
Zeile 2: (3 9) der Weg nach rechts; 8 zeigt nach links

Für die linke Seite fehlen noch die 11 und die 2.
Die 11 steht in der zweiten Zeile links von der 1, also von der 4 nach rechts.
Die 2 steht links von der 5, also von der 1 nach rechts.

Für die rechte Seite fehlen noch die 10 und die 6.
In der ersten Zeile steht die 8 links der 10, also von der 8 nach rechts.
In der ersten Zeile steht die 6 rechts der 10 und in der zweiten Zeile umgekehrt.
Dadurch geht es von der 10 nach links zur 6.

5
           /     &#92;
        1          3
      /   &#92;      /   &#92;
    4       2  8      9
  /   &#92;          &#92;
3      11         10
                  /
                 6

5 - (1 4 3 11 2) - (3 8 10 6 9)

5 - (1 - (4 3 11) - 2) - (3 - (8 10 6) - 9)

5 - (1 - (4 - 3 - 11) - 2) - (3 - (8 - () - (10 6)) - 9)

5 - (1 - (4 - 3 - 11) - 2) - (3 - (8 - # - (10 - 6 - #)) - 9)

Das Zeichen "#" steht für einen leeren Zweig, wenn der andere belegt ist.
Die Klammern zeigen einen linken und einen rechten Zweig an, wobei die erste Zahl die Wurzel ist (von ober herkommend).

Wie löst man diese Aufgabe? Bereich: Informatik!?

1 Antwort