QuestionQuestion

Transcribed TextTranscribed Text

Binary Search Tree Purpose: This project will give you experience with Binary Search Trees. The next project builds of this one project, SO be sure you document your code well and understand well how it works. Implement the two classes defined in the following UML diagrams Binary SearchTree root: Node Node BinarySearchTree() data : integer is_empty() : Bool left_child : Node add(data) : None right_child : Node add_helper(cursor, data) : Node height : integer find(data) : Node find_helper(cursor, data) : Node Node(data, left_child-None, right_child=None) - remove(data) : None is_leaf() : Bool remove_helper(cursor, data) : Node update_height() : None preorder(): list _str__0 : string preorder_helper(cursor, output) : list height() : integer str 0 : string print_helper(cursor, offset) : string len (): integer length_helper(cursor, offset) : integer Binary Search Tree ADT (binarysearchtree.py) You will implement a BST that supports the following operations: is_empty: Return True if empty, False otherwise. __len_ : Return the number of items in the tree. height: Return the height of the tree _str_ : Return a string that shows the shape of the tree when printed add(item): Add item to its proper place in the tree remove(item): Remove item from the tree. find (item): Return the matched item. If item is not in the tree, return None. inorder: Return an iterator that performs an inorder traversal of the tree height: returns the height of the tree (height of the root node) Recursion The following operations must be implemented recursively: add find remove preorder __str_ len__ These functions should all use a "helper" function to do the actual recursion and work. So that the UnitTest can verify that recursion was properly used, at the beginning of every "helper" function, you must add the following line: recursrion helper. DO NOT CALL DIRECTLY RecursionCounter() And at the beginning of the module you will have to add: from recursioncounter import RecursionCounter # place at the beginning of the mod ule Main Program (main.py) You must implement a main function that does the following: 1. Insert the following numbers into the tree in this order: 221,26,30,9,4,14,28,18,15,10,2,3,7 2. Print a preorder traversal of the tree 3. Print the tree 4. Remove the following data from the tree: 21,9,4,18,15,7 5. Print the tree The output should look similar to Figure 1. 21, 9, 4, 2, 3, 7, 14, 10, 18, 15, 26, 30, 28, 21 (4) 9 (3) 4 (2) 2 (1) [Empty] 3 (0) [leaf] 7 (0) [leaf] 14 (2) 10 (0) [leaf] 18 (1) 15 (0) [leaf] [Empty] 26 (2) [Empty] 30 (1) 28 (0) [leaf] [Empty] 26 (3) 10 (2) 2 (1) [Empty] 3 (0) [leaf] 14 (0) [leaf] 30 (1) 28 (0) [leaf] [Empty] Figure 1. Example output showing preorder traversal and printing the tree. Test Cases Following is the set of assertion-based - test cases that your program must pass, and by which your code will be graded. You will be given the pytest unit test code to run against your code as you develop it. This allows you to learn how test are written, and to know what your score is going to be when the code is graded before you submit it Test Empty BST Create an empty BST assert size == 0 assertis_empty is True Test Size Create an empty tree seed random number generator with 0 Insert 123 random integers in range 1, 400 into the tree assert size == 123 Test Height Create an empty tree Insert value 123 into the tree assert height =: 0 Insert 12 and 2 into the tree assert height =: 1 Test Insert and Find Create an empty tree seed random number generator with 0 Generate a list of 123 random integers in range 1, 400 Insert each integer into the list in the order they appear in the list above assert find (first item in list) =: first item in list assert find(401) == None Test Remove Create an empty tree seed random number generator with 0 Generate a list of 10 random integers in range 1, 100 Insert each integer into the list in the order they appear in the list above remove (first item in list) assert find 1(first item in list) == None Test Preorder Traversal Create an empty tree seed random number generator with 0 Generate a list of 123 random integers in range 1, 400 Insert them in the list in the order they appear in the list above assert returned value is a list of length 123 do preorder traversal assert that the first element of the random integers is the first element of the returned list Test String Implement scenario given in Figure 1 and implemented in the main program, but as a test case. Test Recursion the following functions will be tested to verify that they use recursion to do their work add find remove preorder _str __len__ (remember to have the line RecursionCounter 0 at the beginning of every recursive helper function) Test Code Quality PyLint will be run on main.py and binarysearchtree.py. Both must have at least an 8.5 PyLint score. Grading (100 points) Passes TestNode 10 Passed TestBinarySearchTre 35 Passed RecursionTests 30 passed Coding Standards 25 Turn in to Canvas: main.py binarysearchtree.py

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

import unittest
from binarysearchtree import Node, BinarySearchTree
from random import seed, sample
from main import main as mn
from recursioncounter import RecursionCounter as rc
import io
import sys

class TestNode(unittest.TestCase):
    def test_node_creation(self):
       node = Node(12345)
       self.assertTrue(node.is_leaf())
       self.assertEqual(node.data, 12345)
       self.assertEqual(node.height, 0)
       node.update_height()
       self.assertEqual(node.height, 0)

class TestBinarySearchTree(unittest.TestCase):
    def test_tree_creation(self):
       bst = BinarySearchTree()
       self.assertEqual(len(bst), 0)
       self.assertTrue(bst.is_empty())

    def test_tree_size(self):
       bst = BinarySearchTree()
       seed(0)
       data = sample(range(1, 400), k=123)
       for datum in data:
            bst.add(datum)
       self.assertEqual(len(bst), 123)

    def test_tree_height(self):
       bst = BinarySearchTree()
       bst.add(123)
       self.assertEqual(bst.height(), 0)
       bst.add(12)
       bst.add(2)
       self.assertEqual(bst.height(), 2)

    def test_find(self):
       bst = BinarySearchTree()
       seed(0)
       data = sample(range(1, 400), k=123)
       for datum in data:
            bst.add(datum)
       self.assertEqual(bst.find(data[0]).data, data[0])
       self.assertEqual(bst.find(401), None)

    def test_remove(self):
       bst = BinarySearchTree()
       seed(0)
       data = sample(range(1, 100), k=10)
       for datum in data:
            bst.add(datum)
       bst.remove(data[0])
       self.assertEqual(bst.find(data[0]), None)

    def test_preorder(self):
       bst = BinarySearchTree()
       seed(0)
       data = sample(range(1, 400), k=123)
       for datum in data:
            bst.add(datum)
21, 9, 4, 2, 3, 7, 14, 10, 18, 15, 26, 30, 28,
21 (4)
9 (3)
4 (2)
2 (1)
[Empty]
3 (0) [leaf]
7 (0) [leaf]
14 (2)
10 (0) [leaf]
18 (1)
15 (0) [leaf]
[Empty]
26 (2)
[Empty]
30 (1)
28 (0) [leaf]
[Empty]
26 (3)
10 (2)
2 (1)
[Empty]
3 (0) [leaf]
14 (0) [leaf]
30 (1)
28 (0) [leaf]
[Empty]
Figure 1. Example output showing preorder traversal and printing the tree.
Test Cases
Following is the set of assertion-based - test cases that your program must pass, and by
which your code will be graded. You will be given the pytest unit test code to run against
your
code
as
you
develop
it.
This
allows
you
to
learn
how
test
are
written,
and
to
know
what
your score is going to be when the code is graded before you submit it
Test Empty BST
Create an empty BST
assert size == 0 assertis_empty is True
Test Size
Create an empty tree
seed random number generator with 0
Insert 123 random integers in range 1, 400 into the tree assert size == 123
Test Height
Create an empty tree Insert value 123 into the tree
assert height =: 0
Insert 12 and 2 into the tree
assert height =: 1
Test Insert and Find
Create an empty tree
seed random number generator with 0
Generate a list of 123 random integers in range 1, 400
Insert each integer into the list in the order they appear in the list above
assert find (first item in list) =: first item in list
assert find(401) == None
Test Remove
Create an empty tree
seed random number generator with 0
Generate a list of 10 random integers in range 1, 100
Insert each integer into the list in the order they appear in the list above
remove (first item in list)
assert find 1(first item in list) == None
Test Preorder Traversal
Create an empty tree
seed random number generator with 0
Generate a list of 123 random integers in range 1, 400
Insert them in the list in the order they appear in the list above
assert returned value is a list of length 123
do preorder traversal assert that the first element of the random integers is the first
element of the returned list
Test String
Implement scenario given in Figure 1 and implemented in the main program, but as a test
case.
Test Recursion
the following functions will be tested to verify that they use recursion to do their work
add
find
remove
preorder
_str
__len__
(remember to have the line RecursionCounter 0 at the beginning of every recursive helper
function)
Test Code Quality
PyLint will be run on main.py and binarysearchtree.py. Both must have at least an 8.5
PyLint score.
Grading (100 points)
Passes TestNode
10
Passed TestBinarySearchTre
35
Passed RecursionTests
30
passed Coding Standards
25
Turn in to Canvas:
main.py
binarysearchtree.py...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$25.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats