Baum aus geg. pre- und inorder < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:14 Mi 09.05.2007 | | Autor: | RalU |
| Aufgabe | Gegeben sei für einen Baum t:
preorder(t)=<10,3,1,4,2,9,7,5,8>
inorder(t)=<3,4,1,10, 9,7,2,8,5>
Konstruieren Sie einen Baum t aus dieser Information. |
Ok, was ich weiß, ist natürlich der oberste Knoten, nämlich 10.
Und preorder funktioniert so: <W - LT - RT>
inorder funktioniert so: <LT, W, RT>
Mein Problem ist, dass ich aus der gegebenen Preorder einen eigenen Baum erstellen kann, der dann aber nicht mit der gegebenen inorder überinstimmt.
Als "preorder-Baum" hätte ich da stehen:
10
3 9
1 4 7 8
2 5
Aber so müsste das erste Element meiner inorder 1 sein, oder?
Was mach ich falsch? Hat jemand einen Tipp für mich?
Mit freundlichem Gruß, Ralf
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:30 Do 10.05.2007 | | Autor: | Frank05 |
> Gegeben sei für einen Baum t:
> preorder(t)=<10,3,1,4,2,9,7,5,8>
> inorder(t)=<3,4,1,10, 9,7,2,8,5>
>
> Konstruieren Sie einen Baum t aus dieser Information.
> Ok, was ich weiß, ist natürlich der oberste Knoten,
> nämlich 10.
Gut und nun weißt du auch, dass in der inorder Liste die 10 gerade die Werte trennt, die im linken und im rechten Teilbaum darunter stehen müssen. Für den linken Teilbaum bleiben also nur die Werte 3,4,1 (die 2 aus deinem Beispiel kann deshalb schonmal nicht auf die linke Seite gehören).
Um nun diese drei Werte in die richtige Baumstruktur zu bringen sehen wir uns wieder die Preorder-Liste an. Hier kommt als erstes die 3, was uns sagt, dass diese die Wurzel des Teilbaums bildet. Wir haben also die 10 in der Wurzel und links darunter die 3.
Wieder zurück bei der inorder-Liste stellen wir fest, dass die 3 dort vor 4 und 1 kommt. Wie ist das bei einem inorder Durchlauf möglich, wenn die 3 doch in der Wurzel steht? Genau: Es gibt unter der 3 keinen linken Teilbaum. Damit müssen die 4 und 1 beide im rechten Teilbaum unter der 3 liegen.
Und wieder einen Blick auf die preorder-Liste werfen: Erst 1 dann 4 sagt uns, dass die 1 die Wurzel des rechten Teilbaums unter der 3 sein muss.
Zurück bei der inorder-Liste erfahren wir, dass die 4 vor der 1 kommt, was bedeutet, dass sich die 4 im linken Teilbaum unter der 1 befinden muss. Da sie an dieser Stelle die letzte Zahl ist bildet die 4 hier ein Blatt und die Zahlen im linken Teilbaum unter der 10 sind alle zugeordnet:
| 1: |
| | 2: | 10
| | 3: | / \
| | 4: | 3 ...
| | 5: | / \
| | 6: | _ 1
| | 7: | / \
| | 8: | 4 _
|
Viel Spaß nun mit dem rechten Teilbaum 
|
|
|
|
