1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
{
"metadata": {
"name": "ch8"
},
"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": "'''\nexample 8.1\ndemonstrates binary tree\n'''\n\n# for Stack class\nclass 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\nclass 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\ntheTree = Tree()\ntheTree.insert(50,1.5)\ntheTree.insert(25,1.2)\ntheTree.insert(75,1.7)\ntheTree.insert(12,1.5)\ntheTree.insert(37,1.2)\ntheTree.insert(43,1.7)\ntheTree.insert(30,1.5)\ntheTree.insert(33,1.2)\ntheTree.insert(87,1.7)\ntheTree.insert(93,1.5)\ntheTree.insert(97,1.5)\nwhile(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": {}
}
]
}
|
