print binary tree level by level in python
print binary tree level by level in python
Heres my attempt, using recursion, and keeping track of the size of each node and the size of children.
class BstNode:
def __init__(self, key):
self.key = key
self.right = None
self.left = None
def insert(self, key):
if self.key == key:
return
elif self.key < key:
if self.right is None:
self.right = BstNode(key)
else:
self.right.insert(key)
else: # self.key > key
if self.left is None:
self.left = BstNode(key)
else:
self.left.insert(key)
def display(self):
lines, *_ = self._display_aux()
for line in lines:
print(line)
def _display_aux(self):
Returns list of strings, width, height, and horizontal coordinate of the root.
# No child.
if self.right is None and self.left is None:
line = %s % self.key
width = len(line)
height = 1
middle = width // 2
return [line], width, height, middle
# Only left child.
if self.right is None:
lines, n, p, x = self.left._display_aux()
s = %s % self.key
u = len(s)
first_line = (x + 1) * + (n - x - 1) * _ + s
second_line = x * + / + (n - x - 1 + u) *
shifted_lines = [line + u * for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2
# Only right child.
if self.left is None:
lines, n, p, x = self.right._display_aux()
s = %s % self.key
u = len(s)
first_line = s + x * _ + (n - x) *
second_line = (u + x) * + \ + (n - x - 1) *
shifted_lines = [u * + line for line in lines]
return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2
# Two children.
left, n, p, x = self.left._display_aux()
right, m, q, y = self.right._display_aux()
s = %s % self.key
u = len(s)
first_line = (x + 1) * + (n - x - 1) * _ + s + y * _ + (m - y) *
second_line = x * + / + (n - x - 1 + u + y) * + \ + (m - y - 1) *
if p < q:
left += [n * ] * (q - p)
elif q < p:
right += [m * ] * (p - q)
zipped_lines = zip(left, right)
lines = [first_line, second_line] + [a + u * + b for a, b in zipped_lines]
return lines, n + m + u, max(p, q) + 2, n + u // 2
import random
b = BstNode(50)
for _ in range(50):
b.insert(random.randint(0, 100))
b.display()
Example output:
__50_________________________________________
/
________________________43_ ________________________99
/ /
_9_ 48 ____________67_____________________
/ /
3 11_________ 54___ ______96_
/ /
0 8 ____26___________ 61___ ________88___ 97
/ / /
14_ __42 56 64_ 75_____ 92_
/ / / / /
13 16_ 33_ 63 65_ 72 81_ 90 94
/ /
25 __31 41 66 80 87
/ /
28_ 76
29
What youre looking for is breadth-first traversal, which lets you traverse a tree level by level. Basically, you use a queue to keep track of the nodes you need to visit, adding children to the back of the queue as you go (as opposed to adding them to the front of a stack). Get that working first.
After you do that, then you can figure out how many levels the tree has (log2(node_count) + 1) and use that to estimate whitespace. If you want to get the whitespace exactly right, you can use other data structures to keep track of how many spaces you need per level. A smart estimation using number of nodes and levels should be enough, though.
print binary tree level by level in python
class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right
def printTree(node, level=0):
if node != None:
printTree(node.left, level + 1)
print( * 4 * level + -> + node.value)
printTree(node.right, level + 1)
t = Node(1, Node(2, Node(4, Node(7)),Node(9)), Node(3, Node(5), Node(6)))
printTree(t)
output:
-> 7
-> 4
-> 2
-> 9
-> 1
-> 5
-> 3
-> 6