//	  InOrder Threaded Binary Tree
//		 Gaurang Sinha
//	    gaurang85@rediffmail.com
//   gaurang.cjb.net -or- gaurang85.tripod.com
#include<stdio.h>
#include<conio.h>
#include<malloc.h>

#define LSON 	0
#define RSON 	1
#define PRINTED 2
#define THREAD 	0
#define LINK 	1

typedef struct thread{
		int lflag,rflag,data,flag;
		struct thread *left,*right;
		}TREE;
TREE *p,*start,*header,*rldep;
int side,dep,depth[10];
void create();
void add(TREE *root);
void inorder(TREE *root),preorder(TREE *root),postorder(TREE *head);

int main()
{
int s;
A:
clrscr();
printf(	"\n\t\tMENU"
	"\n\t\t1. Add Element"
	"\n\t\t2. Display "
	"\n\t\t3. Exit"
	"\n\t\t::> ");
scanf("%d",&s);
if(s==3)return 0;
switch(s)
{
case 1:
	create();
	goto A;
case 2:
	printf("\n\n\t  InOrder : ");
	inorder(start);
	printf("\n\t PreOrder : ");
	preorder(start);
	printf("\n\tPostOrder : ");
	postorder(header);
	getch();
	goto A;
default:
	goto A;
}
}

void create()
{
if(header==NULL)
{
	header=malloc(sizeof(TREE));
	header->data=-999;
	header->left=header;
	header->right=header;
	header->lflag=1;
	header->rflag=0;
}
p=malloc(sizeof(TREE));
printf("\n\n\tEnter Element : ");
scanf("%d",&p->data);
p->lflag=0;
p->rflag=0;
p->left=NULL;
p->right=NULL;
if(start==NULL)
{
	start=p;
	header->left=start;
	start->left=header;
	start->right=header;
}
else
{
	if(p->data>start->data)
		side=1;
	else
		side=0;
	rldep=start;
	add(start);
}
}

void add(TREE *root)
{
if((root->lflag==LINK)&&(root->rflag==LINK))
	rldep=root;
if((p->data)<(root->data))
{
	if(root->lflag==THREAD)
	{
		root->left=p;
		if(side==0)
			p->left=header;
		else
			p->left=rldep;
		p->right=root;
		root->lflag=1;
	}
	else
		add(root->left);
}
else if((p->data)>(root->data))
{
	if(root->rflag==THREAD)
	{
		TREE *tmp;
		if(side==0)
			p->right=rldep;
		else
			p->right=header;
		p->left=root;
		root->right=p;
		root->rflag=1;
	}
	else
	{
		if(((root->right)->lflag==LINK)&&((root->right)->rflag==LINK))
			rldep=root->right;
		add(root->right);
	}
}
else if((p->data)==(root->data))
{
	printf("\n\n\tElement Already Exists !!! ");
	getch();
	free(p);
}
}

void inorder(TREE *root)
{
while(1)
{
	while(root->lflag!=THREAD)
		root=root->left;
	printf(" %d",root->data);
	if(root->rflag!=THREAD)
		root=root->right;
	else
	{
		while(root->rflag==THREAD)
		{
			if(root->right==header)
				return;
			root=root->right;
			printf(" %d",root->data);
		}
		if(root->rflag!=THREAD)
			root=root->right;
	}
}
}

void preorder(TREE *root)
{
while(1)
{
	printf(" %d",root->data);
	while(root->lflag!=THREAD)
	{
		root=root->left;
		printf(" %d",root->data);
	}
	if(root->rflag!=THREAD)
		root=root->right;
	else
	{
		while(root->rflag==THREAD)
		{
			if(root->right==header)
				return;
			root=root->right;
		}
		if(root->rflag!=THREAD)
			root=root->right;
	}
}
}

void postorder(TREE *head)	//Send Header Node To Function
{
 TREE *temp=head->left;		//Make Temp Equal To Start
 temp->flag=LSON;		//Put it as Left Son in the Flag
 while(temp!=head)
 {
	if(temp->lflag!=THREAD&&temp->left->flag!=PRINTED)
	{//If Left son exists and is not printed go to it
		temp=temp->left;
		temp->flag=LSON;
	}
	else if(temp->rflag==LINK&&temp->right->flag!=PRINTED)
	{//If right son exists and is not printed go to it
		temp=temp->right;
		temp->flag=RSON;
	}
	else
	{
		printf(" %d",temp->data);
		if(temp->flag==LSON)  //if leftson go  to rightmost thread
		{
			temp->flag=PRINTED;
			while(temp->rflag!=THREAD)
				temp=temp->right;
			temp=temp->right;
		}
		else                //if rightson go to leftmost thread
		{
			temp->flag=PRINTED;
			while(temp->lflag!=THREAD)
				temp=temp->left;
			temp=temp->left;
		}
	}
}
}