PROGRAM:
//Binary search tree operations
#include<stdio.h> //header section
#include<stdlib.h>
struct tree
{
int data; //creating the node
struct tree *left;
struct tree *right;
}*root,*ptr1,*ptr,*new;
struct tree* insert(struct tree *root, int x) //defining insert function
{
while(x!=0)
{
ptr=ptr1=root;
int flag=0;
while(ptr!=NULL&&flag==0)
{
if(ptr->data==x) //cheching whether element already exists
{
flag=1;
printf("\n The element already exists");
}
else if(ptr->data<x)
{
ptr1=ptr;
ptr=ptr->right; //inserting in right child position
}
else
{
ptr1=ptr;
ptr=ptr->left; //inserting in left child position
}
}
if(ptr==NULL)
{
new=((struct tree*)malloc(sizeof(struct tree))); //creating new node
new->data=x; //assigning the given number
new->right=new->left=NULL;
if(ptr1==NULL)
{
root=new; //assigning new node to root
}
else
{
if(ptr1->data>x) //checking the data
{
ptr1->left=new;
}
else
{
ptr1->right=new;
}
}
}
printf("\n Enter the value to be inserted: ");
scanf("%d",&x); //getting the value from user
}
return root;
}
void inorder(struct tree *ptr) //inorder traversal
{
if(ptr!=NULL)
{
inorder(ptr->left);
printf("%d",ptr->data);
inorder(ptr->right);
}
}
void search(struct tree *root,int x) //defining search function
{
ptr=root; //asigning ptr to root
int flag=0;
while(ptr!=NULL&&flag==0)
{
if(ptr->data==x) //checking the key value with parent
{
flag=1;
}
else if(ptr->data>x)
{
ptr=ptr->left; //moving to left child
}
else
{
ptr=ptr->right; //moving to right child
}
}
if(flag==1)
{
printf("\n The element is found at %u",ptr); //printing element's address
}
else
{
printf("\n The element is not found");
}
}
int main()
{
int x,y;
printf("\n Enter the value to be inserted: ");
scanf("%d",&x);
root=insert(NULL,x); //calling the insert function
inorder(root); //calling inorder function
printf("\n Enter the element to be searched:");
scanf("%d",&y);
search(root,y); //calling the search function
return 0;
}
OUTPUT:
Enter the value to be inserted: 4
Enter the value to be inserted: 5
Enter the value to be inserted: 6
Enter the value to be inserted: 7
Enter the value to be inserted: 8
Enter the value to be inserted: 9
Enter the value to be inserted: 1
Enter the value to be inserted: 2
Enter the value to be inserted: 3
Enter the value to be inserted: 4
The element already exists
Enter the value to be inserted: 0
123456789
Enter the element to be searched:3
The element is found at 151466120
No comments:
Post a Comment