Hallo ich habe eine Frage. Angenommen, man kennt: inorder und preorder Durchlauf eines (Binär)baumes. Dann kann man ja den Baum eindeutig aufstelllen. Wie sieht es mit anderen Kombinationen aus, z.B: preorder / inorder. Wenn man diese beiden kennt oder auch postorder/inorder usw. kann man dann den Baum auich eindeutig festlegen?
Ein Binaerbaum kann eine Menge Formen haben. Reden wir von einem sortierten und balancierten Binaerbaum ? Dann sollt's fuer jede Sortierung nur eine Form geben.
Das ist eine Frage aus dem Uni Grundstudium 1. oder 2. Semester Praktische Informatik. Die Antwort kenne ich auch nicht mehr auswendig. Aber dazu steht mit Sicherheit etwas in der einschlägigen Literatur, also ab in die Uni Bibliothek ;-)
(Auch_schon_lange_von_der_Uni_weg_aber_trotzdem_antwortender) Ist es nicht so, dass ein preorder oder postorder Darstellung alleine auch schon ausreicht und man nur bei inorder ein Problem hat? Ich denke jetzt bei 'Baum' an arithmetische Ausdrücke. Bei Inorder 2 + 3 * 5 gibt es ja die Möglichkeiten + * / \ / \ 2 * + 5 / \ / \ 3 5 2 3 die dann entweder mit dem Zusatzwissen (Punkt vor Strich) bzw. durch die Einführung von Klammern in der Inorder Version klargestellt werden müssen. Die Pre-Order Version + 2 * 3 5 bzw. * + 2 3 5 sind aber eindeutig. Selbiges für die Post-Order Versionen 2 3 5 * + bzw. 2 3 + 5 * So ein einzelnes Beispiel ist natürlich kein Beweis sondern eher mal ein Denkanstoss.
@Karl heinz Buchegger: Bei dieser Art Aufgabenstellung hat man normalerweise keine Markierung der Blaetter. Innere Knoten und Blaetter sehen in der Traversierung also identisch aus, wodurch die Eindeutigkeit verloren geht. Dein pre-order-Beispiel + 2 * 3 5 koennte auch zu folgendem Baum gehoeren: + / \ 2 5 / \ * 3 Syntaktisch ist das natuerlich kein korrekter Ausdruck (Multiplikation als Blatt), aber als Binaer-Baum sehr wohl moeglich.
Hi, danke für Eure Mühe ! Ja, genau das ist aus dem Fach Praktische Informatik, schreibe am Donnerstag darin eine Klausur. Ich habe die Aufgabe jetzt eigentlich verstanden.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.