Write and test a recursive version of the find function in BST class, write preorder and postorder traversal generators for the BST class. Example to generate a preorder traversal we write code like list(myBST.preorder()). And add a __len__ operation to BST class such that calling len(myBST) shoud return the number of items. In python please. The code needed is below and what i want to do is what i asked above about the find function and the rest.
class TreeNode(object):
def __init__(self, data = None, left=None, right=None):
“””creates a tree node with specified data and references to left
and right children”””
self.item = data
self.left = left
self.right = right
from TreeNode import TreeNode
class BST:
#————————————————————
def __init__(self):
“””create empty binary search tree
post: empty tree created”””
self.root = None
#————————————————————
def insert(self, item):
“””insert item into binary search tree
pre: item is not in self
post: item has been added to self”””
if self.root is None: # handle empty tree case
self.root = TreeNode(item)
else:
# start at root
node = self.root
# loop to find the correct spot (break to exit)
while True:
if item == node.item:
raise ValueError(“Inserting duplicate item”)
if item < node.item: # item goes in left subtree
if node.left is not None: # follow existing subtree
node = node.left
else: # empty subtree, insert here
node.left = TreeNode(item)
break
else: # item goes in right subtree
if node.right is not None: # follow existing subtree
node = node.right
else: # empty subtree, insert here
node.right = TreeNode(item)
break
#————————————————————
def insert_rec(self, item):
“””insert item into binary search tree
pre: item is not in self
post: item has been added to self”””
self.root = self._subtreeInsert(self.root, item)
#————————————————————
def _subtreeInsert(self, root, item):
if root is None: # inserting into empty tree
return TreeNode(item) # the item becomes the new tree root
if item == root.item:
raise ValueError(“Inserting duplicate item”)
if item < root.item: # modify left subtree
root.left = self._subtreeInsert(root.left, item)
else: # modify right subtree
root.right = self._subtreeInsert(root.right, item)
return root # original root is root of modified tree
#————————————————————
def find(self, item):
“”” Search for item in BST
post: Returns item from BST if found, None otherwise”””
node = self.root
while node is not None and not(node.item == item):
if item < node.item:
node = node.left
else:
node = node.right
if node is None:
return None
else:
return node.item
#————————————————————
def delete(self, item):
“””remove item from binary search tree
post: item is removed from the tree”””
self.root = self._subtreeDelete(self.root, item)
#————————————————————
def _subtreeDelete(self, root, item):
if root is None: # Empty tree, nothing to do
return None
if item < root.item: # modify left
root.left = self._subtreeDelete(root.left, item)
elif item > root.item: # modify right
root.right = self._subtreeDelete(root.right, item)
else: # delete root
if root.left is None: # promote right subtree
root = root.right
elif root.right is None: # promote left subtree
root = root.left
else:
# root node can’t be deleted, overwrite it with max of
# left subtree and delete max node from the subtree
root.item, root.left = self._subtreeDelMax(root.left)
return root
#————————————————————
def _subtreeDelMax(self, root):
if root.right is None: # root is the max
return root.item, root.left # return max and promote left subtree
else:
# max is in right subtree, recursively find and delete it
maxVal, root.right = self._subtreeDelMax(root.right)
return maxVal, root
#————————————————————
def asList(self):
“””gets item in in-order traversal order
post: returns list of items in tree in orders”””
items = []
self._subtreeAddItems(self.root, items)
return items
#————————————————————
def _subtreeAddItems(self, root, itemList):
if root is not None:
self._subtreeAddItems(root.left, itemList)
itemList.append(root.item)
self._subtreeAddItems(root.right, itemList)
#————————————————————
def visit(self, f):
“””perform an in-order traversal of the tree
post: calls f with each TreeNode item in an in-order traversal
order”””
self._inorderVisit(self.root, f)
#————————————————————
def _inorderVisit(self, root, f):
if root is not None:
self._inorderVisit(root.left, f)
f(root.item)
self._inorderVisit(root.right, f)
#————————————————————
def __iter__(self):
“””in-order iterator for binary search tree”””
return self._inorderGen(self.root)
#————————————————————
def _inorderGen(self, root):
if root is not None:
# yield all the items in the left subtree
for item in self._inorderGen(root.left):
yield item
yield root.item
# yield all the items from the right subtree
for item in self._inorderGen(root.right):
yield item
#————————————————————
