[Python-de] Re: [Python-de] Kleine Aufgabe, große Wirkung

Mark Zöltsch zoeltsch at mooniewar.de
Mon Apr 7 08:47:44 EDT 2003


> Sollten sich genügend viele finden, die mit dieser Aufgabe
> substantielle Probleme haben, schlage ich hingegen folgendes
> vor: Ich biete Euch ein "Coaching" an, bei dem intensiv mehrere
> Wochen lang geübt wird, solcherart Probleme zu lösen.

Ich braeuchte Coaching wie ich deine Alptraum Attacken ueberlebe!
Nach diesem PERL SP April Joke und nach eine unruhigen Nacht hab ich 
mich doch noch drangehockt und hoffe alle Fragen damit erledigt 
zu haben...hoffe keine brachialen Fehler gemacht zu haben in diesen fruehen
Stunden, hoffe ebenfalls das du Stackless bald fertig hast (Utopie?), ich endlich 
mich mal dran mach Channels und Tasklets zu verstehen und ueberhaupt meine 
Diplomarbeit darueber (unter anderem) fertig zu kriegen :) 
Ich sag ja du bist mein Alptraum in letzter Zeit... ;)

#tested on Python 2.2.1 win32
from __future__ import generators

t    = [1,[2,[4,[8, None, None],[9, None, None]],
       [5,[10, None, None],[11, None, None]]],[3,
       [6,[12, None, None],[13, None, None]],[7,
       [14, None, None],[15, None, None]]]]
"""
#              1
#         2         3
#       4   5     6   7
#      8 9 1011 1213 1415

#PREORDER (depth-first-order):
#node left right
#1 2 4 8 9 5 10 11 3 6 12 13 7 14 15

#INORDER:
#left, node, right
#8 4 9 2 10 5 11 1 12 6 13 3 14 7 15

#POSTORDER:
#left, right, node
#8 9 4 10 11 5 2 12 13 6 14 15 7 3 1

#LEVELORDER (breadth-first-order):
#nodes of level i, before level i+1
#1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
"""

def levelorder(tree):
    """
    as seen on python-de ml
    """
    tmp = [tree]
    while tmp[0]:
        node, left, right = tmp[0]
        yield node
        tmp = tmp[1:]
        tmp.append(left)
        tmp.append(right)

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

def binarytree_walk(method, search=None, verbose=0):
    count = 0
    for n in method(t):
        count += 1
        if search and n == search:
            print n, "<- gefunden nach", count, " Durchgaengen"
            break
        else:
            if verbose:
                print n,

class Tree:
    """
    see http://www.python.org/peps/pep-0255.html
    """
    def __init__(self,label,left=None,right=None):
        """
        Tree consists of node(aka label), left subtree and
        right subtree
        """
        self.label = label
        self.left  = left
        self.right = right

    def __repr__(self, level=0, indent="-"):
        """
        object representation
        for better debug and print output
        """
        s = level*indent+`self.label`
        if self.left:
            s = s+'\n'+self.left.__repr__(level+1, indent)
        if self.right:
            s = s+'\n'+self.right.__repr__(level+1, indent)
        return s

    #2 lazy 2 write tree walk methods again...
    #do it yourself or have a look at pep255

def convertL2T(tree_as_list):
    """
    for the folk who hates [[[[[[[...]]]-slicing-madness :)
    """
    if tree_as_list:
        return Tree(tree_as_list[0], convertL2T(tree_as_list[1]), convertL2T(tree_as_list[2]))

if __name__ == '__main__':
    v = 1
    binarytree_walk(preorder, 12, v)
    binarytree_walk(postorder, 12)
    binarytree_walk(inorder, 12)
    binarytree_walk(levelorder, 12)

    print convertL2T(t)

    """
    PS: yep I'm a generator-lunatic :)
    """
    del v, t


SEE yA 
PS Hat jemand einen Crashkurs-Link fuer Channels und Tasklets?



More information about the Python-de mailing list