//thbitre.h
#include<fstream>
#define MAX 100

using namespace std;


struct BTNode
{
	BTNode * lchild,* rchild;//左右孩子
	char  data;
	int  LTag,RTag;//LTag=1為線索，LTag=0為左子樹
};


class thbitre 
{
private:
	BTNode * root;
	void create(BTNode * & BT,char ch[]);
	void preOrder(BTNode * & BT);
	void inOrder(BTNode * & BT);
	void postOrder(BTNode * & BT);
	void preThreading(BTNode * & BT,BTNode * & pre);
	void inThreading(BTNode * & BT,BTNode * & pre);
	void postThreading(BTNode * & BT,BTNode * & pre);
public:
	thbitre(){BTNode * root=NULL;}
	void create_thbitre(char *filename);
	void preOrderthbitre();//先序遍歷
	void inOrderthbitre(); //中序遍歷
	void postOrderthbitre();//后序遍歷
	void preOrderThreading();//先序線索化二叉樹
	void preOrderTraverse_Thr();//先序遍歷先序線索二叉樹
	void inOrderThreading();//中序線索化二叉樹
	void postOrderThreading();//后序線索化二叉樹
	void inOrderTraverse_Thr();//中序遍歷中序線索二叉樹
	void insert_Pre_Thr(char x);
};


void thbitre::create_thbitre(char *filename)
{
	char a[MAX];
	int m=1,i=0;
	fstream infile(filename,ios::in);
	if(!infile)
	{
		cerr<<"error"<<endl;
		exit(1);
	}
	while(m)
	{
		infile>>a[i];
		cout<<a[i];
		if(a[i]=='#'||a[i]==-9999)
			m=0;
		else
			i++;
	}
	cout<<endl;
	create(root,a);
}

void thbitre::create(BTNode * & BT,char ch[])
{
	static int i=-1;
	i++;
	if(ch[i]=='.')
		BT=NULL;
	else
	{
		BT=new BTNode;
		BT->data=ch[i];
		BT->LTag=0;
		BT->RTag=0;
		create(BT->lchild,ch);
		create(BT->rchild,ch);
	}
	return;
}


void thbitre::inOrderthbitre()
{
	inOrder(root);
	cout<<endl;
}

void thbitre::inOrder(BTNode * & BT)
{
	if(BT!=NULL)
	{
		inOrder(BT->lchild);
		cout<<BT->data<<' ';
		inOrder(BT->rchild);
	}
}

void thbitre::postOrderthbitre()
{
	postOrder(root);
	cout<<endl;
}

void thbitre::postOrder(BTNode * & BT)
{
	if(BT!=NULL)
	{
		postOrder(BT->lchild);
		postOrder(BT->rchild);
		cout<<BT->data<<' ';
	}
}


void thbitre::preOrderThreading()
{
	BTNode * pre=NULL;//*pre指向當前結點前一結點
	preThreading(root,pre);
	pre->rchild=NULL;
}

void thbitre::preOrderthbitre()
{
	preOrder(root);
	cout<<endl;
}

void thbitre::preOrder(BTNode * & BT)
{
	if(BT!=NULL)
	{
		cout<<BT->data<<' ';
		preOrder(BT->lchild);
		preOrder(BT->rchild);
	}
}



void thbitre::preOrderTraverse_Thr()
{
	BTNode * current=root;
	while(current!=NULL)
	{
		cout<<current->data<<" ";
		if(current->LTag==0)
		{current=current->lchild;}
		else
		{current=current->rchild;}
	}
	cout<<endl;
}


void thbitre::inOrderThreading()
{
	BTNode * pre=NULL;//*pre指向當前結點前一結點
	inThreading(root,pre);
	pre->rchild=NULL;
}

void thbitre::inThreading(BTNode * &BT,BTNode *&pre)
{
	if(BT!=NULL)
	{
		if(BT->LTag==0)
			inThreading(BT->lchild,pre);
		if((pre!=NULL)&&(pre->RTag==1))
		{
			pre->rchild=BT;
		}
		if(BT->lchild==NULL)
		{
			BT->LTag=1;
			BT->lchild=pre;
		}
		if(BT->rchild==NULL)
			BT->RTag=1;
		pre=BT;
		if(BT->RTag==0)
			inThreading(BT->rchild,pre);
	}
}

void thbitre::preThreading(BTNode * &BT,BTNode *&pre)
{
	if(BT!=NULL)
	{
		if((pre!=NULL)&&(pre->RTag==1))
		{pre->rchild=BT;}
		if(BT->lchild==NULL)
		{
			BT->LTag=1;
			BT->lchild=pre;
		}
		if(BT->rchild==NULL)
			BT->RTag=1;
		pre=BT;
		if(BT->LTag==0)
			preThreading(BT->lchild,pre);
		if(BT->RTag==0)
			preThreading(BT->rchild,pre);
	}
}


void thbitre::inOrderTraverse_Thr()
{
	BTNode * current=root;
	bool Traversed;
	while(current!=NULL)
	{
		while(current->LTag==0)
			current=current->lchild;
		Traversed=true;
		while(current!=NULL&&Traversed)
		{
			cout<<current->data<<" ";
			current=current->rchild;
			if(current==NULL)
			   Traversed=false;
			else if(current->RTag==0)
		   { 
			   cout<<current->data<<" ";
			   Traversed=false;
			   current=current->rchild;
		   }
		}
	}
	cout<<endl;
}



void thbitre::postOrderThreading()
{
	BTNode * pre=NULL;//*pre指向當前結點前一結點
	postThreading(root,pre);
}

void thbitre::postThreading(BTNode * &BT,BTNode *&pre)
{
	if(BT!=NULL)
	{
		if(BT->LTag==0)
			postThreading(BT->lchild,pre);
		if(BT->RTag==0)
			postThreading(BT->rchild,pre);
		if((pre!=NULL)&&(pre->RTag==1))
		{pre->rchild=BT;}
		if(BT->lchild==NULL)
		{
			BT->LTag=1;
			BT->lchild=pre;
		}
		if(BT->rchild==NULL)
			BT->RTag=1;
		pre=BT;
	}
}


void thbitre::insert_Pre_Thr(char x)
{
	BTNode * ptr=new BTNode;
	ptr->data=x;
	ptr->LTag=1;
	ptr->RTag=1;
	BTNode * current=root->lchild;
	if(root==NULL)
	{
		cerr<<"error"<<endl;
		return;
	}
	else
	{
		while(current->rchild!=root->rchild&&current->rchild!=NULL)
		{
			if(current->LTag==0)
				current=current->lchild;
			else
				current=current->rchild;
		}
		ptr->lchild=current;
		ptr->rchild=current->rchild;
		current->rchild=ptr;
		current->RTag=0;
	}
}