Python. What is wrong with my program? I am trying to prove that my program is c

Question

Python. What is wrong with my program? I am trying to prove that my program is capable of replacing an existing key with a new key instead of creating a new node. This is for a binary search tree. What can I do? It doesn't seem to be replacing anything.

class BinarySearchTree:

def __init__(self):
self.root = None
self.size = 0

def length(self):
return self.size

def __len__(self):
return self.size

def put(self,key,val):
if self.root:
self._put(key,val,self.root)
else:
self.root = TreeNode(key,val)
self.size = self.size + 1

def _put(self,key,val,currentNode):
if key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key,val,currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key,val,parent=currentNode)
else:
if currentNode.hasRightChild():
self._put(key,val,currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key,val,parent=currentNode)

#This allows the _put() method to search for equality in the program   
def _put(self,key,val,currentNode):
if key == currentNode.key:
currentNode.value = val

elif key < currentNode.key:
if currentNode.hasLeftChild():
self._put(key,val,currentNode.leftChild)
else:
currentNode.leftChild = TreeNode(key,val, parent=currentNode)
else:
if currentNode.hasRightChild():
self._put(key,val,currentNode.rightChild)
else:
currentNode.rightChild = TreeNode(key,val, parent=currentNode)

def __setitem__(self,k,v):
self.put(k,v)

def get(self,key):
if self.root:
res = self._get(key,self.root)
if res:
return res.payload
else:
return None
else:
return None

def _get(self,key,currentNode):
if not currentNode:
return None
elif currentNode.key == key:
return currentNode
elif key < currentNode.key:
return self._get(key,currentNode.leftChild)
else:
return self._get(key,currentNode.rightChild)

def __getitem__(self,key):
return self.get(key)

def __contains__(self,key):
if self._get(key,self.root):
return True
else:
return False

def delete(self,key):
if self.size > 1:
nodeToRemove = self._get(key,self.root)
if nodeToRemove:
self.remove(nodeToRemove)
self.size = self.size-1
else:
raise KeyError('Error, key not in tree')
elif self.size == 1 and self.root.key == key:
self.root = None
self.size = self.size - 1
else:
raise KeyError('Error, key not in tree')

def __delitem__(self,key):
self.delete(key)

def spliceOut(self):
if self.isLeaf():
if self.isLeftChild():
self.parent.leftChild = None
else:
self.parent.rightChild = None
elif self.hasAnyChildren():
if self.hasLeftChild():
if self.isLeftChild():
self.parent.leftChild = self.leftChild
else:
self.parent.rightChild = self.leftChild
self.leftChild.parent = self.parent
else:
if self.isLeftChild():
self.parent.leftChild = self.rightChild
else:
self.parent.rightChild = self.rightChild
self.rightChild.parent = self.parent

def findSuccessor(self):
succ = None
if self.hasRightChild():
succ = self.rightChild.findMin()
else:
if self.parent:
if self.isLeftChild():
succ = self.parent
else:
self.parent.rightChild = None
succ = self.parent.findSuccessor()
self.parent.rightChild = self
return succ

def findMin(self):
current = self
while current.hasLeftChild():
current = current.leftChild
return current

def remove(self,currentNode):
if currentNode.isLeaf(): #leaf
if currentNode == currentNode.parent.leftChild:
currentNode.parent.leftChild = None
else:
currentNode.parent.rightChild = None
elif currentNode.hasBothChildren(): #interior
succ = currentNode.findSuccessor()
succ.spliceOut()
currentNode.key = succ.key
currentNode.payload = succ.payload

else: # this node has one child
if currentNode.hasLeftChild():
if currentNode.isLeftChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.leftChild
elif currentNode.isRightChild():
currentNode.leftChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.leftChild
else:
currentNode.replaceNodeData(currentNode.leftChild.key,
currentNode.leftChild.payload,
currentNode.leftChild.leftChild,
currentNode.leftChild.rightChild)
else:
if currentNode.isLeftChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.leftChild = currentNode.rightChild
elif currentNode.isRightChild():
currentNode.rightChild.parent = currentNode.parent
currentNode.parent.rightChild = currentNode.rightChild
else:
currentNode.replaceNodeData(currentNode.rightChild.key,
currentNode.rightChild.payload,
currentNode.rightChild.leftChild,
currentNode.rightChild.rightChild)

class TreeNode:
def __init__(self,key,val,left=None,right=None,parent=None):

self.key = key
self.payload = val
self.leftChild = left
self.rightChild = right
self.parent = parent

def hasLeftChild(self):
return self.leftChild

def hasRightChild(self):
return self.rightChild

def isLeftChild(self):
return self.parent and self.parent.leftChild == self

def isRightChild(self):
return self.parent and self.parent.rightChild == self

def isRoot(self):
return not self.parent

def isLeaf(self):
return not (self.rightChild or self.leftChild)

def hasAnyChildren(self):
return self.rightChild or self.leftChild

def hasBothChildren(self):
return self.rightChild and self.leftChild

def replaceNodeData(self,key,value,lc,rc):
self.key = key
self.payload = value
self.leftChild = lc
self.rightChild = rc
if self.hasLeftChild():
self.leftChild.parent = self
if self.hasRightChild():
self.rightChild.parent = self

mytree = BinarySearchTree()
mytree[3]="red"
mytree[4]="blue"
#Both "yellow" and "at" are purposely set to 6
mytree[6]="yellow"
mytree[6]="at"

print(mytree[6])
print(mytree[6])

Explanation / Answer

Try with the following binary search tree in python code :

class Node:

def __init__(self,info): #constructor of class

self.info = info #information for node
self.left = None #left leef
self.right = None #right leef
self.level = None #level none defined

def __str__(self):

return str(self.info) #return as string

class searchtree:

def __init__(self): #constructor of class

self.root = None

def create(self,val): #create binary search tree nodes

if self.root == None:

self.root = Node(val)

else:

current = self.root

while 1:

if val < current.info:

if current.left:
current = current.left
else:
current.left = Node(val)
break;

elif val > current.info:

if current.right:
current = current.right
else:
current.right = Node(val)
break;

else:
break

def bft(self): #Breadth-First Traversal

self.root.level = 0
queue = [self.root]
out = []
current_level = self.root.level

while len(queue) > 0:

current_node = queue.pop(0)

if current_node.level > current_level:
current_level += 1
out.append(" ")

out.append(str(current_node.info) + " ")

if current_node.left:

current_node.left.level = current_level + 1
queue.append(current_node.left)
  

if current_node.right:

current_node.right.level = current_level + 1
queue.append(current_node.right)
  

print "".join(out)   

def inorder(self,node):
  
if node is not None:
  
self.inorder(node.left)
print node.info
self.inorder(node.right)

def preorder(self,node):
  
if node is not None:
  
print node.info
self.preorder(node.left)
self.preorder(node.right)

def postorder(self,node):
  
if node is not None:
  
self.postorder(node.left)
self.postorder(node.right)
print node.info

  
tree = searchtree()   
arr = [8,3,1,6,4,7,10,14,13]
for i in arr:
tree.create(i)
print 'Breadth-First Traversal'
tree.bft()
print 'Inorder Traversal'
tree.inorder(tree.root)
print 'Preorder Traversal'
tree.preorder(tree.root)
print 'Postorder Traversal'
tree.postorder(tree.root)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.