mikrocontroller.net

Forum: Offtopic (Binär)baum aufstellen


Autor: jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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?

Autor: 6638 (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Ulli (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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 ;-)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
(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.

Autor: Christoph __ (chris)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@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.

Autor: jochen (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Yahoo-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.