Permalink
Cannot retrieve contributors at this time
Name already in use
A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?
5003CEM/STD_2.py
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
258 lines (210 sloc)
11.7 KB
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """ Basic BST code for inserting (i.e. building) and printing a tree | |
| Your ***second standard viva task*** (of 5) will be to implement a find method into | |
| the class BinaryTree from pseudocode. See the lab task sheet for Week 5. | |
| Your ***first advanced viva task*** (of 3) will be to implement a remove (delete) method | |
| into the class Binary Tree from partial pseudocode. See the lab task sheet for Week 5 (available in Week 5). | |
| There will be some ***introductory challenges*** in Week 4, with solutions released in Week 5. | |
| It is STRONGLY RECOMMENDED you attempt these! | |
| Since the given code is in python it is strongly suggested you stay with python; but | |
| if you want to reimplement as C++ this is also OK (see the Week 5 lab sheet guidance). | |
| """ | |
| import math | |
| """ Node class | |
| """ | |
| class Node: | |
| def __init__(self, data = None): | |
| self.data = data | |
| self.left = None | |
| self.right = None | |
| """ BST class with insert and display methods. display pretty prints the tree | |
| """ | |
| class BinaryTree: | |
| def __init__(self): | |
| self.root = None | |
| def insert(self, data): | |
| if self.root is None: | |
| self.root = Node(data) | |
| else: | |
| self._insert(data, self.root) | |
| def _insert(self, data, cur_node): | |
| if data < cur_node.data: | |
| if cur_node.left is None: | |
| cur_node.left = Node(data) | |
| else: | |
| self._insert(data, cur_node.left) | |
| elif data > cur_node.data: | |
| if cur_node.right is None: | |
| cur_node.right = Node(data) | |
| else: | |
| self._insert(data, cur_node.right) | |
| else: | |
| print("Value already present in tree") | |
| def display(self, cur_node): | |
| lines, _, _, _ = self._display(cur_node) | |
| for line in lines: | |
| print(line) | |
| def _display(self, cur_node): | |
| if cur_node.right is None and cur_node.left is None: | |
| line = '%s' % cur_node.data | |
| width = len(line) | |
| height = 1 | |
| middle = width // 2 | |
| return [line], width, height, middle | |
| if cur_node.right is None: | |
| lines, n, p, x = self._display(cur_node.left) | |
| s = '%s' % cur_node.data | |
| u = len(s) | |
| first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s | |
| second_line = x * ' ' + '/' + (n - x - 1 + u) * ' ' | |
| shifted_lines = [line + u * ' ' for line in lines] | |
| return [first_line, second_line] + shifted_lines, n + u, p + 2, n + u // 2 | |
| if cur_node.left is None: | |
| lines, n, p, x = self._display(cur_node.right) | |
| s = '%s' % cur_node.data | |
| u = len(s) | |
| first_line = s + x * '_' + (n - x) * ' ' | |
| second_line = (u + x) * ' ' + '\\' + (n - x - 1) * ' ' | |
| shifted_lines = [u * ' ' + line for line in lines] | |
| return [first_line, second_line] + shifted_lines, n + u, p + 2, u // 2 | |
| left, n, p, x = self._display(cur_node.left) | |
| right, m, q, y = self._display(cur_node.right) | |
| s = '%s' % cur_node.data | |
| u = len(s) | |
| first_line = (x + 1) * ' ' + (n - x - 1) * '_' + s + y * '_' + (m - y) * ' ' | |
| second_line = x * ' ' + '/' + (n - x - 1 + u + y) * ' ' + '\\' + (m - y - 1) * ' ' | |
| if p < q: | |
| left += [n * ' '] * (q - p) | |
| elif q < p: | |
| right += [m * ' '] * (p - q) | |
| zipped_lines = zip(left, right) | |
| lines = [first_line, second_line] + [a + u * ' ' + b for a, b in zipped_lines] | |
| return lines, n + m + u, max(p, q) + 2, n + u // 2 | |
| def find_i(self, target): | |
| '''Iterative method to search a given target in BST.''' | |
| if self.root: # if there is a root node | |
| cur_node = self.root # set the root of BST as cur_node | |
| while cur_node is not None: # while there is a node | |
| if cur_node.data == target: # if the cur_node is equal to the target | |
| return True # return True | |
| elif cur_node.data > target: # if the cur_node is bigger than the target | |
| cur_node = cur_node.left # set the cur_node to the node on the left side | |
| else: # if the cur_node is smaller than the target | |
| cur_node = cur_node.right # set the cur_node to the node on the right side | |
| return False # if the target is not found return False | |
| else: # if there isn't a root node | |
| return None # return None | |
| def find_r(self, target): | |
| '''Recursive method to search a given target in BST.''' | |
| if self.root: # if there is a root node | |
| if self._find_r(target, self.root): # if the sub-method _find_r finds the target | |
| return True # return True | |
| return False # if the target is not found return False | |
| else: # if there isn't a root node | |
| return None # return None | |
| def _find_r(self, target, cur_node): | |
| '''Sub-method for find_r method to search a given target in BST.''' | |
| if target > cur_node.data and cur_node.right: # if the target is bigger than cur_node | |
| # and there is a node to the right | |
| return self._find_r(target, cur_node.right) # return the _find_r function with the right node as argument | |
| elif target < cur_node.data and cur_node.left: # if the target is smaller than the cur_node | |
| # and there is a node to the left | |
| return self._find_r(target, cur_node.left) # return the _find_r function with the left node as argument | |
| if target == cur_node.data: # if the target is equal to the current node | |
| return True # return True | |
| def remove(self, target): | |
| '''Method that removes a node and reorganises the BST.''' | |
| if self.root is None: # if there isn't a root node | |
| return False # return False | |
| #if tree root is the target | |
| elif self.root.data == target: # if the root node is equal to target | |
| if self.root.left is None and self.root.right is None: # if there are no other nodes than root node then | |
| self.root = None # the root node is None | |
| elif self.root.left and self.root.right is None: # if there is only node to the left of the root node | |
| self.root = self.root.left # set the left node as root node | |
| elif self.root.left is None and self.root.right: # if there is only node to the right of the root node | |
| self.root = self.root.right # set the right node as root node | |
| elif self.root.left and self.root.right: # if there is a right node and left node | |
| self.if_left_and_right(self.root) # call if_left_and_right function | |
| #if tree root is not the target | |
| parent = None # set parent node to None | |
| node = self.root # set node to root node | |
| while node and node.data != target: # while there is a node and the node is not equal to the target | |
| parent = node # set node as parent | |
| if target < node.data: # if the target is smaller than the node | |
| node = node.left # set the left node of the current node as current node | |
| elif target > node.data: # if the target is bigger than the node | |
| node = node.right # set the right node of the current node as current node | |
| #target not found | |
| if node is None or node.data != target: # if there isn't any node or the node is not equal to target | |
| return False # return False | |
| #target has no children | |
| elif node.left is None and node.right is None: # if there isn't left or right node from the current node | |
| if target < parent.data: # if the target is smaller than the parent | |
| parent.left = None # set the left parent to None | |
| else: | |
| parent.right = None # set the right parent to None | |
| return True # return True | |
| #target has only left child | |
| elif node.left and node.right is None: # if there is only left node from the current node | |
| if target < parent.data: # if the target is smaller than the parent | |
| parent.left = node.left # set the left parent to left node | |
| else: | |
| parent.right = node.left # set the right parent to left node | |
| return True # return True | |
| #target has only right child | |
| elif node.right and node.left is None: # if there is only left node from the current node | |
| if target < parent.data: # if the target is smaller than the parent | |
| parent.left = node.right # set the left parent to right node | |
| else: | |
| parent.right = node.right # set the right parent to right node | |
| return True # return True | |
| #target has left and right child | |
| else: # if there is node to the left and to the right | |
| self.if_left_and_right(node) # call if_left_and_right function | |
| def if_left_and_right(self, node): | |
| '''Sub-method for deletion method. | |
| Reorganise the BST when the delete node has left and right children.''' | |
| delNodeParent = node # set the target node as delNodeParent | |
| delNode = node.right # set right node of the target as delNode | |
| while delNode.left: # while there is node to the left of the delNode | |
| delNodeParent = delNode # set delNodeParent as delNode | |
| delNode = delNode.left # set delNode as left node | |
| node.data = delNode.data | |
| if delNode.right: # if there is a node to the right of delNode | |
| if delNodeParent > delNode.data: # if delNodeParent is bigger than the delNode | |
| delNodeParent.left = delNode.right | |
| else: | |
| delNodeParent.right = delNode.right | |
| else: | |
| if delNode.data < delNodeParent.data: | |
| delNodeParent.left = None | |
| else: | |
| delNodeParent.right = None | |
| #example calls, which construct and display the tree | |
| bst = BinaryTree() | |
| bst.insert(4) | |
| bst.insert(2) | |
| bst.insert(6) | |
| bst.insert(1) | |
| bst.insert(3) | |
| bst.insert(5) | |
| bst.insert(7) | |
| bst.insert(8) | |
| #bst.insert(9) | |
| #bst.insert(10) | |
| #bst.insert(11) | |
| ##bst.insert(12) | |
| ##bst.insert(13) | |
| ##bst.insert(14) | |
| ##bst.insert(15) | |
| ##bst.insert(100) | |
| ##bst.insert(200) | |
| bst.display(bst.root) | |
| print(bst.find_i(4)) | |
| print(bst.find_i(8)) | |
| print(bst.find_r(3)) | |
| print(bst.find_r(10)) | |
| print(bst.remove(4)) | |
| bst.display(bst.root) | |
| print(bst.find_r(3)) | |
| print(bst.find_i(8)) | |