rtbtlib.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->left=NULL;
	if(*root==NULL)
	{
		*root=temp;
		temp->right=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)
		 {
			par->left=temp;
			temp->right=par;
			temp->thread='1';
		 }
		 else
		 {
			if(par->thread=='1')
			{
				par->thread='0';
				temp->thread='1';
				temp->right=par->right;
				par->right=temp;
			 }
			 else
			 {
			   if(par->thread=='1')
			   {
				temp->thread='\0';
				temp->thread='1';
				temp->right=par->right;
				par->right=temp;
			    }
			    else
			    {
				par->thread='0';
				temp->right=NULL;
				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->right;
      }
    }
  }
  while(temp!=NULL);
  printf("\n");
}

int large(node *root)
{
  if(root->right==NULL)
    return(root->info);
  else
    return(large(root->right));
}

int small(node *root)
{
  if(root->left==NULL)
    return(root->info);
  else
    return(small(root->left));
}