(Binär)baum aufstellen

[jochen (Gast)]

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?

[6638 (Gast)]

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.

[Ulli (Gast)]

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 ;-)

[Karl H. (kbuchegg)]

(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.

[Christoph _. (chris)]

@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.

[jochen (Gast)]

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.