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