Friday 10 February 2017

Common operations in Binary Search Tree


In This Post,I would like to explain the simple structure on how to 
create binary search tree using python classes.In binary search tree,
left child is always smaller than parent and right child is 
greater than parent.This property makes it easy for operations like 
addition,search,deletion of node.In Real world,you may have seen of phone 
directory in which we search by getting common string numbers.
 


class Node:

    #initialize node structure   
    def __init__(self,data):
      self.data = data
      self.left = None      
      self.right = None

   #get minimum node from tree starting from this node   
    def get_min_Node(self):
      current = self      
      while current.left is not None:
         current = current.left
      return current.data

    #get maximum node from tree starting from this node   
     def get_max_Node(self):
      current = self      
      while current.right is not None:
         current = current.right
      return current.data

#insert node in binary tree
def insert(self,data):
      current = self
      if current is None:
         current = Node(data)
      if current.left is None and current.data>data:
         current.left = Node(data)
      elif current.right is None and current.data < data:
         current.right = Node(data)
      elif current.data >data:
         insert(self.left,data)
      else:
         insert(self.right,data)
#delete node from binary tree
def delete_Node(self,data):

   #check for none type    
    if self is None:
        return self
    #if data is greater than node data
    elif data>self.data:
        self.right = delete_Node(self.right,data)
    #if data is less than node
    elif self.data>data:
        self.left = delete_Node(self.left,data)
    else:
        if self.left is None:
            tmp = self.right
            self = None            
            return tmp
        elif self.right is None:
            tmp = self.left
            self = None            
            return tmp
        #get minimal node from right subtree
        tmp = self.right.get_min_Node()
        #put data into self
        self.data  = tmp.data
        #delete the minimal subtree from right
        self.right = delete_Node(self.right,tmp.data)
    return self
#print inorder traversal of binary tree
def inorder(self):
   if self is None:
      return   
   inorder(self.left)
   print(self.data)
   inorder(self.right) 

#print preorder traversal of binary tree
def preorder(self):
   if self is None:
      return   
   print(self.data)
   inorder(self.left)
   inorder(self.right)

#print postorder traversal of binary tree
def postorder(self):
   #if node is null or None 
   if self is None:
      return   

   #if node is not none
   inorder(self.left)
   inorder(self.right)
   print(self.data)

#get height of tree
def height(self):
   if self is None:
      return 0   
   else:
      lheight = height(self.left)
      rheight = height(self.right)

      if lheight > rheight:
         return lheight + 1      
      else:
         return rheight + 1
#level order traversal of tree
def level_order(self):
   #get height of tree
   h = height(self)
   for i in range(1,h+1):
      print_level(self,i)

def print_level(self,level):

   if self is None:
      return   
   if level == 1:
      print(self.data)
   else:
      if level > 1:
         print_level(self.left,level-1)
         print_level(self.right,level-1)

a = Node(30)
insert(a,22)
insert(a,1)
insert(a,36)
#print preorder traversal of binary tree
preorder(a)
root = delete_Node(a,36)
#print tree
preorder(a)


No comments:

Post a Comment