What is the most efficient way to traverse a tree in Python?

Assuming I have a list of objects that have the following fields

parent

value

and this defines a tree structure, similar to a directory tree.

I want to traverse the list in a pre-order fashion. What's the most efficient way?

Normally, in other (more imperative) languages I would iterate the values, finding the ones with no parents, th开发者_开发问答en for each, iterating again for every object whose parent is the one I'm currently looking at and so forth, but is there a cleverer way to do this in Python?

---

I would first create a more suitable data structure -- capturing the link from a parent to its children:

children = {}
for obj in tree:
    children.setdefault(obj.parent, []).append(obj)

def preorder(root, children):
    yield root.value
    for child in children.get(root, []):
        for value in preorder(child, children):
            yield value

for root in children[None]:
    for value in preorder(root, children):
        print value

You could also use collections.defaultdict here.