Python代写 | CS261 Data Structures Assignment 4


CS261 Data Structures Assignment 4

Part 1 – Summary and Specific Instructions

1. Implement a BST class by completing provided skeleton code in the file .
Once completed, your implementation will include the following methods:

add(), contains(), remove()
get_first(), remove_first()
size(), height()
is_complete(), is_full(), is_perfect()

2. We will test your implementation with different types of objects, not just integers.
We guarantee that all such objects will have correct implementation of methods
__eq__, __lt__, __gt__, __ge__, __le__ and __str__.

3. The number of objects stored in the tree will be between 0 and 900, inclusive.

4. Tree must allow for duplicate values. When comparing objects, values less then
current node must be put in the left subtree, values greater than or equal to current
node must be put in the right subtree.
5. When removing a node, replace it with the leftmost child of the right subtree (aka
in-order successor). You do not need to ‘recursively’ continue this process.

If the deleted node only has one subtree (either right or left), replace the deleted
node with the root node of that subtree.
6. Variables in TreeNode and BST classes are not private. You are allowed to access and
change their values directly. You do not need to write any getter or setter methods
for them.
7. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures
and/or their methods.

In case you need ‘helper’ data structures in your solution, skeleton code includes
prewritten implementation of Queue and Stack classes. You are allowed to create
and use objects from those classes in your implementation.

You are not allowed to directly access any variables of the Queue or Stack classes.
All work must be done only by using class methods.

add (self, new_value: object) -> None:

This method adds new value to the tree, maintaining BST property. Duplicates must be
allowed and placed in the right subtree.

Example #1:
tree = BST()

Output :
TREE pre-order { }
TREE pre-order { 10, 5, 15 }
TREE pre-order { 10, 5, 15, 15, 15 }
TREE pre-order { 10, 5, 5, 15, 15, 15 }