/
rnekrasov
/
Python
Обзор
Документация
Войти
/
rnekrasov
/
Python
Код
Запросы
0
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
binary_search_tree.py
382 строки
11 KB
slowy07
fix: baseException and fixing unused imported modules
01 авг 2021, 03:44
01 авг 2021, 03:44
881438b
Код
Авторство
О чём код?
class Node: """Class for node of a tree""" def __init__(self, info): """Initialising a node""" self.info = info self.left = None self.right = None # self.level = None def __str__(self): return str(self.info) def __del__(self): del self class BinarySearchTree: """Class for BST""" def __init__(self): """Initialising a BST""" self.root = None def insert(self, val): """Creating a BST with root value as val""" # Check if tree has root with None value if self.root is None: self.root = Node(val) # Here the tree already has one root else: current = self.root while True: if val < current.info: if current.left: current = current.left else: current.left = Node(val) break elif val > current.info: if current.right: current = current.right else: current.right = Node(val) break else: break def search(self, val, to_delete=False): current = self.root prev = -1 while current: if val < current.info: prev = current current = current.left elif val > current.info: prev = current current = current.right elif current.info == val: if not to_delete: return "Match Found" return prev else: break if not to_delete: return "Not Found" # Method to delete a tree-node if it exists, else error message will be returned. def delete(self, val): prev = self.search(val, True) # Check if node exists if prev is not None: # Check if node is the Root node if prev == -1: temp = self.root.left prev2 = None while temp.right: prev2 = temp temp = temp.right if prev2 is None: self.root.left = temp.left self.root.info = temp.info else: prev2.right = None self.root.info = temp.info print("Deleted Root ", val) # Check if node is to left of its parent elif prev.left and prev.left.info == val: # Check if node is leaf node if prev.left.left is prev.left.right: prev.left = None print("Deleted Node ", val) # Check if node has child at left and None at right elif prev.left.left and prev.left.right is None: prev.left = prev.left.left print("Deleted Node ", val) # Check if node has child at right and None at left elif prev.left.left is None and prev.left.right: prev.left = prev.left.right print("Deleted Node ", val) # Here node to be deleted has 2 children elif prev.left.left and prev.left.right: temp = prev.left while temp.right is not None: prev2 = temp temp = temp.right prev2.right = None prev.left.info = temp.info print("Deleted Node ", val) else: print("Error Left") # Check if node is to right of its parent elif prev.right.info == val: flag = 0 # Check is node is a leaf node if prev.right.left is prev.right.right: prev.right = None flag = 1 print("Deleted Node ", val) # Check if node has left child at None at right if prev.right and prev.right.left and prev.right.right is None: prev.right = prev.right.left print("Deleted Node ", val) # Check if node has right child at None at left elif prev.right and prev.right.left is None and prev.right.right: prev.right = prev.right.right print("Deleted Node ", val) elif prev.right and prev.right.left and prev.right.right: temp = prev.right while temp.left is not None: prev2 = temp temp = temp.left prev2.left = None prev.right.info = temp.info print("Deleted Node ", val) else: if flag == 0: print("Error") else: print("Node doesn't exists") def __str__(self): return "Not able to print tree yet" def is_bst(node, lower_lim=None, upper_lim=None): """Function to find is a binary tree is a binary search tree.""" if lower_lim is not None and node.info < lower_lim: return False if upper_lim is not None and node.info > upper_lim: return False is_left_bst = True is_right_bst = True if node.left is not None: is_left_bst = is_bst(node.left, lower_lim, node.info) if is_left_bst and node.right is not None: is_right_bst = is_bst(node.right, node.info, upper_lim) return is_left_bst and is_right_bst def postorder(node): # L R N : Left , Right, Node if node is None: return if node.left: postorder(node.left) if node.right: postorder(node.right) print(node.info) def inorder(node): # L N R : Left, Node , Right if node is None: return if node.left: inorder(node.left) print(node.info) if node.right: inorder(node.right) def preorder(node): # N L R : Node , Left, Right if node is None: return print(node.info) if node.left: preorder(node.left) if node.right: preorder(node.right) # Levelwise def bfs(node): queue = [] if node: queue.append(node) while queue != []: temp = queue.pop(0) print(temp.info) if temp.left: queue.append(temp.left) if temp.right: queue.append(temp.right) def preorder_itr(node): # N L R : Node, Left , Right stack = [node] values = [] while stack != []: temp = stack.pop() print(temp.info) values.append(temp.info) if temp.right: stack.append(temp.right) if temp.left: stack.append(temp.left) return values def inorder_itr(node): # L N R : Left, Node, Right # 1) Create an empty stack S. # 2) Initialize current node as root # 3) Push the current node to S and set current = current->left until current is NULL # 4) If current is NULL and stack is not empty then # a) Pop the top item from stack. # b) Print the popped item, set current = popped_item->right # c) Go to step 3. # 5) If current is NULL and stack is empty then we are done. stack = [] current = node while True: if current != None: stack.append(current) # L current = current.left elif stack != []: temp = stack.pop() print(temp.info) # N current = temp.right # R else: break def postorder_itr(node): # L R N # 1. Push root to first stack. # 2. Loop while first stack is not empty # 2.1 Pop a node from first stack and push it to second stack # 2.2 Push left and right children of the popped node to first stack # 3. Print contents of second stack s1, s2 = [node], [] while s1 != []: temp = s1.pop() s2.append(temp) if temp.left: s1.append(temp.left) if temp.right: s1.append(temp.right) print(*(s2[::-1])) def bst_frm_pre(pre_list): box = Node(pre_list[0]) if len(pre_list) > 1: if len(pre_list) == 2: if pre_list[1] > pre_list[0]: box.right = Node(pre_list[1]) else: box.left = Node(pre_list[1]) else: all_less = False for i in range(1, len(pre_list)): if pre_list[i] > pre_list[0]: break else: all_less = True if i != 1: box.left = bst_frm_pre(pre_list[1:i]) if not all_less: box.right = bst_frm_pre(pre_list[i:]) return box # Function to find the lowest common ancestor of nodes with values c1 and c2. # It return value in the lowest common ancestor, -1 indicates value returned for None. # Note that both values v1 and v2 should be present in the bst. def lca(t_node, c1, c2): if c1 == c2: return c1 current = t_node while current: if c1 < current.info and c2 < current.info: current = current.left elif c1 > current.info and c2 > current.info: current = current.right else: return current.info return -1 # Function to print element vertically which lie just below the root node def vertical_middle_level(t_node): e = (t_node, 0) # 0 indicates level 0, to left we have -ve and to right +ve queue = [e] ans = [] # Do a level-order traversal and assign level-value to each node while queue != []: temp, level = queue.pop(0) if level == 0: ans.append(str(temp.info)) if temp.left: queue.append((temp.left, level - 1)) if temp.right: queue.append((temp.right, level + 1)) return " ".join(ans) def get_level(n, val): c_level = 0 while n.info != val: if val < n.info: n = n.left elif val > n.info: n = n.right c_level += 1 if n is None: return -1 return c_level def depth(node): if node is None: return 0 l_depth, r_depth = 0, 0 if node.left: l_depth = depth(node.left) if node.right: r_depth = depth(node.right) # print(node.info, l_depth, r_depth) return 1 + max(l_depth, r_depth) t = BinarySearchTree() t.insert(10) t.insert(5) t.insert(15) t.insert(3) t.insert(1) t.insert(0) t.insert(2) t.insert(7) t.insert(12) t.insert(18) t.insert(19) print(depth(t.root)) # inorder(t.root) # print() # print(t.search(5)) # t.delete(7) # t.delete(5) # t.delete(3) # t.delete(15) # inorder(t.root) # print() # t.delete(2) # t.delete(3) # t.delete(7) # t.delete(19) # t.delete(1) # inorder(t.root) # b = BinarySearchTree() # b.root = bst_frm_pre(preorder_itr(t.root)) # print(preorder_itr(b.root) == preorder_itr(t.root)) # print(lca(t.root, 3, 18)) # print(vertical_middle_level(t.root)) # print(get_level(t.root, 1))