pre-post-in-order

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
davidx

pre-post-in-order

Beitragvon davidx » Donnerstag 29. Januar 2004, 16:30

kann mir jemand den quellcode für diese drei arten (pre-post-in-order) eine baum zu durchlaufen geben/posten?
MfG

was ich bisher gefunden habe ist:

Code: Alles auswählen

def preorder(tree):
    if tree:
        yield tree[0]
        for e in preorder(tree[1]):
            yield e
        for e in preorder(tree[2]):
            yield e

def postorder(tree):
    if tree:
        for e in postorder(tree[1]):
            yield e
        for e in postorder(tree[2]):
            yield e
        yield tree[0]

def inorder(tree):
    if tree:
        for e in inorder(tree[1]):
            yield e
        yield tree[0]
        for e in inorder(tree[2]):
            yield e


aber das vestehe ich nicht. kann mir das jemand (alternativ) erklären?
MfG
Benutzeravatar
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Beitragvon Dookie » Donnerstag 29. Januar 2004, 16:55

Hi davidx,

könnte sicher wer, wenn Du erstens den Code in Code-Tags einschließt und 2. sagst wie der Baum aufgebaut ist, als Liste oder mit einer eigenen Klasse?


Gruß

Dookie
Milan
User
Beiträge: 1078
Registriert: Mittwoch 16. Oktober 2002, 20:52

Beitragvon Milan » Donnerstag 29. Januar 2004, 17:27

Code Tags hab ich jetzt mal gesetzt (bitte beim nächsten mal benutzen @davidx). Allerdings kann ich auch nicht helfen, da es wie gesagt an Informationen mangelt.
Benutzeravatar
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Beitragvon Dookie » Donnerstag 29. Januar 2004, 17:52

Hallo nochmal,

also, ein Baum enthält ein Element und zwei Referenzen auf einen linken und einen rechten Teilbaum, diese Referenzen könne auch None sein, wenn keine abzweigung in diese Richtung geht.

Bei preorder wird zuerst das Element des Baumes zurückgegeben, dann kommt erst der linke Teilbaum (wenn nicht None), der ebenso verfährt und dann der rechte Teilbaum (wenn nicht None).

Bei postorder wird zuerst der linke Teilbaum angesprochen, dann der rechte und zum Echluss das eigene Element zurückgegeben.

Bei inorder kommt zuerst der linke Teilbaum, dann das eigene Element zurückgegeben und dann kommt der rechte Teilbaum drann.


Gruß

Dookie
thx@Milan für die Tags.
davidx

Beitragvon davidx » Donnerstag 29. Januar 2004, 23:02

oh sorry, ich hätte den source in diese tags zwängen sollen sorry.
zudem habe ich mich wirklich ungünstig ausgedrückt. was pre-, post-, und in- order ist ist mir klar allerderings die realisierung in phython nicht.

z.B. ist mir der in "meinem" source angegebene begriff yield nicht klar. ich weiß - ist kein python begriff sondern willkürlich gewählt aber vielleicht kann es mir trotzdem jemand erklören ggf. den richtigen code hinschreiben.

betreffemd des baumes:
sei B ein binärer baum. jeder knoten hat also zwei zweige, notfalls
none-zweige.

wie ist ein durchlauf zu realisieren der alle elemente des baumes in der gegebenen order (siehe oben) ausgibt? thx

alles klar?
mfg davidx
davidx

Beitragvon davidx » Donnerstag 29. Januar 2004, 23:04

sorry nochmal,
kann mir jemand sagen was "yield e" heißt?
bedeutet das e += e oder auch e = e+1 ? thx
Benutzeravatar
Dookie
Python-Forum Veteran
Beiträge: 2010
Registriert: Freitag 11. Oktober 2002, 18:00
Wohnort: Salzburg
Kontaktdaten:

Beitragvon Dookie » Donnerstag 29. Januar 2004, 23:22

Hi davidx,

yield ist kein willkürlicher begriff sondern ein Bestandteil von Python seit 2.2 glaub ich und wird in Iteratoren/Generatoren verwendet um den nächsten wert zu liefern.
yield e is so ähnlich wie return, nur dass der Generator beim nächsten aufruf von next an der stelle hinter yield weitermacht.

Gruß

Dookie

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]