Python - tree traversal issue

Question

It's hard for me to walk around a tree, and so avoid it like a plague ... usually.

I have a class of this kind (a slightly simplified version here, but functionally the same) as:

class Branch(object): def __init__(self, title, parent=None): self.title = title self.parent = parent 

I have a dictionary from a set of Branch instances, each heading as a key:

 tree = {'Foo Branch': foo, 'Sub-Foo Branch': sub_foo, 'Bar Branch': bar} 

Now I know that there are complex algorithms for efficient workaround (for example, MPTT, etc.), especially for use with database-based projects where efficiency is important. I do not use a database at all, only simple objects in memory.

Given the title of Branch , I need to get a list all the descendants of this branch (children, child children, etc.) from tree , so:

• Would you recommend using complex (for my algo unanswered algorithm as MPTT for efficiency in my case, or is there an easy way to achieve this in one function?
• If so, which one would you recommend, knowing that I am not using a database?
• Can you give an example, or is it much more than I think?

Note This is not homework. I'm not in school. I'm just so bad at algorithms. I used Django MPTT for a project that required DB-stored trees ... but still doesn't understand it very well.

Answer 1

http://en.wikipedia.org/wiki/Depth-first_search

http://en.wikipedia.org/wiki/Tree_traversal

During two passes you go as follows:

• First pass: find the node query using the appropriate key. (This step is not needed if you have a hashmap of all nodes in the whole tree, you have this (good), so this step is not needed.)

• Second pass: call the modified version of the algorithm in the node request, but this time when you visit the node, output it (or add it to the non-local variable of the battery).

However, your situation is a bit strange, because usually trees have pointers to child elements, sort of like a double list. Unfortunately, we do not have this information ... but, fortunately, it is easy to add this information:

 nodes = tree.values() for node in nodes: if node.parent: if not hasattr(node.parent, 'children'): node.parent.children = [] node.parent.children +=[ node ] 

Now we can continue our example:

 def traverse(root, callback): """ Peform callback on all nodes in depth-first order eg traverse(root, lambda x:print(x)) """ yield root, callback(root) for child in root.children: traverse(child) def getAllDescendents(title): queryNode = titlesToNodes[title] #what you call 'tree' for node,blah in traverse(queryNode, lambda x:None): yield node