Binary Search Tree

#include <stdio.h>
#include<malloc.h>

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

node* insert(node *T,int x)
{
    node *p,*q,*r;
    r=(node*)malloc(sizeof(node));
    r->data=x;
    r->left=NULL;
    r->right=NULL;
    if(T==NULL)
        return r;
    p=T;
    while(p!=NULL)
    {
        q=p;
        if(x>p->data)
            p=p->right;
        else
            p=p->left;
    }
    if(x>q->data)
        q->right=r;
    else
        q->left=r;
    return T;
}

node* create()
{
    int n,x,i;
    node *root;
    root=NULL;
    printf("\nEnter no. of nodes ");
    scanf("%d",&n);
    printf("Enter data ");
    for(i=0;i<n;i++)
    {
        scanf("%d",&x);
        root=insert(root,x);
    }
    return root;
}

node* min(node *T)
{
    while(T->left!=NULL)
        T=T->left;
    return T;
}

node* delete(node *T,int x)
{
    node *temp;
    if(T==NULL)
    {
        printf("\nElement not found !!");
        return T;
    }
    if(x<T->data)
    {
        T->left=delete(T->left,x);
        return T;
    }
    if(x>T->data)
    {
        T->right=delete(T->right,x);
        return T;
    }
    if(T->left==NULL && T->right==NULL)
    {
        free(T);
        return NULL;
    }
    if(T->left==NULL)
    {
        temp=T;
        T=T->right;
        free(temp);
        return T;
    }
    if(T->right==NULL)
    {
        temp=T;
        T=T->left;
        free(temp);
        return T;
    }
    temp=min(T->right);
    T->data=temp->data;
    T->right=delete(T->right,temp->data);
    return T;
}

void preorder(node *T)
{
    if(T!=NULL)
    {
        printf("%d ",T->data);
        preorder(T->left);
        preorder(T->right);
    }
}

void inorder(node *T)
{
    if(T!=NULL)
    {
        inorder(T->left);
        printf("%d ",T->data);
        inorder(T->right);
    }
}

void postorder(node *T)
{
    if(T!=NULL)
    {
        postorder(T->left);
        postorder(T->right);
        printf("%d ",T->data);
    }
}

int main()
{
    node *root;
    int x,n;
    printf("Creating Tree\n");
    root=create();
    do
    {
        printf("\nEnter\n1.Insert\n2.Delete\n3.Preorder\n4.Inorder\n5.Postorder\n6.Exit\n");
        scanf("%d",&x);
        switch(x)
        {
            case 1:
                printf("Enter data to be inserted ");
                scanf("%d",&n);
                root=insert(root,n);
                break;
            case 2:
                printf("Enter data to be deleted ");
                scanf("%d",&n);
                root=delete(root,n);
                break;
            case 3:
                preorder(root);
                printf("\n");
                break;
	    case 4:
                inorder(root);
                printf("\n");
                break;
	    case 5:
                postorder(root);
                printf("\n");
                break;
        }
    }while(x!=6);
    return 0;
}

/*Output
Creating Tree

Enter no. of nodes 8
Enter data 7 2 9 0 5 6 8 1

Enter
1.Insert
2.Delete
3.Preorder
4.Inorder
5.Postorder
6.Exit
3
7 2 0 1 5 6 9 8

Enter
1.Insert
2.Delete
3.Preorder
4.Inorder
5.Postorder
6.Exit
1
Enter data to be inserted 3

Enter
1.Insert
2.Delete
3.Preorder
4.Inorder
5.Postorder
6.Exit
3
7 2 0 1 5 3 6 9 8

Enter
1.Insert
2.Delete
3.Preorder
4.Inorder
5.Postorder
6.Exit
2
Enter data to be deleted 9

Enter
1.Insert
2.Delete
3.Preorder
4.Inorder
5.Postorder
6.Exit
3
7 2 0 1 5 3 6 8

Enter
1.Insert
2.Delete
3.Preorder
4.Inorder
5.Postorder
6.Exit
6
*/

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s