Your current implementation is quite nice.
The only way you are going to avoid using the
while loop to find the right-most node is if you have each individual branch maintain its branch's tail
Node. This is a [sort of] good approach to the problem. However, once you reach this point, a
Node really starts becoming more than just a
Node: it now has information about the entire structure instead of what is directly around it.
So instead of modifying the
Node class, you could create a
This change makes sense:
- Right now you manually create your 'tree'. This approach is not very portable. A
Tree class can handle its own creation.
- You need to store information about the entire branch structure somewhere. Inside a
Node doesn't feel right.
- You don't really flatten a
Node, you flatten a tree of nodes. Thus, it again makes sense to move the
flatten function inside a
Tree class (or at least take a
Here is a skeleton version of my
Tree class. I have stubbed out all my methods except
flatten as that is the function in question:
def __init__(self, root=None):
self.root = root
self.tail = root
self.length = 1 if root else 0
''' Allows iteration through the tree using `for node in tree`. '''
def __getitem__(self, index):
''' Fetches the `Node` at the passed index. '''
def grow(self, nodes):
''' Appends node/nodes/Tree onto itself. Be careful when adding `Node`
we need to append a *copy* of a `Node`, not the reference. '''
def graft(self, tree, node_pos=0):
''' Grafts in another tree to this one. By default the new tree
is grafted to the root of the tree. '''
''' Returns the flattened version of itself. '''
flat = Tree()
for next in self:
In this version of
flatten, we keep the recursive feel as we call a method with the same method declaration. However, we are not doing true recursion because the methods are bound to different objects, and thus are different methods.
In any case, the
flatten function is really quite simple:
- Create the new
Tree we are going to modify and return.
- Loop through the
Nodes of the current tree.
Append the current
3.1. If that
Node has a child
Tree, append the flattened version of that
- Return the final flattened
Here is my
Tree class plus your
Node class in action:
one, two, three, four, five, six, seven, eight, nine = [Node(num) for num in xrange(1,10)]
tree = Tree(one)
tree.grow([two, three, five])
# Graft the new `Tree` to the 3rd `Node`.
branch = Tree(six)
# Graft the new `Tree` to the 1st `Node`.
''' A non-class version of the `flatten` function. '''
flat = Tree()
for next in tree:
print ' - '.join([str(node.value) for node in flatten(tree)])
print ' - '.join([str(node.value) for node in tree.flatten()])