Preorder - Postorder < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Ein binärer Suchbaum ist nur eindeutig rekonstruierbar, wenn seine Post-/Preorder UND Inorder Darstellung gegeben ist.
Geben sie Gegenbeispiele an, die zeigen, dass binäre Suchbäume nicht eindeutig rekonstruierbar sind, wenn NUR die Postorder- UND Preorderdarstellung gegeben ist. |
Hi Leute!
Wie versteht ihr die Aufgabe?
Ich kann mir doch da irgendwelche Bäume konstruieren, oder? Ich meine damit, dass es doch dann egal ist welche Bäume ich zeichne, oder? Oder ist diese Uneindeutigkeit wieder nur bei bestimmten Fällen gegeben?
Ich hab mir natürlich dazu schon Gedanken gemacht:
Preorder und Inorder bzw. Postorder und Inorder sind eindeutig, da Inorder den linken bzw. rechten Unterbaum zeigt und die Pre- bzw. Postorder die Wurzel eindeutig festlegt.
Preorder und Postorder ist nicht eindeutig, da Trennung in linken bzw. rechten Unterbaum, die zuvor durch Inorder festgelegt wurde, fehlt. Bei einzelnen Blättern ist also unklar, ob sie links oder rechts hängen.
Könnt ihr mir weiterhelfen?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Do 17.05.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
