program showing various operations on binary search tree in C

Saturday, 1 March 2014


#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct BSTnode
{
int data;
struct BSTnode *left,*right;
}BSTnode;

BSTnode *find(BSTnode *,int);
BSTnode *insert(BSTnode *,int);
BSTnode *delet(BSTnode *,int);
BSTnode *create();
void inorder(BSTnode *T);
void preorder(BSTnode *T);
void postorder(BSTnode *T);
void main()
{
BSTnode *root=NULL,*p;
int x,op;
clrscr();
do
 { printf("\n\n1)Create\n2)Delete\n3)Search\n4)Preorder");
   printf("\n5)Inorder\n6)Posorder\n7)Insert\n8)Quit");
   printf("\nEnter Your Choice :");
   scanf("%d",&op);
    switch(op)
     {
case 1:root=create();break;
case 2: printf("\nEnter the key to be deleted :");
scanf("%d",&x);
root=delet(root,x);
break;
case 3: printf("\nEnter the key to be searched :");
scanf("%d",&x);
p=find(root,x);
if(p==NULL)
 printf("\n ***** Not Found****");
else
 printf("\n ***** Found*****");
break;
case 4: preorder(root);break;
case 5: inorder(root);break;
case 6: postorder(root);break;
case 7: printf("\nEnter a Data : ");
scanf("%d",&x);
root=insert(root,x);
break;
    }
}while(op!=8);
}


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

void preorder(BSTnode *T)
 {     if(T!=NULL)
 { printf("%d\t",T->data);
   preorder(T->left);
   preorder(T->right);
 }
 }
void postorder(BSTnode *T)
 {     if(T!=NULL)
 {
   postorder(T->left);
   postorder(T->right);
   printf("%d\t",T->data);
 }
 }
BSTnode *find(BSTnode *root,int x)
{
while(root!=NULL)
{
if(x==root->data)
return(root);
if(x>root->data)
root=root->right;
else
root=root->left;
}
return(NULL);
}

BSTnode *insert(BSTnode *T,int x)
{
BSTnode *p,*q,*r;
// acquire memory for the new node
r=(BSTnode*)malloc(sizeof(BSTnode));
r->data=x;
r->left=NULL;
r->right=NULL;
if(T==NULL)
return(r);
// find the leaf node for insertion
p=T;
while(p!=NULL)
{
q=p;
if(x==p->data)
 {
    printf("\nDuplicate Data : ");
    return(T);
 }
if(x>p->data)
p=p->right;
else
p=p->left;
}
if(x>q->data)
q->right=r;  // x as right child of q
else
q->left=r;   //x as left child of q
return(T);
}

BSTnode *delet(BSTnode *T,int x)
{
BSTnode *temp;
if(T==NULL)
{
printf("\nElement not found :");
return(T);
}
if(x < T->data)                // delete in left subtree
{
T->left=delet(T->left,x);
return(T);
}
if(x > T->data)                // delete in right subtree
{
T->right=delet(T->right,x);
return(T);
}

// element is found
if(T->left==NULL && T->right==NULL)   // a leaf node
{
temp=T;
free(temp);
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);
}
// node with two children
//go to the inorder successor of the node
temp=T->right;
while(temp->left !=NULL)
 temp=temp->left;
T->data=temp->data;
T->right=delet(T->right,temp->data);
return(T);
}

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



OUTPUT:-

1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :1

Enter no. of nodes :4

Enter tree values :12 34 87 56


1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :4
12      34      87      56

1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :5
12      34      56      87

1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :6
56      87      34      12

1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :7

Enter a Data : 33


1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :4
12      34      33      87      56

1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :3
Enter the key to be searched :33

 ***** Found*****

1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :8

No comments:

Post a Comment

Related Posts Plugin for WordPress, Blogger...
Related Posts Plugin for WordPress, Blogger...
 

Most Reading

Labels