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?
AdvancedALgorithmsComplete/ADV_1.py
Go to fileThis commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.
195 lines (168 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
| import math | |
| class Node: | |
| ''' | |
| Binary graph node which has a value and can be linked with two other instances of this class, its left and right branch | |
| ''' | |
| def __init__(self, data = None): | |
| self.data = data #set integer value of the node | |
| self.left = None #link to the left branch of the node(smaller value than the node) | |
| self.right = None #link to the right branch of the node(bigger value than the node) | |
| class BinaryTree: | |
| """ | |
| BST class with insert and display methods. display pretty prints the tree | |
| """ | |
| def __init__(self): | |
| self.root = None #create root of the tree BST attribute and set it to None | |
| def insert(self, data): | |
| ''' | |
| Class method for inserting nodes into the binary tree | |
| Input: Integer. value of the inserted node | |
| Output: no output. Binary tree is transformed instead | |
| ''' | |
| if self.root is None: #if tree has no root node | |
| self.root = Node(data) #create an instance of Node class with data as parameter and set it as root of the tree | |
| else: #if tree has a root node | |
| self._insert(data, self.root) #execute _insert class method with data and tree root as arguments | |
| def _insert(self, data, cur_node): | |
| ''' | |
| Class method for inserting values into the tree, when there already is a tree root | |
| Input: Integer,class instance.value of the node we want to insert,instance of a Node class the method is currently evaluating as a parent of the node we want to insert. | |
| Output:no output. Binary tree is transformed instead | |
| ''' | |
| if data < cur_node.data: #if value of inserted node is smaller than value of the currently evaluated node | |
| if cur_node.left is None: #if currently evaluated node has no left branch | |
| cur_node.left = Node(data) #create an instance of Node class with data as parameter and set it as left branch of currently evaluated node | |
| else: | |
| self._insert(data, cur_node.left) #recursively execute the class method with the same data attribute, and left branch of currently evaluated node as current node | |
| elif data > cur_node.data: #else if value of inserted node is bigger than value of the currently evaluated node | |
| if cur_node.right is None: #if currently evaluated node has no right branch | |
| cur_node.right = Node(data) #create an instance of Node class with data as parameter and set it as right branch of currently evaluated node | |
| else: | |
| self._insert(data, cur_node.right) #recursively execute the class method with the same data attribute, and right branch of currently evaluated node as current node | |
| else: #if currently evaluated node has the same value as data attribute | |
| 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 remove(self,T): | |
| ''' | |
| Class method for removing an element in a tree | |
| Input: integer, value that we want to delete | |
| Output: boolean, True if value was deleted, False if it did not exist | |
| ''' | |
| if self.root == None: #if there is no root node | |
| return False | |
| elif self.root.data == T: #if root node is targeted value | |
| if self.root.left == None and self.root.right == None: #Case 1: root node has no children | |
| self.root = None #remove the root node | |
| elif self.root.left and self.root.right == None: #Case 2: root node has only left child | |
| self.root = self.root.left #left child becomes the root node | |
| elif self.root.right and self.root.left == None: #Case 3: root node has only right child | |
| self.root = self.root.right #right child becomes the root node | |
| elif self.root.left and self.root.right: #Case 4: root node has both left and right child | |
| self.if_left_and_right(self.root) #call a method for deleting node with left and right child | |
| parent = None #set parent to none | |
| node = self.root #set current node to root | |
| while node and node.data != T: #while current node is not None, and current node value is not target value | |
| parent = node #set current node as parent node | |
| if T < node.data: #if target node is smaller than current node value | |
| node = node.left #set current node left child as current node | |
| elif T > node.data: #if target node is bigger than current node value | |
| node = node.right #set current node right child as current node | |
| if node == None or node.data != T: #Case 5: the target value is not in the tree | |
| return False | |
| elif node.left == None and node.right == None: #Case 6: target node has no children | |
| if T < parent.data: #if target value is smaller than value of the parent of the current node | |
| parent.left = None #we delete left child of the parent of the current node | |
| else: #if target value is bigger than value of the parent of the current node | |
| parent.right = None #we delete right child of the parent of the current node | |
| return True | |
| elif node.left and node.right == None: #Case 7: target node has only left child | |
| if T < parent.data: #if target value is smaller than value of the parent of the current node | |
| parent.left = node.left #set left child of current node as left child of the parent of the current node | |
| else: #if target value is bigger than value of the parent of the current node | |
| parent.right = node.left #set left child of current node as right child of the parent of the current node | |
| return True | |
| elif node.right and node.left == None: #Case 8: target node has only right child | |
| if T < parent.data: #if target value is smaller than value of the parent of the current node | |
| parent.left = node.right #set right child of current node as left child of the parent of the current node | |
| else: #if target value is bigger than value of the parent of the current node | |
| parent.right = node.right #set right child of current node as right child of the parent of the current node | |
| else: #Case 9: target node has both left and right child | |
| self.if_left_and_right(node) #call a method for deleting node with left and right child | |
| def if_left_and_right(self,node): | |
| ''' | |
| Class method for deleting a node in a binary tree when it has left and right child | |
| Input: BinarySearchTree Class Node attribute, Node which we want to delete | |
| Output: No output, the method rearranges node attributes in its class | |
| ''' | |
| replNodeParent = node #set the node that we want to delete as parent of a node that will replace it | |
| replNode = node.right #set right child of the node that we want to delete as replacement of that node | |
| while replNode.left: #while the replacement node has a left child | |
| replNodeParent = replNode #set replacement node as a parent for a new replacement node | |
| replNode = replNode.left #set left child of a replacement node as a new replacement node | |
| node.data = replNode.data #set data of a node that we want to delete to data of a replacement node | |
| if replNode.right: #if replacement node has a right child | |
| if replNodeParent.data > replNode.data: #if value of repl node parent is bigger than value of repl node | |
| replNodeParent.left = replNode.right #set right child of replacement node as left child of the parent of the replacement node | |
| else: | |
| replNodeParent.right = replNode.right #set right child of replacement node as right child of the parent of the replacement node | |
| else: | |
| if replNodeParent.data > replNode.data: #if value of repl node parent is bigger than value of repl node | |
| replNodeParent.left = None #delete the left child of the replacement node parent | |
| else: | |
| replNodeParent.right = None #delete the right child of the replacement node parent | |
| #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.display(bst.root) | |
| node2remove = 2 | |
| print('Node to remove: ',node2remove) | |
| bst.remove(node2remove) | |
| bst.display(bst.root) |