Friday, 22 September 2017

Implementation of Binary Search tree in C++ language

In this article, I discussed the creation of Binary Search tree, inserting new data element into the binary search tree, traversing the Binary search tree in pre-order, in-order and post-order, search a data element in it.
Binary search tree is a Binary tree with more conditions given below:
1. All the data elements which are smaller or equal to root element always put in the left-subtree. 
2.  All the data elements which are greater than root element always put in the right-sub-tree. 

Below is the implementation of Binary Search tree with some operations on it like inserting new data element in BST, Different traversing techniques like pre-order, in-order and post-order, search a data element.
We divide the whole code into different parts according to their functionality.
In this section, only header file required, different function and variables used are declared.
Here, CreateBST() is declared to create/insert a new node into BST, Inorder(), preorder() and postorder() are used to traverse BST respectively, search() is used to search a data element into BST. 
#include<iostream>
  using namespace std;
  struct node *createBST( node *root,int val);
  void inorder( node *root);
   void preorder( node *root);
   void postorder( node *root);
   void search(node *root,int value);
   int ext=0,total=0;


In this section, only structure of the BST node is created with the structure of C++ language. In this node of BST, we have one info part where the data element is stored, *left pointer variable is used to store left child of the node, and *right variable is used to store right child of the node.
struct node
{
    int info;
    node *left;
    node *right;
};
    


In this section, the define the implementation of creating node/insert a new node with the data element. In this function, it should return the address of the root node to the main function always.

    struct node *createBST(struct node *root,int val)
    {
        if(root==NULL) 
        {
        root = new node;
        root->info=val;
        root->left=NULL;
        root->right=NULL;
        }
        else if(val<=root->info)
        {
            root->left=createBST(root->left,val);
         }
            else
            {
                root->right=createBST(root->right,val);
            }
                return root;
    }
    
 
In this section, the define the implementation of traversing BST in inorder traversal. In inorder left child is processed first- root node is processed after that - the right child is processed in the end. 

    void inorder(struct node *root)
     {
                    if(root!=NULL)
                    {
                        total++;
                        if(root->left==NULL && root->right==NULL)
                        ext++;
                        
                        inorder(root->left);
                        cout<<root->info<<" ";
                        inorder(root->right);
                    }
                }
    
In this section, the define the implementation of traversing BST in inorder traversal. In inorder traversal root node is processed first - left child is processed first - right child is processed in the end. 

        void preorder(struct node *root)
     {
                    if(root!=NULL)
                    {
                        cout<<root->info<<" ";
                        preorder(root->left);
                        preorder(root->right);
                    }
                }


In this section, the define the implementation of traversing BST in inorder traversal. In inorder left child is processed first - a right child is processed after that - root node is processed at the end

void postorder(struct node *root)
     {
                    if(root!=NULL)
                    {
                       
                        postorder(root->left);
                        postorder(root->right);
                         cout<<root->info<<" ";
                    }
                }


In this section, a data element is searched in the BST, If the data element is not present in the BST then a message "not found" is displayed and if found then search data element found will be displayed.
 
void search(node *root,int value)
    if(root==NULL)
    {
        cout<<"not found";
    }
    else if(root->info==value)
    {
        cout<<"found"<<value;
    }
    else if(value<=root->info)
    {
         search(root->left,value);
    }
    else
    {
       search(root->right,value);
    }
}


In this section, different function call is implemented like createBST(), inorder(), preorder(), postorder() and search().
    int main()
    {
        struct node *root=NULL;
        int n,val,i,key;
        cin>>n;
        for(i=0;i<n;i++)
        {
            cin>>val;
            root=createBST(root,val);
        }
            
         cout<<"\nInorder";
            inorder(root);
           cout<<"\ntotal nodes="<<total<<endl;
           cout<<"\nInternal nodes"<<total-ext<<endl;
           cout<<"\nExternal nodes"<<ext<<endl;
        
         cout<<"\npreorder";
            preorder(root);
           cout<<"\ntotal nodes="<<total<<endl;
           cout<<"\nInternal nodes"<<total-ext<<endl;
           cout<<"\nExternal nodes"<<ext<<endl;
        
         cout<<"\npostorder";
            postorder(root);
           cout<<"\ntotal nodes="<<total<<endl;
           cout<<"\nInternal nodes"<<total-ext<<endl;
           cout<<"\nExternal nodes"<<ext<<endl;
        
        cin>>key;
        search(root,key);
     }




Thanks
Mukesh Rajput, Shankar Aggarwal

No comments:

Post a Comment

Thanks
Mukesh Rajput