Last active
May 22, 2018 07:15
-
-
Save sudhanshuptl/2e5f62f502aadaba9d751ee04542e19c to your computer and use it in GitHub Desktop.
Complete Binary tree in python (using oops ). Also defined many different operations and algorithms for it.
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
__author__='Sudhanshu Patel' | |
''' | |
Binary search tree implementation | |
# goes left if key less than node.key else right | |
1. insetion | |
2. Preorder | |
3. postorder | |
4. inorder traversal | |
5. find max depth | |
6. print all leaf node | |
7. search a key in binary search tree | |
8. Level Order Traversal | |
9. level order traversal without recursion | |
10. delete node with given key | |
''' | |
class Node: | |
def __init__(self, key): | |
self.left = None | |
self.right = None | |
self.key = key | |
class BinarySearchTree(object): | |
pre_order = 'PREORDER' | |
in_order = 'INORDER' | |
post_order = 'POSTORDER' | |
def __init__(self, root=None): | |
self.root = root | |
def get_root(self): | |
return self.root | |
def insert(self, key): | |
if self.root is None: | |
self.root = Node(key) | |
else: | |
self.utility_insert(self.root, key) | |
def utility_insert(self, this_node, key): | |
if this_node.key > key: | |
if this_node.left is None: | |
this_node.left = Node(key) | |
else: | |
self.utility_insert(this_node.left, key) | |
else: | |
if this_node.right is None: | |
this_node.right = Node(key) | |
else: | |
self.utility_insert(this_node.right, key) | |
def print(self, traversal_type='INORDER'): | |
if traversal_type.upper() == self.in_order: | |
print('\nInorder Traversal :>') | |
self.inorder(self.root) | |
elif traversal_type.upper() == self.pre_order: | |
print('\nPreorder Traversal :>') | |
self.preorder(self.root) | |
elif traversal_type.upper() == self.post_order: | |
print('\nPostorder Traversal :>') | |
self.postorder(self.root) | |
def inorder(self, this_node): | |
if this_node: | |
self.inorder(this_node.left) | |
print(this_node.key, ', ', end='') | |
self.inorder(this_node.right) | |
def preorder(self, this_node): | |
if this_node: | |
print(this_node.key, ', ', end='') | |
self.preorder(this_node.left) | |
self.preorder(this_node.right) | |
def postorder(self, this_node): | |
if this_node: | |
self.postorder(this_node.left) | |
self.postorder(this_node.right) | |
print(this_node.key, ', ', end='') | |
def max_depth(self, this_node): | |
''' | |
calculate number of node from root to max depth | |
:param this_node: root node | |
:return: height of tree (root node has height 1): | |
''' | |
if this_node is None: | |
return 0 | |
left_subtree = self.max_depth(this_node.left) | |
right_subtree = self.max_depth(this_node.right) | |
return max(left_subtree, right_subtree)+1 | |
def print_all_leaf_node(self, this_node): | |
''' | |
print all leaf Node | |
:param this_node: this_node | |
:return: print values at leave node | |
''' | |
if this_node.left: | |
self.print_all_leaf_node(this_node.left) | |
if this_node.right: | |
self.print_all_leaf_node(this_node.right) | |
if this_node.right is None and this_node.left is None: | |
print(this_node.key, ', ', end='') | |
@staticmethod | |
def search(self, this_node, key): | |
if this_node is None: | |
print('Key (',key , ')is Not Found !') | |
return False | |
elif this_node.key == key: | |
print('Key (=', key, ') Found :) ') | |
return True | |
elif key < this_node.key: | |
self.search(this_node.left, key) | |
else: | |
self.search(this_node.right, key) | |
def level_order_traversal(self, queue): | |
''' | |
input root node as a list | |
print 'level order traversal ' | |
:return: None | |
''' | |
queue_new = [] | |
data = [] | |
print() | |
if not queue: | |
return | |
else: | |
for node in queue: | |
#print('<-->', node.key, end='') | |
data.append(node.key) | |
if node.left is not None: | |
queue_new.append(node.left) | |
if node.right is not None: | |
queue_new.append(node.right) | |
print(' <> '.join([str(x) for x in data])) | |
#print('\n________________________') | |
self.level_order_traversal(queue_new) | |
def level_order_without_recursion(self): | |
queue = [self.root] | |
data = [] | |
while queue: | |
node = queue.pop(0) | |
data.append(str(node.key)) | |
if node.left is not None: | |
queue.append(node.left) | |
if node.right is not None: | |
queue.append(node.right) | |
print(' level order Traversal without recursion :') | |
print(' <> '.join(data)) | |
def find_inorder_succesor(self, this_node): | |
ptr = this_node | |
while ptr.left is not None: | |
ptr = ptr.left | |
return ptr | |
def delete_node(self, this_node, key): | |
if this_node is None: | |
return this_node | |
if key < this_node.key: | |
this_node.left = self.delete_node(this_node.left, key) | |
elif key > this_node.key: | |
this_node.right = self.delete_node(this_node.right, key) | |
else: | |
# case 1 : delete node with no child or only one child node | |
if this_node.left is None: | |
temp = this_node.right | |
this_node = None | |
return temp | |
elif this_node.right is None: | |
temp = this_node.left | |
this_node = None | |
return temp | |
# case 2 : Have 2 child node: then assign this node to its inorder successor | |
temp = self.find_inorder_succesor(this_node.right) | |
this_node.key = temp.key | |
this_node.right = self.delete_node(this_node.right, temp.key) | |
return this_node | |
def delete_tree(self, this_node): | |
if this_node: | |
self.delete_tree(this_node.left) | |
self.delete_tree(this_node.right) | |
this_node = None | |
if __name__ == '__main__': | |
print('Binary Search TREE') | |
bst = BinarySearchTree() | |
bst.insert(3) | |
bst.insert(1) | |
bst.insert(2) | |
bst.insert(4) | |
bst.insert(5) | |
bst.print() | |
bst.print(traversal_type='preorder') | |
bst.print(traversal_type='postorder') | |
print('\nMax Depth >> ', end='') | |
print(bst.max_depth(bst.root)) | |
print('Print leaf Node >>') | |
bst.print_all_leaf_node(bst.root) | |
print(' \nSearch a node') | |
bst.search(bst.get_root(), 11 ) | |
bst.search(bst.get_root(), 4) | |
print('Level Order Traversal') | |
bst.level_order_traversal([bst.get_root()]) | |
bst.level_order_without_recursion() | |
# delete node with given key | |
bst.delete_node(bst.get_root(), 2) | |
print('Level Order Traversal after deletion') | |
bst.level_order_traversal([bst.get_root()]) | |
bst.level_order_without_recursion() | |
# delete Tree | |
print('delete tree data structre') | |
bst.delete_tree(bst.get_root()) | |
bst.level_order_traversal([bst.get_root()]) |
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
from BinarySearchTree import BinarySearchTree, Node | |
import copy | |
''' | |
1. Insertion Logic | |
2. Search a node | |
3. creating Mirror image of tree | |
4 . delete a Node from tree | |
''' | |
class CompleteBinaryTree(BinarySearchTree): | |
''' | |
most of tree traversal logic is same just need to update insertion and updation logic | |
''' | |
def __init__(self, root = None): | |
super().__init__(root) | |
def insert(self, key): | |
''' | |
:param key: | |
insert node with value key at first available position in level order traversal | |
:return:None | |
''' | |
node = Node(key) | |
if self.root is None: | |
self.root = node | |
return | |
queue = [self.get_root()] | |
while queue: | |
this_node = queue.pop(0) | |
if this_node.left is not None: | |
queue.append(this_node.left) | |
else: | |
this_node.left = node | |
break | |
if this_node.right is not None: | |
queue.append(this_node.right) | |
else: | |
this_node.right = node | |
break | |
@staticmethod | |
def search(this_node, key): | |
if this_node is None: | |
return False | |
elif this_node.key == key: | |
return True | |
return CompleteBinaryTree.search(this_node.left, key) or CompleteBinaryTree.search(this_node.right, key) | |
def create_mirror_image(self, this_node): | |
''' | |
:param this_node: | |
:return: new tree mirror image tree i.e 180 degree rotated from vertical line | |
''' | |
if this_node: | |
self.create_mirror_image(this_node.left) | |
self.create_mirror_image(this_node.right) | |
# Actual swapping | |
this_node.left, this_node.right = this_node.right, this_node.left | |
return this_node | |
def delete_deepest(self, last_node): | |
queue = [self.root] | |
while queue: | |
this_node = queue.pop(0) | |
if this_node.left is not None: | |
if this_node.left == last_node: | |
this_node.left = None | |
del last_node | |
return | |
else: | |
queue.append(this_node.left) | |
if this_node.right is not None: | |
if this_node.right == last_node: | |
this_node.right = None | |
del last_node | |
return | |
else: | |
queue.append(this_node.right) | |
def delete(self, key): | |
''' | |
find node with value key and deppest node , swap and delete deepest node | |
''' | |
if self.root is None: | |
print('Tree is Empty') | |
return | |
queue = [self.root] | |
while queue: | |
this_node = queue.pop(0) | |
if this_node.key == key: | |
key_node = this_node | |
if this_node.left is not None: | |
queue.append(this_node.left) | |
if this_node.right is not None: | |
queue.append(this_node.right) | |
key_node.key = this_node.key # here this node is last node or deepest node | |
self.delete_deepest(this_node) | |
@staticmethod | |
def are_mirrors(root1, root2): | |
''' | |
:param root1: | |
:param root2: | |
:return return true if these two trees are mirror images of each other: | |
''' | |
if root1 is None and root2 is None: | |
return True | |
if root1 is None or root2 is None: | |
return False | |
if root1.key != root2.key: | |
return False | |
else: | |
return CompleteBinaryTree.are_mirrors(root1.left, root2.right)\ | |
and CompleteBinaryTree.are_mirrors(root1.right, root2.left) | |
@staticmethod | |
def print_root_to_leaf(root, path=[]): | |
if root is None: | |
#print('->'.join([str(x) for x in path])) | |
return | |
path.append(root.key) | |
if root.left is None and root.right is None: | |
print('->'.join([str(x) for x in path])) | |
else: | |
CompleteBinaryTree.print_root_to_leaf(root.left, copy.copy(path)) | |
CompleteBinaryTree.print_root_to_leaf(root.right, copy.copy(path)) | |
if __name__ == '__main__': | |
complete_binary_tree = CompleteBinaryTree() | |
complete_binary_tree.insert(1) | |
complete_binary_tree.insert(2) | |
complete_binary_tree.insert(3) | |
complete_binary_tree.insert(4) | |
complete_binary_tree.insert(5) | |
complete_binary_tree.insert(6) | |
complete_binary_tree.insert(7) | |
complete_binary_tree.insert(8) | |
print('_____Level Order Traversal____') | |
complete_binary_tree.level_order_traversal([complete_binary_tree.get_root()]) | |
complete_binary_tree.print('INORDER') | |
print('\nMax Depth >> ', end='') | |
print(complete_binary_tree.max_depth(complete_binary_tree.root)) | |
print('Print All leaf Node >>') | |
complete_binary_tree.print_all_leaf_node(complete_binary_tree.root) | |
print('\n\nSearch a Node 5 :', complete_binary_tree.search(complete_binary_tree.get_root(), 5)) | |
print('\n\nSearch a Node 9 :', complete_binary_tree.search(complete_binary_tree.get_root(), 9)) | |
print('____Delete Node __________') | |
complete_binary_tree.delete(8) | |
print('_____Level Order Traversal____') | |
complete_binary_tree.level_order_traversal([complete_binary_tree.get_root()]) | |
print('________Create mirror image_______') | |
complete_binary_tree.create_mirror_image(complete_binary_tree.root) | |
print('_____Level Order Traversal____') | |
complete_binary_tree.level_order_traversal([complete_binary_tree.get_root()]) | |
#bt = CompleteBinaryTree() | |
#bt.insert(1) | |
#bt.insert(2) | |
#bt.insert(3) | |
#bt.insert(4) | |
#bt.insert(5) | |
#bt.insert(6) | |
#bt.insert(7) | |
#bt.insert(8) | |
#print('_____Level Order Traversal tree_2 ____') | |
#bt.level_order_traversal([bt.get_root()]) | |
#print('__Check is tree1 and tree2 are mirror image__ :', end='') | |
#print(CompleteBinaryTree.are_mirrors(complete_binary_tree.root, bt.root)) | |
print('__Print all the path from root to leaf__') | |
CompleteBinaryTree.print_root_to_leaf(complete_binary_tree.get_root(), []) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment