Binärbäume < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
ich habe ein Problem mit einer Aufgabe: es geht um die Zeichnung eines Binärbaums, der als preorder-Ausgabe „ANUPSIDEDOWNTREE“ erzeugt und UNPADIESDNWTOERE“ als inorder-Ausgabe erzeugt.
Lösung ist unter folgendem Link:
http://img89.imageshack.us/img89/152/67253497.png
So und jetzt mein Problem: ich bin zu schwach an Verstand, um herzuleiten, wie man von der gegebenen Aufgabenstellung auf diese Lösung kommt.
Kann mir das Jemand erklären bzw. auf ein passendes Dokument verweisen, damit ich es vielleicht doch noch kapiere.
Gruß
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Noch mal PS: was soll der Quatsch?
|
|
| |
|
Hio!
Also leider kann ich Dir kein "Musterrezept" nennen, um solche Aufgaben zu lösen, aber ich kann Dir folgende Hilfestellung geben:
Schaue Dir mal die Implementierung von Inorder und Preorder an:
Beim Preorder-Durchlauf z.B. wird die Wurzel zuerst ausgegeben, dann der linke und danach der rechte Teilbaum
Das heißt zu Beginn der Ausgabe von Preorder steht immer die Wurzel Deines Baumes und das nächste Zeichen/Zahl ist der linke Nachbar davon.
Damit hättest Du schonmal A und N geklärt. Nun kommt bei der Preorder-Ausgabe 'U'. Das ist das erste Zeichen der Ausgabe von Inorder. Inorder gibt immer das linkeste Element eines Baumes als erstes zurück (bzgl. einer Ordnungsrelation ist das das kleines Element im Baum), d.h. 'U' muss irgendwo ganz links stehen.
Darum weißt Du, dass 'U' der linke Nachfolger von 'N' ist und, dass danach keine linken Nachfolger mehr kommen.
Nun kommt beim Preorder 'P' als nächstes. Diese 'P' könnte der rechte Nachfolger von 'U' oder 'N' sein (beachte, zu einem Preorder-Durchlauf kann es immer mehrere Bäume geben, die dieselbe Preorder-Ausgabe liefern)
Um die Position wieder eindeutig zu bestimmen, schaust Du Dir nun wieder Inorder an, dort steht "UNP", d.h. P muss der rechte Nachfolger von N sein (gemäß der "Definition" von Inorder)
So kannst Du Dich immer weiter durch den Baum hangeln. Preorder gibt Dir einen Anfang und von dort aus mehrere Möglichkeiten,wie der Baum aussehen kann. Durch Inorder bekommst Du dann genau die Möglichkeit, die für Deine beiden Ausgaben passend sind.
Hoffe das hilft Dir,
Pille
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:21 Mi 05.01.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
