Showing posts with label Traversal. Show all posts
Showing posts with label Traversal. Show all posts

Saturday, 9 August 2014

Insertion, deletion and reversal of link list

This is a program to implement the various functions of a link list. If you have any doubts please let me know.
#include<stdio.h>
#include<stdlib.h>
struct node
{
 int data;
 struct node *next;
};
struct node *newn,*start=NULL,*ptr=NULL,*prev=NULL,*rev,*temp=NULL;
void insbeg();
void insend();
void inspos();
void insaft();
void delbeg();
void delend();
void delelement();
void display();
main()
{
 int ch1,ch,ch2;
 do
 {
  printf("\nMenu:\n1.Insertion\n2.Deletion\n3.Reversal\n4.Display\n5.Exit\n");
  printf("Enter your choice:");
  scanf("%d",&ch);
  switch(ch)
  {
   case 1:
    do
    {
     printf("\nSubmenu\n1.Insertion at beginning\n2.Insetion at End\n3.Insert at a specified position\n4.Insert after a specified node\n5.Exit from menu\n");

     printf("Enter your choice:");
     scanf("%d",&ch1);
     switch(ch1)
     {
      case 1:insbeg();
             break;
      case 2:
             insend();
             break;
      case 3:
             inspos();
             break;
      case 4:
             insaft();
             break;
      case 5:
             break;
      default:printf("Wrong choice\n");
              break;
     }
    }while(ch1!=5);
    break;
   case 2:
    do
    {
     printf("\nSubmenu\n1.Deletion at beginning\n2.Deletion at end\n3.Deletion of specific node\n4.Exit from this menu\n");
     printf("Enter your choice:");
     scanf("%d",&ch2);

     switch(ch2)
     {
      case 1:delbeg();
             break;
      case 2:delend();
             break;
      case 3:delelement();
             break;
      case 4:
             break;
      default:printf("Wrong choice\n");
              break;
     }
    }while(ch2!=4);
    break;
  case 3:
    if(start==NULL)
    {
     printf("\nUnderflow\n");
    }
    else
    {
     ptr=start;
     prev=NULL;
     while(ptr->next!=NULL)
     {
      rev=prev;
      prev=ptr;
      ptr=ptr->next;
      prev->next=rev;
     }
     start=prev;
     display();
   }
   break;
  case 4:
     display();
    break;
  case 5:
         break;
  default:printf("\nWrong Choice\n");
          break;
   }
  }while(ch!=5);
}

void insbeg()
{
 int num;
 printf("Enter the element:");
 scanf("%d",&num);
 newn=(struct node *)malloc(sizeof(struct node));
 if(start==NULL)
 {
  newn->data=num;
  newn->next=NULL;
  start=newn;
 }
 else
 {
  newn->data=num;
  newn->next=start;
  start=newn;
 }
}

void insend()
{
 int num;
 printf("Enter the element:");
 scanf("%d",&num);
 newn=(struct node *)malloc(sizeof(struct node));
  if(start==NULL)
 {
  newn->data=num;
  newn->next=NULL;
  start=newn;
 }
 else
 {
  ptr=start;
  while((ptr->next)!=NULL)
    ptr=ptr->next;
  newn->data=num;
  ptr->next=newn;
  newn->next=NULL;
 }
}

void inspos()
{
 int num,k=0,n;
 ptr=start;
 printf("Enter the the position at which the element must be inserted:");
 scanf("%d",&n);
 if(n==1)
 {
  insbeg();
 }
 else
 {
   printf("Enter the element:");
   scanf("%d",&num);
   while(k!=(n-1))
  {
    prev=ptr;
    ptr=ptr->next;
    k++;
   }
  newn=(struct node *)malloc(sizeof(struct node));
  newn->data=num;
  newn->next=ptr;
  prev->next=newn;
 }
}

void insaft()
{
 int n,num,c=0;
 ptr=start;
 printf("Enter the element:");
 scanf("%d",&num);
 printf("Enter the element after which insertion must be done:");
 scanf("%d",&n);
 while(ptr!=NULL)
 {
         if(ptr->data!=n)
         {
        ptr=ptr->next;
         }
         else
         {
                 c++;
                 {

                        newn=(struct node *)malloc(sizeof(struct node));
                        newn->data=num;
                        newn->next=ptr->next;
                        ptr->next=newn;
                        ptr=ptr->next;
                        break;
                }
         }
 }
 if(c==0)
         printf("NODE NOT FOUND");

}



void delbeg()
{
        if(start==NULL)
        {
                printf("\nUnderflow\n");
        }
        else
        {
                ptr=start;
                start=start->next;
                free(ptr);
        }
}

void delend()
{
        if(start==NULL)
        {
                printf("\nUnderflow\n");
        }
        else if(start->next==NULL)
          delbeg();
        else
        {
         ptr=start;
         while(ptr->next!=NULL)
        {
                prev=ptr;
                ptr=ptr->next;
        }
        prev->next=NULL;
        free(ptr);
        }
}
void delelement()
{
 int num,c=0;
 if(start==NULL)
 {
  printf("\nUnderflow\n");
 }
 else
 {
 printf("Enter the element to be deleted:");
 scanf("%d",&num);
 ptr=start;
 while(ptr!=NULL)
 {
        if(start->data==num)
        {
                 c++;
                delbeg();
                ptr=start;
                break;

        }
        else if(ptr->data==num)
        {
                c++;
          temp=ptr;
          prev->next=temp->next;
          ptr=ptr->next;
          free(temp);
          break;

        }

                prev=ptr;
                ptr=ptr->next;

 }

if(c==0)
 {
         printf("NODE NOT FOUND");
 }
}
}
 void display()
{
   if(start==NULL)
    {
     printf("\nUnderflow\n");
    }
    else
        {
    ptr=start;
    while(ptr->next!=NULL)
    {
     printf("=>%d  ",ptr->data);
     ptr=ptr->next;
    }
    printf("=>%d  ",ptr->data);
    }
}




The various functions on BST

Now this length program is the Insertion, Deletion , Traversal, etc of the Binary Search Tree. If you have doubts, please let me know.
#include<stdio.h>
#include<stdlib.h>
#define max(A,B) (((A)>(B))?(A):(B))
struct node
{
        int data;
        struct node *rc,*lc;
}*newn,*ptr=NULL,*pre=NULL,*root=NULL,*succ=NULL;
void ins(int);
void del(int);
void inorder(struct node *temp);
void preorder(struct node *temp);
void postorder(struct node *temp);
void display(struct node*);
int height(struct node*);

main()
{
        int ch,r,x,h,l,d;
        do
        {
        printf("\nMenu:\n1.Isertion\n2.Deletion\n3.Traversal\n4.Level\n5.Height\n6.Display\n7.Exit\n");
        printf("\nEnter your choice:");
        scanf("%d",&ch);
        switch(ch)
        {
        case 1:
                printf("Enter the element to be inserted:");
                scanf("%d",&d);
                scanf("%d",&d);
                ins(d);
                break;
        case 2:
                printf("Enter the element to be deleted:");
                scanf("%d",&x);
                del(x);
                break;
        case 3: display(root);
                break;
        case 4:
                h=height(root);
                l=h-1;
                printf("\nLEVEL:%d",l);
                break;
        case 5:h=height(root);
                printf("\nHEIGHT:%d",h);
                break;
        case 6:
                display(root);
                break;
        case 7:break;
        default:
                printf("\nWrong choice\n");
                break;
        }
        }while(ch!=7);
}
void ins(int d)
{
        int flag=0;
         ptr=root;
         newn=(struct node*)malloc(sizeof(struct node));
        newn->data=d;
        newn->lc=NULL;
        newn->rc=NULL;
        while((ptr!=NULL)&&(flag==0))
        {
                if(d<ptr->data)
                {
                        pre=ptr;
                        ptr=ptr->lc;
                }
                else if(d>ptr->data)
                {
                        pre=ptr;
                        ptr=ptr->rc;
                }
                else
                {
                        flag=1;
                        printf("Element already exists!");
                }
        }
        if(ptr==NULL)
        {
           if(root==NULL)
           {
            root=newn;
            ptr=root;
           }
           else if(pre->data<d)
           {
             pre->rc=newn;
             ptr=pre->rc;
           }
           else if(pre->data>d)
           {
             pre->lc=newn;
             ptr=pre->lc;
           }
        }

}

void del(int x)
{
        ptr=root;
        while(ptr!=NULL)
        {
                if(x<ptr->data)
                {
                        pre=ptr;
                        ptr=ptr->lc;
                }
                else if(x>ptr->data)
                {
                        pre=ptr;
                        ptr=ptr->rc;
                }
                else if(ptr->data==x)
                {
                        if((ptr->lc==NULL)&&(ptr->rc==NULL))
                        {
                                if(root==ptr)
                                {
                                 free(root);
                                 root=NULL;
                                 break;
                                }
                                else if(pre->lc==ptr)
                                        pre->lc=NULL;
                                else if(pre->rc==ptr)
                                        pre->rc=NULL;
                                free(ptr);
                            break;

                        }

                        else if(ptr->lc!=NULL&&ptr->rc==NULL)
                        {
                        if(pre->lc==ptr)
                                pre->lc=ptr->lc;
                        else if(pre->rc==ptr)
                                pre->rc=ptr->lc;
                        free(ptr);
                        break;
                        }
                        else if(ptr->lc==NULL&&ptr->rc!=NULL)
                        {
                        if(pre->lc==ptr)
                                pre->lc=ptr->rc;
                        else if(pre->rc==ptr)
                                pre->rc=ptr->rc;
                        free(ptr);
                        break;
                        }
                        else if(ptr->lc!=NULL&&ptr->rc!=NULL)
                        {
                        succ=ptr->rc;
                        if(succ->lc==NULL)
                        {
                                if(ptr==root)
                                {
                                   succ->lc=root->lc;
                                  root=succ;
                                }
                                else if(pre->lc==ptr)
                                {
                                        pre->lc=succ;
                                        succ->lc=ptr->lc;
                                }
                                else if(pre->rc==ptr)
                                {
                                        pre->rc=succ;
                                        succ->rc=ptr->rc;
                                }
                                free(ptr);
                                break;
                        }
                        else
                        {
                                while(succ->lc!=NULL)
                                {
                                        pre=succ;
                                        succ=succ->lc;
                                }
                                ptr->data=succ->data;
                                pre->lc=succ->rc;
                                free(ptr);
                                break;
                                }
                        }
                }
        }
        if(ptr==NULL)
                {
                        printf("\nElement absent\n");
                }
}
void postorder(struct node *temp)
{
        if(temp!=NULL)
        {
                postorder(temp->lc);
                postorder(temp->rc);
                printf("  %d",temp->data);
        }
  }
 void preorder(struct node *temp)
{

        if(temp!=NULL)
        {
                printf("  %d",temp->data);
                preorder(temp->lc);
        preorder(temp->rc);
        }
}

void display(struct node *root1)
{
int i;
if(root1==NULL)
        printf("Empty tree!");
else
{
printf("\nEnter the order\n1:inorder\n2:preorder\n3:postorder\n");
         printf("\nEnter your choice:");
         scanf("%d",&i);
         if(i==1)
         {
                 printf("\nINORDER:\n");
         inorder(root1);

          }
         else if(i==2)
         {
         printf("\nPREORDER:\n");
         preorder(root1);
         }
         else
         {
                 printf("\nPOSTORDER:\n");
                 postorder(root1);
         }
}
}
 void inorder(struct node *temp)
{
        if(temp!=NULL)
        {
        inorder(temp->lc);
                printf("  %d",temp->data);
                inorder(temp->rc);
        }
}

int height(struct node *root)
{
        if(root==NULL)
                return 0;
        else
             return max(height(root->lc),height(root->rc));
}