C Program to construct a Binary Search Tree (BST)...

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node* left,* right;
};

// Basic Functions...
struct node* insert(struct node* troot,int x);
struct node* deletenode(struct node* troot,int x);
struct node* findmin(struct node* troot);
int search(struct node* troot,int x);

// Basic display..
void predisplay(struct node* troot);
void indisplay(struct node* troot);
void postdisplay(struct node* troot);

void main()
{
    struct node* root=NULL;
    int n,a,i,val;
    int breakcondition=0;
    printf("\nChoice: \n1) Insert a node.. \n2) Delete a node.. \n3) Search for a node.. \n4) Display as Per Pre-order traversal.. \n5) Display as Per In-order traversal.. \n6) Display as Per Post-order traversal.. \n7)Stop ");
    int ch;
    while(1){
        printf("\nEnter your choice..");
        scanf("%d",&ch);
        switch(ch){
            case 1:{
                    printf("\nEnter any element to be inserted..");
                    scanf("%d",&val);
                    root=insert(root,val);
                    break;
                   }
            case 2:{
                    printf("\nEnter the element to be deleted..");
                    scanf("%d",&val);
                    root=deletenode(root,val);
                    break;
                   }
            case 3:{
                    printf("\nEnter the element to be searched..");
                    scanf("%d",&val);
                    if(search(root,val)){
                        printf("\nThe element is found..");
                    }
                    else{
                        printf("\nThe element is not found..");
                    }
                    break;
                   }
            case 4:{
                    if(root==NULL){
                        printf("\nThe list is empty..");
                        break;
                    }
                    printf("\nThe tree displayed as per pre order traversal is..");
                    predisplay(root);
                    break;
                   }
            case 5:{
                    if(root==NULL){
                        printf("\nThe list is empty..");
                        break;
                    }
                    printf("\nThe tree displayed as per in order traversal is..");
                    indisplay(root);
                    break;
                   }
            case 6:{
                    if(root==NULL){
                        printf("\nThe list is empty..");
                        break;
                    }
                    printf("\nThe tree displayed as per post order traversal is..");
                    postdisplay(root);
                    break;
                   }
            case 7:{
                    breakcondition=1;
                    break;
                   }
        }
        if(breakcondition==1){
            break;
        }
    }
}
struct node* insert(struct node* troot,int x)
{
   if(troot==NULL){
    struct node* temp=(struct node*)malloc(sizeof(struct node));
    temp->data=x;
    temp->left=temp->right=NULL;
    troot=temp;
   }
   else if(x<troot->data){
    troot->left=insert(troot->left,x);
   }
   else if(x>troot->data){
    troot->right=insert(troot->right,x);
   }
   else{
    printf("\nThe element is already present..");
   }
    return troot;
}

struct node* deletenode(struct node* troot,int x)
{
    if(troot==NULL){
        return troot;
    }
    else if(x<troot->data){
        troot->left=deletenode(troot->left,x);
    }
    else if(x>troot->data){
        troot->right=deletenode(troot->right,x);
    }
    else{
        if(troot->right==NULL && troot->left==NULL){
            free(troot);
            troot=NULL;
        }
        else if(troot->left==NULL){
            struct node* temp=troot;
            troot=troot->right;
            free(temp);
        }
        else if(troot->right==NULL){
            struct node* temp=troot;
            troot=troot->left;
            free(temp);
            return troot;
        }
        else{
            struct node* temp=findmin(troot->right);
            troot->data=temp->data;
            troot->right=deletenode(troot->right,temp->data);
        }
        return troot;
    }
}

struct node* findmin(struct node* troot)
{
    if(troot->left==NULL)
        return troot;
    else
        return findmin(troot->left);
}


int search(struct node* troot,int x)
{
    if(troot==NULL)return 0;
    else if (troot->data==x)return 1;
    else if(x<=troot->data)return search(troot->left,x);
    else return search(troot->right,x);
}

void predisplay(struct node* troot)
{
    if(troot==NULL)
        return;
    printf("%d ",troot->data);
    predisplay(troot->left);
    predisplay(troot->right);
}

void indisplay(struct node* troot)
{
    if(troot==NULL)
        return;
    indisplay(troot->left);
    printf("%d ",troot->data);
    indisplay(troot->right);
}

void postdisplay(struct node* troot)
{
    if(troot==NULL)
        return;
    postdisplay(troot->left);
    postdisplay(troot->right);
    printf("%d ",troot->data);
}

No comments:

Post a comment