Traversierung eines Baumes:

Hallo,

ich glabe, dass dies besser zur Mathematik passt, als zu "rund um die Programmierung".

Also, ich habe eine
Preorder Angabe: AEBDCFG

und

Inorder Angabe: BEDAFCG

Jetzt weiß ich, dass beide Angaben den selben Baum erzeugen sollen.
Über den Baum weiß ich, dass Jeder Knoten maximal 2 Söhne hat.
(Also ist leider auch kein oder ein Sohn möglich)

Ich kann zwar einen Baum erzeugen, indem ich so lange probiere, bis ich es richtig gemacht habe, aber das dauert zu lange!

Gibt es eine Formel dafür?
(Ich habe schon gegoogled aber nichts konkretes gefunden)

SG1

MisterX schrieb:

Preorder Angabe: AEBDCFG
Inorder Angabe: BEDAFCG

Die Wurzel des Baums ist A, da A in der Preorder-Darstellung ganz vorne steht. Unter dem A sind 2 Teilbäume, der eine bestehend aus den Knoten B, D und E, der andere aus C, G und F (links bzw. rechts vom A in der Inorder-Darstellung). Wie die Teilbäume aufgebaut sind, findest Du auf die gleiche Weise raus.

Hallo,

was mache ich denn, wenn ich andere Kombinationen habe:

preorder und inorder Angabe
preorder und postorder Angabe
postorder und inorder Angabe

Wie löse ich den das?

Gibt es irgendwo nen Skript oder sonstwas, wo ich das nachlesen kann?

Dommel

ich denke nicht, dass es da ne Formel oder ähnliches gibt. Aber eigentlich kommt man doch meist mit n bischen Überlegung drauf...

nman

MisterX schrieb:

preorder und postorder Angabe

Daraus kannst Du IMO keinen eindeutigen Baum rekonstruieren.

Ansonsten ist das nicht so schwer; wenn man weiß, wie Preorder, Postorder und Inorder ungefähr aussehen:

preorder(knoten)
{
    if (knoten==NULL)
        return;
    gib_aus(knoten.wert);
    preorder(knoten.links);
    preorder(knoten.rechts);
}

postorder(knoten)
{
    if (knoten==NULL)
        return;
    preorder(knoten.links);
    preorder(knoten.rechts);
    gib_aus(knoten.wert);
}

inorder(knoten)
{
    if (knoten==NULL)
        return;
    preorder(knoten.links);
    gib_aus(knoten.wert);
    preorder(knoten.rechts);
}

(Ich hoffe ich habe jetzt keinen Mist geschrieben. :))

@nman:

das währe schön, wenn das so einfach wäre, aber ich weiß nur, dass jeder Knoten im Baum maximal 2 Nachfolger hat. Also kann der auch 0 oder 1 nachfolger haben.

Aus diesem grund sind auch 2 Traversierungen angegeben, aus denen man (hoffentlich" eideutig EINEN Baum erzeugen soll.

Deine Algorithmen funktionieren leider nur bei einem Baum dessen Knoten GENAU 2 Nachfolger haben!

z.B habe ich den Baum zu meinem Beispiel gefunden:

Preorder Angabe: AEBDCFG

und

Inorder Angabe: BEDAFCG

Ponto

Mister X schrieb:

z.B habe ich den Baum zu meinem Beispiel gefunden:

Preorder Angabe: AEBDCFG

und

Inorder Angabe: BEDAFCG
A
                   / \
                  E   F
                 / \ / \
                B  D C  G

Der Baum Inorder traversiert ergibt BEDACFG und nicht BEDAFCG

Ponto

Du kannst rekursiv den Baum eindeutig nach folgender Vorschrift aufbauen:

tree build_tree( string inorder, string preorder)
{
  if (inorder.empty()) return empty_tree
  root = preorder[0]
  pos =  inorder.find(root)
  left_inorder = inorder[0..pos-1]
  right_inorder = inorder[pos+1..inorder.size()-1]
  left_preorder = preorder[1..1+left_inorder.size()]
  right_preorder = preorder[1+left_inorder.size()+1..preorder.size()-1]
  left_subtree = build_tree(left_inorder, left_preorder)
  right_subtree = build_tree(right_inorder, right_preorder)
  if (not left_subtree.empty()) root.append_left(left_subtree)
  if (not right_subtree.empty()) root.append_right(right_subtree)
  return root;
}

nman

MisterX schrieb:

Deine Algorithmen funktionieren leider nur bei einem Baum dessen Knoten GENAU 2 Nachfolger haben!

Das ist Blödsinn.
wenn ich preorder(knoten.links) für einen Knoten aufrufe der kein linkes Kind hat, dann wird ja NULL übergeben und der Aufruf bricht ab, daher sollte das durchaus eine brauchbare Pseudocode-Implementierung sein.