Saturday, 31 December 2011

Right Threaded Tree in C



#include<stdio.h>
#include<stdlib.h>

typedef struct node
{
 int data;
 int rthread;
 struct node *left,*right;
}NODE,*NODEPTR;

NODEPTR getnode()
{
 NODEPTR temp;
 temp=(NODEPTR)malloc(sizeof(NODE));
 temp->left=NULL;
 temp->rthread=1;
 return temp;
}

NODEPTR insucc(NODEPTR s)//to find the inorder successor
{
  NODEPTR  p=s->right;
  if(s->rthread==0)
   while(p->left!=NULL)
    p=p->left;
  return p;
}

void inorder(NODEPTR h)//function to traverse in in-order
{
  NODEPTR t=h;
  while(1)
  {
    t=insucc(t);
     if(t==h)
            return;
     printf("%d\n",t->data);
   }
}

NODEPTR create(NODEPTR head)
{
 NODEPTR y,t,q[100];
 int f=0,r=0,v;
 y=getnode();
 q[r++]=y;
 printf("Enter the root:");
 scanf("%d",&y->data);
 y->right=head;
 head->right=y;
 head->rthread=0;
 while(f!=r)
 {
  t=q[f++];
  printf("\nEnter the left child(%d) :",t->data);
  do
  {
   printf("Left child should be smaller\n");
   scanf("%d",&v);
   if(v==-1)break;
  }while(v>t->data);
  if(v!=-1)
  {
   y=getnode();
   q[r++]=y;
   t->left=y;
   y->right=t;
   y->data=v;
  }
  printf("Enter the right child(%d) :",t->data);
  do
  {
   printf("Right child should be  greater\n");
   scanf("%d",&v);
   if(v==-1)break;
  }while(v<t->data);
  if(v!=-1)
  {
    y=getnode();
    y->right=t->right;
    t->right=y;
    y->data=v;
    t->rthread=0;
    q[r++]=y;
  }
 }
 return head;
}

int main()
{
 NODEPTR head;
 head=getnode();
 head=create(head);
 printf("Inorder traversal : \n");
 inorder(head);
}



PS : A very long, inefficient code.. Try to understand at your own risk!

No comments:

Post a Comment