Suchbaum Postorder zeichnen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:22 Mo 07.02.2011 | | Autor: | bobbert |
| Aufgabe | Gegeben sei die Postorder-Traversierung eines Suchbaums:
8 25 32 33 31 27 35 36 41 34
Zeichnen Sie den zugehörigen Baum. |
Musterlösung: syntax_tree.png
Ich weiß wie man mit Inorder und Postorder zusammen sich den Baum erschließen kann, allerdings weiß ich nicht wie das nur mit Post order geht. Natürlich weiß ich das das letzte Eleement die Wurzel sein muss da Postorder LRW ist. Wie komme ich aber auf die übrigen glieder , wenn es hier keine größer kleiner unterteilung gibt?
Vielen Dank im VOraus!
Dateianhänge:
Anhang Nr. 1 (Typ: png) [nicht öffentlich]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:13 Mo 07.02.2011 | | Autor: | felixf |
Moin!
> Gegeben sei die Postorder-Traversierung eines Suchbaums:
> 8 25 32 33 31 27 35 36 41 34
> Zeichnen Sie den zugehörigen Baum.
> Musterlösung: syntax_tree.png
>
> Ich weiß wie man mit Inorder und Postorder zusammen sich
> den Baum erschließen kann, allerdings weiß ich nicht wie
> das nur mit Post order geht. Natürlich weiß ich das das
> letzte Eleement die Wurzel sein muss da Postorder LRW ist.
> Wie komme ich aber auf die übrigen glieder , wenn es hier
> keine größer kleiner unterteilung gibt?
Du weisst, dass es ein Suchbaum ist. Es ist also nicht nur das linke Kind kleiner als die Wurzel, sondern auch alle Kinder davon etc. Ebenso fuer den rechten Teilbaum.
Damit und mit der Postorder kannst du den Baum rekonstruieren.
Der Baum, den du angehaengt hast, stimmt auch.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 12:07 Di 08.02.2011 | | Autor: | bobbert |
KK verstehe , vielen Dank felixf!
Also hier eine Anleitung (für die die es interessiert):
gegeben:
Postorder Traversierung : 8 25 32 33 31 27 35 36 41 34
1) Wurzel finden : Post order LRW=> äußerstes Element (34)
34
2) Da Suchbaum li<W>re : Alle Elemente kleiner W (hier 34) auf den linken Teilbaum(8 25 32 33 31 27) , alle größer auf den rechten (35 36 41)
3) Wiederhole Schritte 1 + 2 bis keine Zahl mehr vorhanden
Lösung: siehe Bildanhang
links Wurzel rechts
1 ) 8 25 32 33 31 27 [34] 41 36 35
2)8 25 [27] 32 33 31 [34] 41 36 35
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Do 10.02.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
