Introduction
python，，，
Requirement
You may begin this assignment with the sample BST code.
Add the following functionality to the code:
1. Modify the code so that each node stores not only a number (which is used as the sort value (or “key”) of the node), but also a string containing the name of a person. So, the root node of a BST may contain for its data: [40, “Wendy”], the left child of the root may be [18, “Carol”]. Modify all functions that this change affects.
2. Add a function called “changeLeaves” which changes the person’s name contained in the leaf nodes to “Leif”. Recall that a leaf node is one that has no children. Your function should take one parameter, the root of a BST, and it should return the root of the (changed) tree.
3. Add a function called “countNodes” that counts the number of nodes that contain names starting with “w” or “W”. Your function should take one parameter, the head of a BST and it should return the number of nodes matching the given condition.
4. Add a function called “printReverse” that prints all the nodes in reverse order. That is, the node with the largest numerical value is printed first and the node with the smallest numerical value is printed last. Your function should take as a parameter the root of a BST and it should return nothing.
5. Write a function that will convince the TA that your code works. Be sure to explain what you are showing. You should cover special cases such as empty trees.
What to Submit
Submit a single file containing your entire program. DO NOT ZIP THE FILE. You do not need to include the data file. We will test your program on a different grid.
Be sure you document your program appropriately. Each function should include a header comment explaining what the function does, what the parameters are and what it returns.
Marking
The assignment will be marked using a rubric. Rubrics provide a guide to the TAs however they are not all inclusive. We may deduct marks for unanticipated errors.
I do not give extensions on assignments. A 24 hour extension is available to everyone but comes with a 2 mark penalty. Please do not ask for another extension unless you have a very, very good reason.
Academic Integrity
Please refer to the notes on Academic Integrity. It is ok (and encouraged) to talk about solutions with your friends but please do your own work. It is also ok to take snippits of code from the internet as long as the code does not solve the entire problem. If you use snippits of code, please document it in your comments by adding a URL indicating where the code came from.
“””
This module implements binary search trees.
The tree elements may be of any type. Duplicates are not allowed.
Example for CISC 121
“””
# A BST node is a dict with three elements:
# 1. data: the value in the node
# 2. left: a reference to the left subtree
# 3. right: a reference to the right subtree
# Prints an indented display of the tree – useful for debugging.
# The output will look kind of like a sideways version of a drawing
# of the tree.
def display(tree, indent=0):
if tree == None: # empty
pass
else:
# right tree first (so it’s on the right when you tilt your
# head to the left to look at the display)
display(tree[‘right’],indent+1)
print(“ “ * indent + str(tree[‘data’]))
# now the left tree
display(tree[‘left’],indent+1)
# adds a value to a BST and returns a pointer to the modified BST
def add(tree, value):
if tree == None:
return {‘data’:value, ‘left’:None, ‘right’:None}
elif value tree[‘data’]:
tree[‘right’] = add(tree[‘right’],value)
return tree
else: # value == tree[‘data’]
return tree # ignore duplicate
def printValues(tree):
if tree == None:
return
printValues(tree[‘left’])
print(tree[‘data’])
printValues(tree[‘right’])
def main():
myTree = None #create an empty tree
#Create a tree with the nodes [20, 2, 25, 14, 1, 23, 75, 93, 74]
#Note that the add function always returns the root of the BST!
myTree = add(myTree, 20)
myTree = add(myTree, 2)
myTree = add(myTree, 25)
myTree = add(myTree, 14)
myTree = add(myTree, 1)
myTree = add(myTree, 23)
myTree = add(myTree, 75)
myTree = add(myTree, 93)
myTree = add(myTree, 74)
display(myTree, 0)
printValues(myTree)
main()