#include
#include
#define false 0
#define true 1
using namespace std;
typedef struct BTnode{
 	int data;
 	struct BTnode *lchild,*rchild;
 	int ltag,rtag;
 }*BTree,BTnode;

#include
#include
#define false 0
#define true 1
using namespace std;
typedef struct BTnode{
 	int data;
 	struct BTnode *lchild,*rchild;
 	int ltag,rtag;
 }*BTree,BTnode;

int j=0;  //創建二叉樹的全局變量 
 //先序創建二叉樹
 int CreateBTree(BTree &T){
 	int str[]={1,2,3,NULL,4,NULL,NULL,NULL,5,6,NULL,7,NULL,NULL,8,NULL,NULL};
 	if(str[j]=='#') return false;
 	if(str[j]==NULL){
 		T=NULL;
 		j++;
	 }else{
	 	T=(BTnode *)malloc(sizeof(BTnode));
	 	T->data=str[j];
	 	j++;
	 	CreateBTree(T->lchild);
	 	CreateBTree(T->rchild);
	 }
 }  

inline bool visit(int e){   //此處使用內斂函數，提高運行效率 
 	printf("%d",e);
 	return true;
 }

//先序線索化.
 void prehread(BTree &root){
	if(root!=NULL){
		if(root->lchild==NULL){
			root->ltag=1;
			root->lchild=pre;
		}else{
			root->ltag=0;
		}
		if(pre){
			if(pre->rchild==NULL){
				pre->rtag=1;
				pre->rchild=root;
			}else{
				pre->rtag=0;
			}
		}
		pre=root;
		if(root->ltag==0){
		prehread(root->lchild);	
		}
		if(root->rtag==0){
			prehread(root->rchild);
		}
	}
} 

//尋找先序后繼 
BTree preNext(BTree T){
 	if(T->rtag==1){
		return T->rchild;
	 }else{
	 	if(T->ltag==0){
	 		return T->lchild;
		 }else{
		 	return T->rchild;
		 }
	 }
	 }
//先序線索二叉樹的遍歷
void prebianli(BTree T){
	BTree p;
	p=T;
	while(p){
		visit(p->data);
		p=preNext(p);
	}
} 

//中序線索化
BTree pre=NULL ;  //中序線索化的全局變量 
void Inthread(BTree &root){
	if(root!=NULL){
		Inthread(root->lchild);
		if(root->lchild==NULL){
			root->ltag=1;
			root->lchild=pre;
		}else{
			root->ltag=0;
		}
		if(pre){
			if(pre->rchild==NULL){
				pre->rtag=1;
				pre->rchild=root;
			}else{
				pre->rtag=0;
			}
		}
		pre=root;
		Inthread(root->rchild);
	}
}

//求中序首結點 
BTree InFirst(BTree T){
	BTree p=T;
	if(p==NULL) return NULL;
	while(p->ltag==0){
		p=p->lchild; 
	}
	return p;
} 
//求中序后繼
 BTree InNext(BTree T) {
 	BTree next=NULL;
 	if(T->rtag==1){
 		next=T->rchild;
	 }else {
		T = T->rchild;
		while (T->ltag==0 ) {
			T = T->lchild;
		}
		next=T;
	 }
	 return next;
 }
 //中序線索二叉樹的遍歷
void Inbianli(BTree T){
	BTree p;
	p=InFirst(T);
	while(p){
		visit(p->data);
		p=InNext(p);
	}
} 

//后續線索化
  void Postthread(BTree &root){
	BTree pre=NULL;
	if(root){
		Postthread(root->lchild);
		Postthread(root->rchild);
		if(root->lchild==NULL){
			root->ltag=1;
			root->lchild=pre;
		}
		if(pre&&pre->rchild==NULL){
			pre->rtag=1;
			pre->rchild=root;
		}
		pre=root;
		}
}

//求后序前驅 
BTree postnext(BTree T){
	if(T->ltag==0){
		if(T->rtag==0){
			return T->rchild;
		}else{
			return T->lchild;
		}
	}else {
		return T->lchild;
	}
}
//后序遍歷
void postbianli(BTree T){
	BTree p;
	p=T;
	while(p){
		p=postnext(p);
		visit(p->data);
	}
}