#define  _CRT_SECURE_NO_WARNINGS  1
#include<iostream>
using namespace std;
typedef struct BiThrNode {
	char data;
	struct BiThrNode* lchild, * rchild;	//左右孩子指针
	int LTag, RTag;
}BiThrNode, * BiThrTree;
BiThrNode* pre = new BiThrNode;  // 全局变量pre
void CreateBiTree(BiThrTree& T) {
	//按先序次序输入二叉树中结点的值（一个字符），创建二叉链表表示的二叉树T
	char ch;
	cin >> ch;
	if (ch == '#')  T = NULL;			//递归结束，建空树
	else {
		T = new BiThrNode;
		T->data = ch;//生成根结点
		CreateBiTree(T->lchild);	//递归创建左子树
		CreateBiTree(T->rchild);	//递归创建右子树
	}
}
void InThreading(BiThrTree p) {
	//pre是全局变量，初始化时其右孩子指针为空，便于在树的最左点开始建线索
	if (p) {
		InThreading(p->lchild);             			//左子树递归线索化
		if (!p->lchild) {    //p的左孩子为空
			p->LTag = 1;   	//给p加上左线索
			p->lchild = pre; 			//p的左孩子指针指向pre（前驱）
		}
		else
			p->LTag = 0;
		if (!pre->rchild) {		//pre的右孩子为空
			pre->RTag = 1;    		//给pre加上右线索
			pre->rchild = p;      	//pre的右孩子指针指向p（后继）
		}
		else
			pre->RTag = 0;
		pre = p;        			//保持pre指向p的前驱
		InThreading(p->rchild);	//右子树递归线索化
	}
}
void InOrderThreading(BiThrTree& Thrt, BiThrTree T) {
	Thrt = new BiThrNode;           
	Thrt->LTag = 0;  		   		 
	Thrt->RTag = 1;				
	Thrt->rchild = Thrt;            	
	if (!T)  Thrt->lchild = Thrt;      
	else {
		Thrt->lchild = T;  pre = Thrt;   
		InThreading(T);             
		pre->rchild = Thrt;          
		pre->RTag = 1;
		Thrt->rchild = pre;       
	}
}
void InOrderTraverse_Thr(BiThrTree T) {
	
	BiThrTree p;
	p = T->lchild;             
	while (p != T) {			  
		while (p->LTag == 0)	  
			p = p->lchild;	 
		cout << p->data;
		while (p->RTag == 1 && p->rchild != T) {
			p = p->rchild;	
			cout << p->data;
		}
		p = p->rchild;
	}
}
void PreOrderTraverse_Thr(BiThrTree T) {
	BiThrTree p;
	p = T->lchild;              
	while (p != T) {
		cout << p->data;
		while (p->LTag == 0)	 
			p = p->lchild;	 
		while (p->RTag == 1 && p->rchild != T) {
			p = p->rchild;	
			cout << p->data;
		}
		p = p->rchild;
	}
}
void AfterOrderTraverse_Thr(BiThrTree T) {
	BiThrTree p;
	p = T->lchild;              
	while (p != T) {			  
		while (p->LTag == 0)	  
			p = p->lchild;	 
		while (p->RTag == 1 && p->rchild != T) {
			p = p->rchild;
			cout << p->data;

		}
		cout << p->data;
		p = p->rchild;
	}
}

int main() {
	pre->RTag = 1;
	pre->rchild = NULL;
	BiThrTree tree, Thrt;

	cout << "请输入建立二叉链表的序列，例如(ABD#G##E##CF###):\n";
	CreateBiTree(tree);
	InOrderThreading(Thrt, tree);
	printf("\n");
	cout << "前序遍历线索二叉树的结果为：\n";
	PreOrderTraverse_Thr(Thrt);
	printf("\n");
	cout << "中序遍历线索二叉树的结果为：\n";
	InOrderTraverse_Thr(Thrt);
	printf("\n");
	cout << "后序遍历线索二叉树的结果为：\n";
	AfterOrderTraverse_Thr(Thrt);
	cout << endl;
}