Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the template provided in the GitHub repository, using the class TreeNode that is also provided

Subject:Computer SciencePrice: Bought3

Share With

Lab 5: Binary Search Tree

Implement operations for a Binary Search Tree class starting from the template provided in the GitHub repository, using the class TreeNode that is also provided. You may (should) implement helper methods that make your code easier to write, read, and understand. You will also need to write test cases of your own as you develop the methods. You may use iterative and/or recursive functions in your implementation.

The following starter files are available on GitHub.

• binary_search_tree.py
• binary_search_tree_tests.py

Complete the implementations and ensure that the following are pushed to GitHub.

• binary_search_tree.py
• binary_search_tree_test.py
• queue_array.py (from lab 3)

 

My personal note: I believe this is a priority queue implementation because there is a "key" in the TreeNode constructor.

 

My question: What does the 'key' represent in the TreeNode constructor and can you show some examples on how to write the specified functions from binary_search_tree.py?

 

 

My code:

 

binary_search_tree.py:

 

from queue_array import Queue

class TreeNode:
    def __init__(self, key, data, left=None, right=None):
        self.key = key
        self.data = data
        self.left = left
        self.right = right

class BinarySearchTree:

    def __init__(self): # Returns empty BST
        self.root = None

    def is_empty(self): # returns True if tree is empty, else False
        if self.root == None:
            return True
        else:
            return False

    def search(self, key): # returns True if key is in a node of the tree, else False
        pass


    def insert(self, key, data=None): # inserts new node w/ key and data
        # If an item with the given key is already in the BST, 
        # the data in the tree will be replaced with the new data
        pass

    def find_min(self): # returns a tuple with min key and data in the BST
        # returns None if the tree is empty
        pass

    def find_max(self): # returns a tuple with max key and data in the BST
        # returns None if the tree is empty
        pass

    def tree_height(self): # return the height of the tree # returns None if tree is empty
        pass

    def inorder_list(self): # return Python list of BST keys representing in-order traversal of BST
        pass

    def preorder_list(self):  # return Python list of BST keys representing pre-order traversal of BST
        pass
        
    def level_order_list(self):  # return Python list of BST keys representing level-order traversal of BST
        # You MUST use your queue_array data structure from lab 3 to implement this method
        q = Queue(25000) # Don't change this!
        pass
        

 

queue_array.py:

 

class Queue:
    '''Implements an array-based, efficient first-in first-out Abstract Data Type 
       using a Python array (faked using a List)'''

    def __init__(self, capacity):
        '''Creates an empty Queue with a capacity'''
        self.capacity = capacity
        self.num_items = 0
        self.queue = [None] * capacity
        self.front = 0
        self.rear = 0

    def is_empty(self):
        '''Returns True if the Queue is empty, and False otherwise
           MUST have O(1) performance'''
        if self.num_items == 0:
            return True
        else:
            return False

    def is_full(self):
        '''Returns True if the Queue is full, and False otherwise
           MUST have O(1) performance'''
        if self.num_items == self.capacity:
            return True
        else:
            return False

    def enqueue(self, item):
        '''If Queue is not full, enqueues (adds) item to Queue 
           If Queue is full when enqueue is attempted, raises IndexError
           MUST have O(1) performance'''
        if self.is_full() == False:
            self.queue[self.rear] = item                    # adds item to rear of queue
            self.num_items += 1                             # increases the number of items in the queue by 1
            self.rear += 1                                  # increases the number by 1 to represent the location of the rear
        else:
            raise IndexError

    def dequeue(self):
        '''If Queue is not empty, dequeues (removes) item from Queue and returns item.
           If Queue is empty when dequeue is attempted, raises IndexError
           MUST have O(1) performance'''
        if self.is_empty() == False:
            item = self.queue[self.front]                   # to obtain the front item the location of the front item is accessed
            self.queue[self.front] = None                   # the front item is made None to represent the removal of the item
            self.front += 1                                 # the front of queue is added by 1 to move on to the next item in the queue
            self.num_items -= 1                             # the number of items lowers by 1
            return item
        else:
            raise IndexError


    def size(self):
        '''Returns the number of elements currently in the Queue, not the capacity
           MUST have O(1) performance'''
        return self.num_items

 

binary_search_tree_tests.py:

 

import unittest
from binary_search_tree import *

class TestLab4(unittest.TestCase):

    def test_simple(self):
        bst = BinarySearchTree()
        self.assertTrue(bst.is_empty())
        bst.insert(10, 'stuff')
        self.assertTrue(bst.search(10))
        self.assertEqual(bst.find_min(), (10, 'stuff'))
        bst.insert(10, 'other')
        self.assertEqual(bst.find_max(), (10, 'other'))
        self.assertEqual(bst.tree_height(), 0)
        self.assertEqual(bst.inorder_list(), [10])
        self.assertEqual(bst.preorder_list(), [10])
        self.assertEqual(bst.level_order_list(), [10])

if __name__ == '__main__': 
    unittest.main()

• Must pass at least these tests