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/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.
175 lines (146 sloc)
9.45 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 | |
#note: although replacement node will always be smaller than its parent node it might not be the case when we change the value of the deleted node, as we might have gone only one layer deep in which case it could be otherwise | |
#note: if delete node has no children, we have to set one of parents child to none instead of setting itself to none, as otherwise one of parents child nodes will still have value | |
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 find_i(self,T): | |
''' | |
Function for iteratively searching a value in a binary tree | |
Input: integer. target value | |
output: boolean. answer if value is inside the tree | |
''' | |
if self.root: #if tree does exist | |
cur_node = self.root #set root node as current node | |
while cur_node != None: #while the previous node was not the leaf node | |
if cur_node.data == T: #if value of current node is equal to target node | |
return True | |
elif cur_node.data > T: #if value of current node is greater than target node | |
cur_node = cur_node.left #change value of current node to the node left of the current node | |
else: #if value of current node is smaller than target node | |
cur_node = cur_node.right #change value of current node to the node right of the current node | |
return False | |
else: #if tree does not exist | |
return None | |
def find_r(self,T): | |
''' | |
Class method for calling a recursive function that searches for a value inside a binary tree | |
Input: integer. target value | |
output: boolean. answer if value is inside the tree | |
''' | |
if self.root: #if a tree exists | |
if self._find_r(T,self.root): #if called function returns True | |
return True | |
return False #if previously called function returns False | |
else: #if a tree does not exist | |
return None | |
def _find_r(self,T,cur_node): | |
''' | |
Class method for recursively searching a value in a binary tree | |
input: integer,tree class node attribute. target value, current node in a binary tree | |
output: boolean, answer if current value is inside a binary tree | |
''' | |
if T == cur_node.data: #base case of recursion, compare if target value and data of current node are equal | |
return True | |
if T > cur_node.data and cur_node.right: #if target value is bigger than data of current node, and right node for the current node exists | |
return self._find_r(T,cur_node.right) #recursevly call function with arguments being current target value, and right leaf of the current node | |
elif T < cur_node.data and cur_node.left: #if target value is smaller than data of current node, and left node for the current node exists | |
return self._find_r(T,cur_node.left) #recursevly call function with arguments being current target value, and left leaf of the current node | |
else: #else statement not neccesary, but improves readability of code | |
return False | |
#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) | |
valueInGraph = bst.find_i(2) | |
valueNotInGraph = bst.find_r(12) | |
print("Value had been found: ",valueInGraph) | |
print("Value had been found: ",valueNotInGraph) | |