|
Anzeige
|
(Binär)baum aufstellen
Gast
#796187
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?
Gast
#797580
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.
Gast
#797596
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.
Gast
#797995
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. Antwort schreibenBitte melde dich an, um einen Beitrag zu schreiben. |
Anzeige
|
