[FRAGE] - In-/ Preorder
Results 1 to 7 of 7

Thread: In-/ Preorder

  1. #1

    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    185
    Thanks
    0
    Thanked 0 Times in 0 Posts

    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.

  2. #2
    Länz's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.....
    Last edited by Länz; 21-05-2002 at 18:22.

  3. #3

    Title
    Principal
    Join Date
    Feb 2002
    Location
    Wien 23
    Posts
    50
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

    lg, Geli

  4. #4

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    Last edited by Chris; 21-05-2002 at 18:23.
    hi, i'm a signature virus. copy me into your signature to help me spread.

  5. #5
    Länz's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    78
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

  6. #6
    Walter Huber's Avatar
    Title
    Elite
    Join Date
    May 2002
    Posts
    387
    Thanks
    11
    Thanked 5 Times in 3 Posts
    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
    Last edited by Walter Huber; 21-05-2002 at 18:35.

  7. #7

    Title
    Elite
    Join Date
    Jan 2002
    Posts
    314
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ups. hab wohl zu langsam geschrieben..

    aber postorder hab ich selbständig auch dasselbe rausbekommen, dass sollt also auch passen
    hi, i'm a signature virus. copy me into your signature to help me spread.

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •