I'm not a programmer, but I'm currently experimenting with binary trees in Python, and I'm wanting to create a good method for printing out the binary tree, level by level; currently I have implemented a breadth-first method, printing each level starting at the root - which works fine, but was interested in a widely accepted recursive solution.
If I was to use a recursive method, that doesn't simply emulate the iterative breadth-first method - would I/could I use depth-first iterative deepening solution?
I know depth-first iterative deepening is used as an efficient search method, could it be used to give me a level by level print of my tree? Or is the accepted solution here to simply keep my breadth-first method?
Here is code to my tree class, the instantiation creates a tree structure of Fibonacci function recursion calls; I have amended this so that is saves the level into each Node:
from collections import deque
class FibTree(object):
"""Class which builds binary tree from Fibonacci function call graph"""
def __init__(self, n, parent, level=None):
if level is None:
level = 0
self.n = n
self.parent = parent
self.level = level
if n < 2:
self.left = None
self.right = None
self.value = n
else:
self.left = FibTree(n - 1, self, level + 1)
self.right = FibTree(n - 2, self, level + 1)
self.value = self.left.value + self.right.value
The Iterative Breadth-First traversal method implemented:
def level_order_breadth_first_traversal(self):
"""Level order Breadth First Traversal, returning nodes by level"""
this_level = deque([self])
while this_level:
next_level = deque()
yield this_level
while this_level:
u = this_level.popleft()
if u.left is not None:
next_level.extend([u.left])
if u.right is not None:
next_level.extend([u.right])
this_level = next_level
Could I in any way now make use of the Level order stored in each Node in my Breadth-First Traversal to Print out my Binary Tree, or do I have to do some kind of traversal regardless to the fact that I have the level order stored into the Node.
EDIT: To show my Iteratve Deepening Depth level traversal, to attempt to print out my binary tree in level order:
def _getChildren(self,node):
"""Method to expand node"""
hasLeft = node.left is not None
hasRight = node.right is not None
if hasLeft:
yield node.left
if hasRight:
yield node.right
def dls(self, node, depth):
"""Depth Limited Search"""
if (depth == 0):
return node
elif (depth > 0):
print "(" + repr(node.i) + ")" + repr(node.value),
children = self._getChildren(node)
for child in children:
self.dls(child, depth-1)
else:
return False
def iterative_deepening(self):
"""Iterative Deepening to print out binary tree level order"""
depth = 0
while True:
result = self.dls(self, depth)
if result is not False:
return result
depth += 1
When calling the iterative_deepening method just returns the root node, instead of a list of nodes in level order.
Thanks Alex
