Data structure (Python)

# Course: CS261 - Data Structures # Student Name: # Assignment: # Description: class Stack: """ Class implementing STACK ADT. Supported methods are: push, pop, top, is_empty DO NOT CHANGE THIS CLASS IN ANY WAY YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION """ def __init__(self): """ Initialize empty stack based on Python list """ self._data = [] def push(self, value: object) -> None: """ Add new element on top of the stack """ self._data.append(value) def pop(self) -> object: """ Remove element from top of the stack and return its value """ return self._data.pop() def top(self) -> object: """ Return value of top element without removing from stack """ return self._data[-1] def is_empty(self): """ Return True if the stack is empty, return False otherwise """ return len(self._data) == 0 def __str__(self): """ Return content of the stack as a string (for use with print) """ data_str = [str(i) for i in self._data] return "STACK: { " + ", ".join(data_str) + " }" class Queue: """ Class implementing QUEUE ADT. Supported methods are: enqueue, dequeue, is_empty DO NOT CHANGE THIS CLASS IN ANY WAY YOU ARE ALLOWED TO CREATE AND USE OBJECTS OF THIS CLASS IN YOUR SOLUTION """ def __init__(self): """ Initialize empty queue based on Python list """ self._data = [] def enqueue(self, value: object) -> None: """ Add new element to the end of the queue """ self._data.append(value) def dequeue(self) -> object: """ Remove element from the beginning of the queue and return its value """ return self._data.pop(0) def is_empty(self): """ Return True if the queue is empty, return False otherwise """ return len(self._data) == 0 def __str__(self): """ Return content of the stack as a string (for use with print) """ data_str = [str(i) for i in self._data] return "QUEUE { " + ", ".join(data_str) + " }" class TreeNode: """ Binary Search Tree Node class DO NOT CHANGE THIS CLASS IN ANY WAY """ def __init__(self, value: object) -> None: """ Init new Binary Search Tree DO NOT CHANGE THIS METHOD IN ANY WAY """ self.value = value # to store node's data self.left = None # pointer to root of left subtree self.right = None # pointer to root of right subtree def __str__(self): return str(self.value) class BST: def __init__(self, start_tree=None) -> None: """ Init new Binary Search Tree DO NOT CHANGE THIS METHOD IN ANY WAY """ self.root = None # populate BST with initial values (if provided) # before using this feature, implement add() method if start_tree is not None: for value in start_tree: self.add(value) def __str__(self) -> str: """ Return content of BST in human-readable form using in-order traversal DO NOT CHANGE THIS METHOD IN ANY WAY """ values = [] self._str_helper(self.root, values) return "TREE in order { " + ", ".join(values) + " }" def _str_helper(self, cur, values): """ Helper method for __str__. Does in-order tree traversal DO NOT CHANGE THIS METHOD IN ANY WAY """ # base case if cur is None: return # recursive case for left subtree self._str_helper(cur.left, values) # store value of current node values.append(str(cur.value)) # recursive case for right subtree self._str_helper(cur.right, values) # ------------------------------------------------------------------ # def add(self, value: object) -> None: """ TODO: Write this implementation """ pass def contains(self, value: object) -> bool: """ TODO: Write this implementation """ return True def get_first(self) -> object: """ TODO: Write this implementation """ return None def remove_first(self) -> bool: """ TODO: Write this implementation """ return True def remove(self, value) -> bool: """ TODO: Write this implementation """ return True def pre_order_traversal(self) -> Queue: """ TODO: Write this implementation """ return Queue() def in_order_traversal(self) -> Queue: """ TODO: Write this implementation """ return Queue() def post_order_traversal(self) -> Queue: """ TODO: Write this implementation """ return Queue() def by_level_traversal(self) -> Queue: """ TODO: Write this implementation """ return Queue() def is_full(self) -> bool: """ TODO: Write this implementation """ return True def is_complete(self) -> bool: """ TODO: Write this implementation """ return True def is_perfect(self) -> bool: """ TODO: Write this implementation """ return True def size(self) -> int: """ TODO: Write this implementation """ return 0 def height(self) -> int: """ TODO: Write this implementation """ return -1 def count_leaves(self) -> int: """ TODO: Write this implementation """ return 0 def count_unique(self) -> int: """ TODO: Write this implementation """ return 0 # BASIC TESTING - PDF EXAMPLES if __name__ == '__main__': """ add() example #1 """ print("\nPDF - method add() example 1") print("----------------------------") tree = BST() print(tree) tree.add(10) tree.add(15) tree.add(5) print(tree) tree.add(15) tree.add(15) print(tree) tree.add(5) print(tree) """ add() example 2 """ print("\nPDF - method add() example 2") print("----------------------------") tree = BST() tree.add(10) tree.add(10) print(tree) tree.add(-1) print(tree) tree.add(5) print(tree) tree.add(-1) print(tree) """ contains() example 1 """ print("\nPDF - method contains() example 1") print("---------------------------------") tree = BST([10, 5, 15]) print(tree.contains(15)) print(tree.contains(-10)) print(tree.contains(15)) """ contains() example 2 """ print("\nPDF - method contains() example 2") print("---------------------------------") tree = BST() print(tree.contains(0)) """ get_first() example 1 """ print("\nPDF - method get_first() example 1") print("----------------------------------") tree = BST() print(tree.get_first()) tree.add(10) tree.add(15) tree.add(5) print(tree.get_first()) print(tree) """ remove() example 1 """ print("\nPDF - method remove() example 1") print("-------------------------------") tree = BST([10, 5, 15]) print(tree.remove(7)) print(tree.remove(15)) print(tree.remove(15)) """ remove() example 2 """ print("\nPDF - method remove() example 2") print("-------------------------------") tree = BST([10, 20, 5, 15, 17, 7, 12]) print(tree.remove(20)) print(tree) """ remove() example 3 """ print("\nPDF - method remove() example 3") print("-------------------------------") tree = BST([10, 5, 20, 18, 12, 7, 27, 22, 18, 24, 22, 30]) print(tree.remove(20)) print(tree) # comment out the following lines # if you have not yet implemented traversal methods print(tree.pre_order_traversal()) print(tree.in_order_traversal()) print(tree.post_order_traversal()) print(tree.by_level_traversal()) """ remove_first() example 1 """ print("\nPDF - method remove_first() example 1") print("-------------------------------------") tree = BST([10, 15, 5]) print(tree.remove_first()) print(tree) """ remove_first() example 2 """ print("\nPDF - method remove_first() example 2") print("-------------------------------------") tree = BST([10, 20, 5, 15, 17, 7]) print(tree.remove_first()) print(tree) """ remove_first() example 3 """ print("\nPDF - method remove_first() example 3") print("-------------------------------------") tree = BST([10, 10, -1, 5, -1]) print(tree.remove_first(), tree) print(tree.remove_first(), tree) print(tree.remove_first(), tree) print(tree.remove_first(), tree) print(tree.remove_first(), tree) print(tree.remove_first(), tree) """ Traversal methods example 1 """ print("\nPDF - traversal methods example 1") print("---------------------------------") tree = BST([10, 20, 5, 15, 17, 7, 12]) print(tree.pre_order_traversal()) print(tree.in_order_traversal()) print(tree.post_order_traversal()) print(tree.by_level_traversal()) """ Traversal methods example 2 """ print("\nPDF - traversal methods example 2") print("---------------------------------") tree = BST([10, 10, -1, 5, -1]) print(tree.pre_order_traversal()) print(tree.in_order_traversal()) print(tree.post_order_traversal()) print(tree.by_level_traversal()) """ Comprehensive example 1 """ print("\nComprehensive example 1") print("-----------------------") tree = BST() header = 'Value Size Height Leaves Unique ' header += 'Complete? Full? Perfect?' print(header) print('-' * len(header)) print(f' N/A {tree.size():6} {tree.height():7} ', f'{tree.count_leaves():7} {tree.count_unique():8} ', f'{str(tree.is_complete()):10}', f'{str(tree.is_full()):7} ', f'{str(tree.is_perfect())}') for value in [10, 5, 3, 15, 12, 8, 20, 1, 4, 9, 7]: tree.add(value) print(f'{value:5} {tree.size():6} {tree.height():7} ', f'{tree.count_leaves():7} {tree.count_unique():8} ', f'{str(tree.is_complete()):10}', f'{str(tree.is_full()):7} ', f'{str(tree.is_perfect())}') print() print(tree.pre_order_traversal()) print(tree.in_order_traversal()) print(tree.post_order_traversal()) print(tree.by_level_traversal()) """ Comprehensive example 2 """ print("\nComprehensive example 2") print("-----------------------") tree = BST() header = 'Value Size Height Leaves Unique ' header += 'Complete? Full? Perfect?' print(header) print('-' * len(header)) print(f'N/A {tree.size():6} {tree.height():7} ', f'{tree.count_leaves():7} {tree.count_unique():8} ', f'{str(tree.is_complete()):10}', f'{str(tree.is_full()):7} ', f'{str(tree.is_perfect())}') for value in 'DATA STRUCTURES': tree.add(value) print(f'{value:5} {tree.size():6} {tree.height():7} ', f'{tree.count_leaves():7} {tree.count_unique():8} ', f'{str(tree.is_complete()):10}', f'{str(tree.is_full()):7} ', f'{str(tree.is_perfect())}') print('', tree.pre_order_traversal(), tree.in_order_traversal(), tree.post_order_traversal(), tree.by_level_traversal(), sep='\n')