from collections import deque
class Node:
left , right, data = None, None, 0
def __init__(self, data):
# initializes the data members
self.left = None
self.right = None
self.data = data
class BTree:
def __init__(self):
# initializes the root member
self.root = None
def addNode(self, data):
# creates a new node and returns it
return Node(data)
def insert(self, root, data):
# inserts a new data
if root == None:
# it there isn't any data
# adds it and returns
return self.addNode(data)
else:
# enters into the tree
if data <= root.data:
# if the data is less than the stored one
# goes into the left-sub-tree
root.left = self.insert(root.left, data)
else:
# processes the right-sub-tree
root.right = self.insert(root.right, data)
return root
def pre_order_traversal(self, root, result=[]):
if root == None:
pass
else:
result.append(root.data)
self.pre_order_traversal(root.left, result)
self.pre_order_traversal(root.right, result)
return result
def in_order_traversal(self, root, result=[]):
if root == None:
pass
else:
self.in_order_traversal(root.left, result)
result.append(root.data)
self.in_order_traversal(root.right, result)
return result
def post_order_traversal(self, root, result=[]):
if root == None:
pass
else:
self.post_order_traversal(root.left, result)
self.post_order_traversal(root.right, result)
result.append(root.data)
return result
# breadth first traversal
def bfs_traversal(self, root):
if root == None: # empty tree
return
# keep a queue which will hold all the nodes
q = deque([root])
while len(q) != 0: # keep going until queue is empty
node = q.popleft()
if node == None:
break
print node.data
if node.left != None:
q.append(node.left)
if node.right != None:
q.append(node.right)
if __name__ == "__main__":
# create the binary tree
BTree = BTree()
# add the root node
root = BTree.addNode(0)
# ask the user to insert values
for i in range(0, 3):
data = int(raw_input("insert the node value for node %d: " % i))
# insert values
BTree.insert(root, data)
result = BTree.in_order_traversal(root, result=[])
print "Inorder Traversal "
print ", ".join(map(str, result))
result = BTree.pre_order_traversal(root, result=[])
print "Preorder Traversal "
print ", ".join(map(str, result))
result = BTree.post_order_traversal(root, result=[])
print "PostOrder Traversal "
print ", ".join(map(str, result))
print "BFS Traversal "
BTree.bfs_traversal(root)
