tbst.c

right threaded binary tree

/*threaded binary tree*/
#include<stdio.h>
#include<conio.h>
#include<alloc.h>

typedef struct nodetype
{
  int info;
  char thread;
  struct nodetype *left,*right;
}node;

void create(node **root)
{
  *root=NULL;
}

void insert(node **root,int ele)
{
	node *temp,*curr,*par;
	temp=(node *) malloc(sizeof(node));
	temp->info=ele;
	temp->right=NULL;
	if(*root==NULL)
	{
		*root=temp;
		temp->left=NULL;
		temp->thread='0';
	}
	else
	{
		par=NULL;
		curr=*root;
		while(curr!=NULL)
		{
			par=curr;
			if(ele<curr->info)
			   curr = curr->left;
			else
			 {
			   if(curr->thread=='1')
			     curr=NULL;
			   else
			     curr = curr->right;
			 }
		 }
		 if(ele<par->info)
		 {
			temp->left=par->left;
			temp->thread='0';
			par->left=temp;
		 }
		 else
		 {
			if(par->thread=='1')
			{
				par->thread='0';
				temp->thread='1';
				temp->left=par;
				par->right=temp;
			 }
			 else
			    {
				temp->thread='1';
				temp->left=par;
				par->right=temp;
			    }
			  }
	      }
      }
}

void inorder(node *root)
{
  node *temp,*temp1;
  temp=root;
  do
  {
    temp1=NULL;
    while(temp!=NULL)
    {
      temp1=temp;
      temp=temp->left;
    }
    if(temp1!=NULL)
    {
      printf("%d\t",temp1->info);
      temp=temp1->right;
      while(temp1->thread=='1' && temp!=NULL)
      {
	printf("%d\t",temp->info);
	temp1=temp;
	temp=temp->left;
      }
    }
  }
  while(temp!=NULL);
  printf("\n");
}


void main()
{
   node *s;
   char ch;
   int n,ele;
   clrscr();
   do
   {
     printf(" 1->insertion \n 2->inorder \n 3-> exit\n");
     scanf("%d",&n);
     switch(n)
     {
       case 1:  create(&s);
		do
		{
		  printf("element : ");
		  scanf("%d",&ele);
		  insert(&s,ele);
		  printf("again : ");
		  fflush(stdin);
		  scanf("%c",&ch);
		  }
		  while(ch=='y');
		 break;
       case 2: printf("the inorder traversing is \n");
	       inorder(s);
	       break;
       case 3: exit();
	       break;

	   }
	   }while(n!=3);
	   getch();
}