C source code for implementation of Binary Search Tree
/* binary search tree */
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct bstnode
{
int data;
struct bstnode *left,*right;
}bstnode;
bstnode *init();
bstnode *search(bstnode*,int);
bstnode *insert(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("\n1.create\n2.search\n3.insert\n4.preorder\n5.inorder\n6.postorder\n7.exit");
printf("\nenter your choice");
scanf("%d",&op);
switch(op)
{
case 1:
root=create();
break;
case 2:
printf("\nenter the key to be searched");
scanf("%d",&x);
p=search(root,x);
if(p==NULL)
printf("\nkey not found");
else
printf("\nfound");
break;
case 3:
printf("\nenter the data to be inserted");
scanf("%d",&x);
root=insert(root,x);
break;
case 4:
preorder(root);
break;
case 5:
inorder(root);
break;
case 6:
postorder(root);
break;
}
}while(op!=7);
}
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 *search(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;
r=(bstnode*)malloc(sizeof(bstnode));
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
if(x<p->data)
p=p->left;
else
{
printf("\nduplicate entry");
return(t);
}
}
if(x>q->data)
q->right=r;
else
q->left=r;
return(t);
}
bstnode *create()
{
int n,x,i;
bstnode *root;
root=NULL;
printf("\nno of nodes");
scanf("%d",&n);
printf("\nenter the values");
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
return(root);
}
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
typedef struct bstnode
{
int data;
struct bstnode *left,*right;
}bstnode;
bstnode *init();
bstnode *search(bstnode*,int);
bstnode *insert(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("\n1.create\n2.search\n3.insert\n4.preorder\n5.inorder\n6.postorder\n7.exit");
printf("\nenter your choice");
scanf("%d",&op);
switch(op)
{
case 1:
root=create();
break;
case 2:
printf("\nenter the key to be searched");
scanf("%d",&x);
p=search(root,x);
if(p==NULL)
printf("\nkey not found");
else
printf("\nfound");
break;
case 3:
printf("\nenter the data to be inserted");
scanf("%d",&x);
root=insert(root,x);
break;
case 4:
preorder(root);
break;
case 5:
inorder(root);
break;
case 6:
postorder(root);
break;
}
}while(op!=7);
}
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 *search(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;
r=(bstnode*)malloc(sizeof(bstnode));
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
if(x<p->data)
p=p->left;
else
{
printf("\nduplicate entry");
return(t);
}
}
if(x>q->data)
q->right=r;
else
q->left=r;
return(t);
}
bstnode *create()
{
int n,x,i;
bstnode *root;
root=NULL;
printf("\nno of nodes");
scanf("%d",&n);
printf("\nenter the values");
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
return(root);
}
0 comments:
Post a Comment