Binary Tree Implementation and Traversal (DFS, BFS)
Simpler way:
class Node:
def __init__(self,data):
self.data = data
self.left = None
self.right = None
def binary_insert(self,node):
if self is None:
self = node
else:
if self.data >= node.data:
if self.left is None:
self.left = node
else:
binary_insert(self.left,node)
else:
if self.right is None:
self.right = node
else:
binary_insert(self.right,node)
#Below 3 functions are for DFS
def pre_order_print(self):
if self is None:
return
print self.data
pre_order_print(self.left)
pre_order_print(self.right)
def in_order_print(self):
if self is None:
return
in_order_print(self.left)
print self.data
in_order_print(self.right)
def post_order_print(self):
if self is None:
return
post_order_print(self.left)
post_order_print(self.right)
print self.data
#Below function is for BFS (level-order)
def level_order_print(list):
while(len(list)>0):
self = list[0]
print self.data
list.pop(0)
if(self.left is not None):
list.append(self.left)
if(self.right is not None):
list.append(self.right)
level_order_print(list)
r = Node(3)
binary_insert(r, Node(7))
binary_insert(r, Node(1))
binary_insert(r, Node(5))
binary_insert(r, Node(12))
binary_insert(r, Node(9))
binary_insert(r, Node(4))
binary_insert(r, Node(8))
binary_insert(r, Node(10))
binary_insert(r, Node(1))
binary_insert(r, Node(11))
binary_insert(r, Node(2))
binary_insert(r, Node(-4))
print "DFS: pre order print is:"
pre_order_print(r)
print "DFS: in order print is:"
in_order_print(r)
print "DFS: post order print is:"
post_order_print(r)
print "BFS: level order print:"
level_order_print([r])
+++++++++++++++++++++++
DFS: pre order print is:
3
1
1
-4
2
7
5
4
12
9
8
10
11
DFS: in order print is:
-4
1
1
2
3
4
5
7
8
9
10
11
12
DFS: post order print is:
-4
1
2
1
4
5
8
11
10
9
12
7
3
BFS: level order print:
3
1
7
1
2
5
12
-4
4
9
8
10
11
++++++++++++++++++
Binary tree above diagrammatically:
3 <-- Level0
1 7 <-- Level1
1 2 5 11 <-- Level2
-4 4 12 <-- Level3
9 <-- Level4
8 10 <-- Level5
11 <-- Level6
