Can you make a test case for this to see if it works?
Can you make a test case for this to see if it works?
class BSTnode:
def __init__(self, key=None, left=None, right=None, parent=None):
# Initialize a node.
self.__key = key # value for the node
self.__left = left
self.__right = right
self.__parent = parent
def setkey(self, newkey):
# Sets the key value of the node to newkey
self.__key = newkey
def getkey(self):
# returns the key value of the node
return self.__key
def getright(self):
# returns the right child of the node
return self.__right
def setright(self, newright):
# Sets the right child to the new node object newright. Child nodes parent is also updated.
self.__right = newright
if newright is not None:
newright.__parent = self
def getleft(self):
# returns the left child of the node.
return self.__left
def setleft(self, newleft):
# Sets the left child to the new node object newleft. Child nodes parent is also updated.
self.__left = newleft
if newleft is not None:
newleft.__parent = self
def getparent(self):
# returns the parent of the node
return self.__parent
def setparent(self, newparent, left=True):
# Sets the parent to the new node object newparent.
# Parents child pointer is also updated based on the value of the left.
# If left = True then sets node as left child of parent, sets as right child otherwise.
self.__parent = newparent
if newparent is not None:
if left:
newparent.__left = self
else:
newparent.__right = self
class BST:
def __init__(self, root=None):
if root is not None:
root.setparent(None)
self.__root = root
def getroot(self):
# Returns the root node of the tree
return self.__root
def setroot(self, node):
# Sets the root node of the tree
self.__root = node
def insertnode(self, node):
# Inserts a node to the correct position in a BST. A success returns true and failure returns false.
if self.__root is None:
self.__root = node
return True
else:
currentnode = self.__root
while True:
if node.getkey() == currentnode.getkey():
return False
elif node.getkey() < currentnode.getkey():
if currentnode.getleftchild() is None:
currentnode.setleftchild(node)
node.setparent(currentnode)
return True
else:
currentnode = currentnode.getleftchild()
else:
if currentnode.getrightchild() is None:
currentnode.setrightchild(node)
node.setparent(currentnode)
return True
else:
currentnode = currentnode.getrightchild()
def searchnode(self, searchkey):
# Search the BST for a node with searchkey. If found returns the first node with searchkey and failure returns false.
currentnode = self.__root
while currentnode is not None:
if searchkey == currentnode.getkey():
return currentnode
elif searchkey < currentnode.getkey():
currentnode = currentnode.getleftchild()
else:
currentnode = currentnode.getrightchild()
return False
def __removenode(self, node):
# Removes a node from the BST. This method uses the __successornode and __replacechild method.
if node.getleftchild() is None and node.getrightchild() is None:
parentnode = node.getparent()
if parentnode is None:
self.__root = None
else:
if node == parentnode.getleftchild():
parentnode.setleftchild(None)
else:
parentnode.setrightchild(None)
elif node.getleftchild() is None:
self.__replacechild(node.getparent(), node, node.getrightchild())
elif node.getrightchild() is None:
self.__replacechild(node.getparent(), node, node.getleftchild())
else:
successor = self.__successornode(node)
if successor != node.getrightchild():
self.__replacechild(successor.getparent(), successor, successor.getrightchild())
successor.setrightchild(node.getrightchild())
node.getrightchild().setparent(successor)
Trending now
This is a popular solution!
Step by step
Solved in 5 steps
