{
"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": {}
}
]
}