Sunday 23 December 2012

implement binary tree

// implement binary  tree

#include<stdio.h>
#include<conio.h>
#define N 10
#include<stdlib.h>
#include<process.h>
struct node
{
  struct node* lp;
  struct node* rp;
  int info;
};
struct stack
{
  int top;
  int st[N];
};
void main()
{
  int x,ch;
  char c;
  struct node* insert(struct node*,int);
  struct node* delet(struct node*,int);
  void retrieve(struct node*);
   void inorder(struct node*);

  struct node *root,*cur;
  root= '\0';
  clrscr();
  do
  {
    printf("\n1.insert\n 2.retrieve\n 3.delete\n 4.exit\n");
    printf("\nenter your choice\n");
    scanf("%d",&ch);
    switch(ch)
    {
      case 1:  printf("enter data\n");
           scanf("%d",&x);
           root=insert(root,x);
           break;

      case 2:  //retrieve(root);
          inorder(root);
           break;

      case 3:  printf("enter data u want to delete:\n");
           scanf("%d",&x);
           root=delet(root,x);
          // free(cur);
           break;

      case 4: exit(0);
    }
    printf("\ndo u want to continue(y/n)?");
    c=getche();
  }while(c=='y'||c=='Y');
  getch();
}

struct node* insert(struct node*root,int x)
{
  struct node* makenode(int);
  struct node *p,*q;
  if(root=='\0')
  {
    root=makenode(x);
    return(root);
  }
  p=q=root;
  while(q!='\0' && x!=p->info)
  {
    p=q;
    if(x<p->info)
     q=p->lp;
    else
     q=p->rp;
   }
   if(x==p->info)
     printf("duplication not allowed\n");
   else if(x<p->info)
   {
     p->lp=makenode(x);
   }
   else
   {
     p->rp=makenode(x);
    }
   return(root);
}

struct node* makenode(int x)
{
  struct node* nev;
  nev=(struct node*)malloc(sizeof(struct node));
  nev->info=x;
  nev->lp=nev->rp='\0';
  return(nev);
}


/* RETRIEVING IN POST-ORDER USING STACK. */
void retrieve(struct node *root)
{
   struct node *p,*x;
   int y;
   struct stack s;
   void push(struct stack *,int);
   int pop(struct stack *);
   if(root==NULL)
   {
     printf("Empty Tree");
   }
   else
   {
   p=root;
   s.top=-1;
   while(p!='\0' || s.top>-1)
     {
      while(p!=NULL)
      {
     push(&s,p->info);
     p=p->lp;
      }
      if(s.top>-1)
      {
     p=pop(&s);
     printf("/ \n");
     printf("%10d",p->info);
     p=p->rp;
      }
    }
  return;

}
void inorder(struct node *root)
{
   if(root==NULL)
     printf("Empty Tree");
   else
   {
     if(root->lp!=NULL)
    inorder(root->lp);
     printf("%d\n",root->info);
     if(root->rp!=NULL)
    inorder(root->rp);
   }
}

void push(struct stack *s1,int no)
{
 if(s1->top==N-1)
  {
   printf("Stack overflow\n");
   return;
  }
 else
  {
   s1->top++;
   s1->st[s1->top]=no;
   return;
  }
}

int pop(struct stack *s1)
{
  if(s1->top==-1)
   {
    printf("stack is empty\n");
    return(-1);
   }
  else
   {
    return(s1->st[s1->top--]);
   }
}

struct node* delet(struct node *root,int x)
{
   struct node *cur,*par,*suc,*pred,*q;
   char d;
   int found=0;
   if(root=='\0')
   {
     printf("empty tree\n");
     return(root);
   }
   else
   {
    cur=root;
    found=0;
    par=NULL;
   while(!found && cur!='\0')
   {
     if(cur->info==x)
     {
       found=1;
     }
     else if(x<cur->info)
     {
       par=cur;
       cur=par->lp;
       d='l';
     }
     else
     {
       par=cur;
       cur=par->rp;
       d='r';
     }
   }
   if(found==0)
   {
    printf("node not found\n");
    return(root);
   }
   else if(cur->lp=='\0')
     q=cur->rp;
   else if(cur->rp=='\0')
     q=cur->lp;
   else
   {
     suc=cur->rp;
     if(suc->lp=='\0')
     {
       q=suc;
       q->lp=cur->lp;
     }
     else
     {
       pred=cur->rp;
       suc=pred->lp;
       while(suc->lp!='\0')
       {
     pred=suc;
     suc=pred->lp;
       }
       pred->lp=suc->rp;
       suc->lp=cur->lp;
       suc->rp=cur->rp;
       q=suc;
       }
     }
   }
     if(par==NULL)
     {
    root=q;
    return(root);
     }
     if(d=='l')
      par->lp=q;
     else
      par->rp=q;
     printf("deleted data is=%d",cur->info);
     free(cur);
     return(root);
}



Digg Google Bookmarks reddit Mixx StumbleUpon Technorati Yahoo! Buzz DesignFloat Delicious BlinkList Furl

0 comments : on " implement binary tree "

Post a Comment

Popular Posts