#demonstrates binary tree
class Node:
def __init__(self): #special method to create objects
#with instances customized to a specific initial state
self.iData = 0 #data item (key)
self.dData = 0.0 #data item
self.pLeftChild = None #this node's left child
self.pRightChild = None #this node's right child
def __del__(self): #destructor
print 'X-', self.iData,
def displayNode(self): #display ourself
print '{', self.iData, ',', self.dData, '}'
#end class Node
class Tree:
#as private instance variables don't exist in Python,
#hence using a convention: name prefixed with an underscore, to treat them as non-public part
def __init__(self):
self._pRoot = None #first node of tree
def find(self, key): #find node with given key
#(assumes non-empty tree)
pCurrent = self._pRoot #start at root
while pCurrent.iData != key: #while no match,
if key < pCurrent.iData: #go left?
pCurrent = pCurrent.pLeftChild
else: #or go right?
pCurrent = pCurrent.pRightChild
if not pCurrent: #if no child,
return None#didn't find it
return pCurrent #found it
#end find()
def insert(self, Id, dd): #insert new node
pNewNode = Node() #make new node
pNewNode.iData = Id#insert data
pNewNode.dData = dd
if not self._pRoot: #no node in root
self._pRoot = pNewNode
else: #root occupied
pCurrent = self._pRoot #start at root
while True: #(exits internally)
pParent = pCurrent
if Id < pCurrent.iData: #go left?
pCurrent = pCurrent.pLeftChild
if not pCurrent: #if end of the line,
pParent.pLeftChild = pNewNode #insert on left
return
#end if go left
else: #or go right?
pCurrent = pCurrent.pRightChild
if not pCurrent: #if end of the line
pParent.pRightChild = pNewNode #insert on right
return
#end else go right
#end while
#end else not root
#end insert()
def traverse(self, traverseType):
#as Python does not support switch, hence using dictionaries and functions instead
case = {1 : self.preOrder,
2 : self.inOrder,
3 : self.postOrder
}
case[traverseType](self._pRoot) #performing respective operation using dictionary lookup
def preOrder(self, pLocalRoot):
if pLocalRoot:
print pLocalRoot.iData, #display node
self.preOrder(pLocalRoot.pLeftChild) #left child
self.preOrder(pLocalRoot.pRightChild) #right child
def inOrder(self, pLocalRoot):
if pLocalRoot:
self.inOrder(pLocalRoot.pLeftChild) #left child
print pLocalRoot.iData, #display node
self.inOrder(pLocalRoot.pRightChild) #right child
def postOrder(self, pLocalRoot):
if pLocalRoot:
self.postOrder(pLocalRoot.pLeftChild) #left child
self.postOrder(pLocalRoot.pRightChild) #right child
print pLocalRoot.iData, #display node
def displayTree(self):
globalStack = []
globalStack.append(self._pRoot)
nBlanks = 32
isRowEmpty = False
print '......................................................'
while not isRowEmpty:
localStack = []
isRowEmpty = True
for j in xrange(nBlanks - 1):
print '',
while globalStack:
temp = globalStack.pop()
if temp:
print temp.iData,
localStack.append(temp.pLeftChild)
localStack.append(temp.pRightChild)
if temp.pLeftChild or temp.pRightChild:
isRowEmpty = False
else:
print '--',
localStack.append(None)
localStack.append(None)
for j in xrange(nBlanks*2-3):
print '',
#end while globalStack not empty
print
print
nBlanks /= 2
while localStack:
globalStack.append(localStack.pop())
#end while isRowEmpty is False
print '......................................................'
#end displayTree()
def destroy(self): #deletes tree
del self._pRoot
#end class Tree
choice = None
theTree = Tree() #create tree
theTree.insert(50, 5.0) #insert nodes
theTree.insert(25, 2.5)
theTree.insert(75, 7.5)
theTree.insert(12, 1.2)
theTree.insert(37, 3.7)
theTree.insert(43, 4.3)
theTree.insert(30, 3.0)
theTree.insert(33, 3.3)
theTree.insert(87, 8.7)
theTree.insert(93, 9.3)
theTree.insert(97, 9.7)
#as Python does not support switch, hence using functions and dictionaries instead
def show(): #show the tree
theTree.displayTree()
def insert(): #insert a node
value = int(raw_input('Enter value to insert: '))
theTree.insert(value, value + 0.9)
def find(): #find a node
value = int(raw_input('Enter value to find: '))
found = theTree.find(value)
if found:
print 'Found:',
found.displayNode()
else:
print 'Could not find', value
def traverse(): #traverse the tree
value = int(raw_input('Enter traverse type (1=preorder, 2=inorder, 3=postorder): '))
theTree.traverse(value)
def quit(): #quit the program
theTree.destroy()
case = {'s' : show,
'i': insert,
'f' : find,
't' : traverse,
'q' : quit}
#functions and dictionaries ready
while choice != 'q': #interact with user until user types 'q'
choice = raw_input('\nEnter first letter of show, insert, find, traverse or quit: ')
if case.get(choice, None):
case[choice]() #performing user's choice by dictionary lookup
else:
print 'Invalid entry'
#end while
#end