Chapter 8 : Binary Trees

Exmaple 8.1 Page No : 406

In [ ]:
 
# 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'
In [ ]: