Define Tree, a traversable tree structure.
A traversable tree structure.
Examples
Construct:
+bdg
a+ +e
+c+fhi
with
>>> i = Tree(); i.n = "i"
>>> h = Tree([i]); h.n = "h"
>>> f = Tree([h]); f.n = "f"
>>> e = Tree(); e.n = "e"
>>> c = Tree([f,e]); c.n = "c"
>>> g = Tree(); g.n = "g"
>>> d = Tree([g]); d.n = "d"
>>> b = Tree([d]); b.n = "b"
>>> a = Tree(); a.n = "a"
>>> a.append(c)
>>> a.append(b)
Get the longest branch length with
>>> a.branch_len()
5
Sort the tree recursively. Here we sort longest branch length first.
>>> a.sort(key=lambda node : node.branch_len())
>>> "".join([node.n for node in a.traverse()])
'acfhiebdg'
And here we sort shortest branch length first.
>>> a.sort(key=lambda node : node.branch_len())
>>> "".join([node.n for node in a.traverse()])
'abdgcefhi'
We can also do breadthfirst traverses.
>>> "".join([node.n for node in a.traverse(depth_first=False)])
'abcdefghi'
Serialize the tree with depth marking branches.
>>> for depth,node in a.thread():
... print "%*s" % (2*depth+1, node.n)
a
b
d
g
c
e
f
h
i
Flattening the thread disables depth increases except at branch splits.
>>> for depth,node in a.thread(flatten=True):
... print "%*s" % (2*depth+1, node.n)
a
b
d
g
c
e
f
h
i
We can also check if a node is contained in a tree.
>>> a.has_descendant(g)
True
>>> c.has_descendant(g)
False
>>> a.has_descendant(a)
False
>>> a.has_descendant(a, match_self=True)
True
Methods
append  L.append(object) – append object to end 
branch_len()  Return the largest number of nodes from root to leaf (inclusive). 
count(...)  
extend  L.extend(iterable) – extend list by appending elements from the iterable 
has_descendant(descendant[, depth_first, ...])  Check if a node is contained in a tree. 
index((value, [start, ...)  Raises ValueError if the value is not present. 
insert  L.insert(index, object) – insert object before index 
pop(...)  Raises IndexError if list is empty or index is out of range. 
remove  L.remove(value) – remove first occurrence of value. 
reverse  L.reverse() – reverse IN PLACE 
sort(*args, **kwargs)  Sort the tree recursively. 
thread([flatten])  Generate a (depth, node) tuple for every node in the tree. 
traverse([depth_first])  Generate all the nodes in a tree, starting with the root node. 
Return the largest number of nodes from root to leaf (inclusive).
For the tree:
+bdg
a+ +e
+c+fhi
this method returns 5.
Notes
Exhaustive search every time == slow.
Use only on small trees, or reimplement by overriding childaddition methods to allow accurate caching.
Check if a node is contained in a tree.
Parameters :  descendant : Tree
depth_first : bool
match_self : bool


Sort the tree recursively.
This method extends list.sort() to Trees.
Notes
This method can be slow, e.g. on a branch_len() sort, since a node at depth N from the root has it’s branch_len() method called N times.
Generate a (depth, node) tuple for every node in the tree.
When flatten is False, the depth of any node is one greater than the depth of its parent. That way the inheritance is explicit, but you can end up with highly indented threads.
When flatten is True, the depth of any node is only greater than the depth of its parent when there is a branch, and the node is not the last child. This can lead to ancestry ambiguity, but keeps the total indentation down. For example:
+b +bc
a+c and a+
+def +def
would both produce (after sorting by branch_len()):
(0, a)
(1, b)
(1, c)
(0, d)
(0, e)
(0, f)
Generate all the nodes in a tree, starting with the root node.
Parameters :  depth_first : bool

