Seite 1 von 1
pre-post-in-order
Verfasst: Donnerstag 29. Januar 2004, 16:30
von davidx
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
Verfasst: Donnerstag 29. Januar 2004, 16:55
von Dookie
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
Verfasst: Donnerstag 29. Januar 2004, 17:27
von Milan
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.
Verfasst: Donnerstag 29. Januar 2004, 17:52
von Dookie
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.
Verfasst: Donnerstag 29. Januar 2004, 23:02
von davidx
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
Verfasst: Donnerstag 29. Januar 2004, 23:04
von davidx
sorry nochmal,
kann mir jemand sagen was "yield e" heißt?
bedeutet das e += e oder auch e = e+1 ? thx
Verfasst: Donnerstag 29. Januar 2004, 23:22
von Dookie
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