Visitor traversal: http://therning.org/magnus/?p=1184

visitor2.py

class Visitor:
    def visit(self, obj):
        getattr(self, 'visit_' + obj.__class__.__name__)(obj)

    def visit_Tree(self, t):
        pass

    def visit_Leaf(self, l):
        pass


class Visitable:
    def accept(self, visitor):
        visitor.visit(self)


class Tree(Visitable):
    def __init__(self, left, right):
        self.left = left
        self.right = right


class Leaf(Visitable):
    def __init__(self, value):
        self.value = value


def build_tree():
    l0 = Leaf(0)
    l1 = Leaf(1)
    t0 = Tree(l0, l1)
    l2 = Leaf(2)
    t1 = Tree(t0, l2)
    l3 = Leaf(3)
    l4 = Leaf(4)
    t2 = Tree(l3, l4)
    return Tree(t1, t2)


class Print(Visitor):
    def visit_Tree(self, t):
        print('Tree (%s)' % hex(id(t)))

    def visit_Leaf(self, l):
        print('Leaf (%s): %i' % (hex(id(l)), l.value))


class Sequence(Visitor):
    def __init__(self, first, then):
        self.first = first
        self.then = then

    def visit_Tree(self, t):
        t.accept(self.first)
        t.accept(self.then)

    def visit_Leaf(self, l):
        l.accept(self.first)
        l.accept(self.then)


class All(Visitor):
    def __init__(self, v):
        self.v = v

    def visit_Tree(self, t):
        t.left.accept(self.v)
        t.right.accept(self.v)


class TopDown(Sequence):
    def __init__(self, v):
        Sequence.__init__(self, v, All(self))


class BottomUp(Sequence):
    def __init__(self, v):
        Sequence.__init__(self, All(self), v)