Sometimes when debugging trees it's useful to analyze them by printing them out. Using a reversed inorder traversal makes this easy.
Using the code below you'll get something like this:
14 6 13 2 12 5 11 0 10 4 9 1 8 3 7
- Calculate the string for the right branch, and pass the function the current depth + 1.
- Calculate the string for the value of the current node, and prepend spaces to the string. The number of spaces will be some multiple of the depth.
- Calculate the string for the left branch, and pass the function the current depth + 1.
Here is the implementation, the __str__ method is what you want to look at:
#!/usr/bin/python class BinaryTree: def __init__(self, depth, value=0): self.value = value # For demo purposes, this just creates a full binary tree self.left = BinaryTree(depth-1, value*2 + 1) if depth > 0 else None self.right = BinaryTree(depth-1, value*2 + 2) if depth > 0 else None def __str__(self, depth=0): ret = "" # Print right branch if self.right != None: ret += self.right.__str__(depth + 1) # Print own value ret += "\n" + (" "*depth) + str(self.value) # Print left branch if self.left != None: ret += self.left.__str__(depth + 1) return ret if __name__ == "__main__": print BinaryTree(4)
About the author
I'm Steve Krenzel, a software engineer and co-founder of Thinkfuse. Contact me at firstname.lastname@example.org.