C source code for implementation of Binary Search Tree

, by Engineer's Vision

/* 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);
}

0 comments: