Thursday, 21 September 2017

Data Structure: Binary Search Tree implementation with in-order traversing

Data Structure: Binary Search Tree implementation with in-order traversing

A binary search tree is a binary tree where each node has a Comparable data and satisfies the restriction that the data in any node is larger than the data's in all nodes in that node's left subtree and smaller than the data's in all nodes in that node's right subtree.

Basic Operations performed on Binary Search Trees:

1. Search − Searches an element in a Binary Search Trees.

2. Insert − Inserts an element in a Binary Search Trees.

3. Pre-order Traversal − Traverses a tree in a pre-order manner form the Binary Search Trees.

4. In-order Traversal − Traverses a tree in an in-order manner from the Binary Search Trees.

5. Post-order Traversal − Traverses a tree in a post-order manner from the Binary Search Trees.


Implementation of the Binary Search Tree in C++ language:
Node Structure of a Binary Search Tree: we define a node structure having some info part, the pointer to its left child and right child nodes. We simply create this node with the help of structure.

struct node
    {
        int info;
         node *left;
         node *right;
    };



 

Insert Operation in Binary Search tree: Whenever an element is to be inserted, first locate its proper location. Start searching from the root node, then if the data is less than the key value, search for the empty location in the left subtree and insert the data. Otherwise, search for the empty location in the right subtree and insert the data.

node * createBST( node *r, int val)
{
    if(r==NULL)
    {
        r=new node;
        r->info=val;
        r->left=NULL;
        r->right=NULL;
    }
    else if(val<=r->info)
    {
        r->left=createBST(r->left,val);
       
    }
    else 
    {
        r->right=createBST(r->right,val);
    }
    return r;
}

In-order Traversing function of Binary Search Tree: In this function, we write a code to traverse the node of the Binary search tree in the In-order way. The rules for In-order traversing is First we write left-child -> root-node -> right-child.

 
void inOrder( node *r)
{
if(r!=NULL)
  {
    total++; 
    if(r->left==NULL && r->right==NULL)
    ext++;
    inOrder(r->left);
    cout<<r->info<<" ";
    inOrder(r->right);
  }
}

Main function of implemention Binary search Tree:

     int main()
    {
       node *r=NULL;
        int n,val;
        cin>>n;
        for(int i=0;i<n;i++)
        {
            cin>>val;
            r=createBST(r,val);
        }
        cout<<"Inorder"<<endl;
        inOrder(r);
        cout<<endl;
    cout<<"total nodes="<<total<<endl<<"external nodes:"<<ext<<endl<<"internal nodes:"<<total-ext<<endl;
      
    }



Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput