In-/ Preorder

  • beispiel aus dem prüfungsordner:


    preorder-reihenfolge: c, k, g, a, l, d, b
    inorder-reihenfolge: k, c, d, l, a, b, g


    a) den dazugehörigen baum konstruieren
    b) postorder-reihenfolge?


    wie geht das? irgendwie widerspricht sich da meiner meinung nach in- und preorder, hab keine ahnung wie der baum ausschauen könnte.

  • finde hier keinen widerspruch!


    Wurzel: c
    k--------------d l a b g
    nächste Ausgabe laut PreOrder: k stimmt (muss so sein) weil nach der Ausgabe der Wurzel mit linkem Kind rek. aufgerufen wird - k wird ausgegeben - keine Kinder eine RekStufe nach oben rechtes Kind der Wurzel = g
    -----c
    k-----------------g
    --------d l a b
    .....usw.


    Ergebnis:
    -----c
    k---------------g
    ------------a
    ---------l------b
    -----d



    PostorderReihenfolge: k d l b a g c


    hoffe ich hab mich nirgends vertan.....

  • ich hab hier als postorder -reihenfolge:


    k, d, l, b, a, g, c


    und wie du den Baum aufbaust, versuch da jetzt mal zu erklären, so gut es halt geht:


    in der preorder-aufzählung (po) ist die erste Zahl immer die Wurzel. Danach kommen die Element die links stehn, als hier mal k.
    wennst in die inorder-aufzählung (io) schaust, siehst du, dass nur das k vorm c steht, also nur das k links vom c ist. also hast du den linken Teilbaum von c schon fertig.


    jetzt geht's in den rechten. g ist die nächste root. in der IO siehst du, dass alle anderen Elemente vorm g stehn, d.h. alle anderen sind link von g im Baum. (definition von IO: leftchild, root, rightchild)
    a ist die nächste root laut PO. in der IO siehst du, dass d und l vorm a stehn, also links vom a im Baum sind. usw...bis du siehst, dass laut IO kein Element mehr links vom d is, also is d ganz unten und alle bisherigen Buchstaben sind die roots darüber.
    Dann is noch da b übrig. Weil das in der IO noch vorm g kommt aber nach dem a, ist es ein rechtes Kind von a.
    fertig.


    Ich weiß nicht, obs eine einfachere Methode gibt, diese hab ich mir halt irgendwie selbst aus den Definitionen zusammengebastelt. und sie funktioniert. :D


    lg, Geli

  • widerspricht sich meiner meinung nach nicht.. der baum sieht so aus:


    knoten | Kinder
    c | k,g
    k | -,-
    g | a,-
    a | l,b
    l |d,-
    d |-,-
    b | -,-


    mfg Chris

  • :D da war ich ja gerade noch der schnellste und die PostorderReihenfolge scheint auch zu stimmen......
    denn ich denke nicht dass GELI ihr Posting in einer Minute verfasst hat und dabei meine Reihenfolge abgeschrieben hat ;)

  • ich schaffe es auch nicht... vielleicht ist es kein binärer baum... wie lautet die angabe genau? bhuu so viele antworten als ich das geschrieben hab... sollte mir vorher die antworten durchlesen. ok bin mit den antworten einverstanden...
    wahnsinn wie schnell ihr alle posten könnts :)

  • ups. hab wohl zu langsam geschrieben.. ;)


    aber postorder hab ich selbständig auch dasselbe rausbekommen, dass sollt also auch passen