# for Stack class
class Node:
def __init__(self):
self.iData = None # data item (key)
self.dData = None # data item
self.leftChild = None # this nodes left child
self.rightChild = None # this nodes right child
def displayNode(self):
# display ourself
print '{' , self.iData , ',' ,self.dData , '}',
class Tree:
def __init__(self):
# constructor
self.root = None # no nodes in tree
def find(self,key): # find node with given key
# (assumes non-empty tree)
current = self.root # start at self.root
while(current.iData != key): # while no match,
if(key < current.iData): # go left?
current = current.leftChild
else: # or go right?
current = current.rightChild
if(current == None): # if no child,
return None # didnt find it
return current
def insert(self,i,dd):
newNode = Node() # make new node
newNode.iData = i # insert data
newNode.dData = dd
if(self.root==None):# no node in self.root
self.root = newNode
else: # self.root occupied
current = self.root # start at self.root
while(True): # (exits internally)
parent = current
if(i < current.iData): # go left?
current = current.leftChild
if(current == None): # if end of the line,
# insert on left
parent.leftChild = newNode
return
else:# or go right?
current = current.rightChild
if(current == None): # if end of the line
# insert on right
parent.rightChild = newNode
return
def delete(self,key): # delete node with given key
# (assumes non-empty list)
current = self.root
parent = self.root
isLeftChild = True
while(current.iData != key):
parent = current
if(key < current.iData):
isLeftChild = True
current = current.leftChild
else:
isLeftChild = False
current = current.rightChild
if(current == None):
return False
# if no children, simply delete it
if(current.leftChild==None and current.rightChild==None):
if(current == self.root): # if self.root,
self.root = None # tree is empty
elif(isLeftChild):
parent.leftChild = None
else:
parent.rightChild = None
elif(current.rightChild==None):
if(current == self.root):
self.root = current.leftChild
elif(isLeftChild):
parent.leftChild = current.leftChild
else:
parent.rightChild = current.leftChild # if no left child, replace with right subtree
elif(current.leftChild==None):
if(current == self.root):
self.root = current.rightChild
elif(isLeftChild):
parent.leftChild = current.rightChild
else:
parent.rightChild = current.rightChild
else: # two children, so replace with inorder successor
# get successor of node to delete (current)
successor = self.getSuccessor(current)
# connect parent of current to successor instead
if(current == self.root):
self.root = successor
elif(isLeftChild):
parent.leftChild = successor
else:
parent.rightChild = successor
# connect successor to currents left child
successor.leftChild = current.leftChild
return True
def getSuccessor(self,delNode):
successorParent = delNode
successor = delNode
current = delNode.rightChild # go to right child
while(current != None): # until no more
# left children,
successorParent = successor
successor = current
current = current.leftChild # go to left child
# if successor not
if(successor != delNode.rightChild): # right child,
# make connections
successorParent.leftChild = successor.rightChild
successor.rightChild = delNode.rightChild
return successor
def traverse(self,traverseType):
if traverseType == 1:
print '\nPreorder traversal: ',
self.preOrder(self.root)
elif traverseType == 2:
print '\nInorder traversal: ',
self.inOrder(self.root)
else:
print '\nPostorder traversal: ',
self.postOrder(self.root)
print ''
def preOrder(self, localroot):
if(localroot != None):
print localroot.iData ,
self.preOrder(localroot.leftChild)
self.preOrder(localroot.rightChild)
def inOrder(self, localroot):
if(localroot != None):
self.inOrder(localroot.leftChild)
print localroot.iData ,
self.inOrder(localroot.rightChild)
def postOrder(self, localroot):
if(localroot != None):
self.postOrder(localroot.leftChild)
self.postOrder(localroot.rightChild)
print localroot.iData ,
def displayTree(self):
globalStack = list()
globalStack.append(self.root)
nBlanks = 32
isRowEmpty = False
print '\n......................................................'
while(isRowEmpty==False):
localStack = list()
isRowEmpty = True
for j in range(nBlanks):
print ' ',
while(globalStack is not None):
temp = globalStack.pop()
if(temp != None):
print temp.iData,
localStack.append(temp.leftChild)
localStack.append(temp.rightChild)
if(temp.leftChild != None or temp.rightChild != None):
isRowEmpty = False
else:
print '--' ,
localStack.push(None)
localStack.push(None)
for j in range(nBlanks*2-2):
print ' ', # end while globalStack not empty
print ''
nBlanks /= 2
while(localStack is not None):
globalStack.append( localStack.pop() ) # end while isRowEmpty is false
print '\n......................................................'
theTree = Tree()
theTree.insert(50,1.5)
theTree.insert(25,1.2)
theTree.insert(75,1.7)
theTree.insert(12,1.5)
theTree.insert(37,1.2)
theTree.insert(43,1.7)
theTree.insert(30,1.5)
theTree.insert(33,1.2)
theTree.insert(87,1.7)
theTree.insert(93,1.5)
theTree.insert(97,1.5)
while(True):
print 'Enter first letter of show, '
print 'insert, find, delete, or traverse: ',
choice = raw_input()
if choice == 's':
theTree.displayTree()
elif choice == 'i':
print 'Enter value to insert: '
value = int(raw_input())
theTree.insert(value, value + 0.9)
elif choice == 'f':
print 'Enter value to find: ',
value = int(raw_input())
found = theTree.find(value)
if(found != None):
print 'Found: ',
found.displayNode()
print ''
else:
print 'Could not find', value
elif choice=='d':
print 'Enter value to delete: ',
value = int(raw_input())
didDelete = theTree.delete(value)
if(didDelete):
print 'Deleted ' , value
else:
print 'Could not delete ',value
elif choice=='t':
print 'Enter type 1, 2 or 3: '
value = int(raw_input())
theTree.traverse(value)
else:
print 'Invalid entry'