#!/usr/bin/python3
# ==================================================================
# play with binary tree (of integers)
# ==================================================================
class Node():
'''create a node in the binary tree'''
def __init__(self,v):
self.value = v
self.left = None
self.right = None
def SetLeft(self,v):
self.left = Node(v)
def SetRight(self,v):
self.right = Node(v)
def GetLeft():
return left
def GetRight():
return right
def GetValue():
return self.value
class BinaryTree():
'''create the root node of a binary tree'''
def __init__(self,v):
self.root = Node(v)
def print_tree(self,traversal_type):
if traversal_type == 'preorder':
return self.preorder_print(tree.root,'')
elif traversal_type == 'postorder':
return self.postorder_print(tree.root,'')
elif traversal_type == 'inorder':
return self.inorder_print(tree.root,'')
else:
print('Traversal type ' + traversal_type + ' not supported')
return False
def preorder_print(self,start,traversal):
'''pre-order traversal: root- > left-> right'''
if start:
traversal += (str(start.value) + ',')
traversal = self.preorder_print(start.left,traversal)
traversal = self.preorder_print(start.right,traversal)
return traversal
def postorder_print(self,start,traversal):
'''post-order traversal: right-> left -> root'''
if start:
traversal = self.postorder_print(start.left,traversal)
traversal = self.postorder_print(start.right,traversal)
traversal += (str(start.value) + ',')
return traversal
def inorder_print(self,start,traversal):
'''in-order traversal: left -> root -> right'''
if start:
traversal = self.inorder_print(start.left,traversal)
traversal += (str(start.value) + ",")
traversal = self.inorder_print(start.right,traversal)
return traversal
# ------------------------------------------------------------------
print ('''
--------demo tree--------
5
/ \
3 7
/ \ / \
2 4 6 8
/
1
In the demo tree, for each node, the left sub-tree
contains values that are less than the node's value.
The right sub-tree contain values larger than
the node's value.
pre-order traversal : root -> left -> right
post-order traversal: right-> left -> root
in-order traversal : left -> root -> right
''')
tree = BinaryTree(5)
tree.root.left = Node(3)
tree.root.right = Node(7)
tree.root.left.left = Node(2)
tree.root.left.right = Node(4)
tree.root.left.left.left = Node(1)
tree.root.right.left = Node(6)
tree.root.right.right = Node(8)
print('pre-oder : ' + tree.print_tree('preorder'))
print('post-order: ' + tree.print_tree('postorder'))
print('in-order : ' + tree.print_tree('inorder'))
print('''
As an exercise, create a tree that pre-order traversal
prints out the nodes in order (1,2,3,4,5,6,7,8,). How
about a post-order Traversal? How another traversal
method?
As you will see the order of the nodes and the tree
traversal are very much entwined. The design question
is how the data is comming in and how do we need to
access it. For example, is it worth the resources
(cpu cycles, memory, software development time, etc.)
to re-order the data for efficient access, etc.
''')