#include<iostream>//cout,cin
#include<string>
using namespace std;

template<class DT>
struct ThrBTNode
{
	DT  data;											// 数据域
	int lflag;											// 左标志域
	int rflag;											// 右标志域
	ThrBTNode* lchild;								// 左指针域
	ThrBTNode* rchild;								// 右指针域
};


template <class DT>										// 创建二叉树
void CreateBiTree(ThrBTNode<DT>*& bt)
{														// 按先序序列的顺序输入二叉树,#为空指针域标志;
	char ch;
	cin >> ch;											// 输入根结点的数据
	if (ch == '#')											// # 表示指针为空，说明树为空
		bt = NULL;
	else
	{
		bt = new ThrBTNode<DT>;							// 新建结点
		if (!bt)
		{
			cout << "申请内存失败！" << endl;
			exit(-1);									// 申请内存失败退出
		}
		bt->lflag = 0;									// 非线索
		bt->rflag = 0;									// 非线索
		bt->data = ch;
		CreateBiTree(bt->lchild);						// 递归创建根结点左子树
		CreateBiTree(bt->rchild);						// 递归创建根结点右子树
	}
	return;
}

ThrBTNode<char>* pre;

//算法5.13												中序线索化二叉树
template <class DT>
void InThread(ThrBTNode<DT>*& p)
{

	if (p != NULL)											// 结点非空
	{
		InThread(p->lchild);							// 中序线索化左子树
		if (p->lchild == NULL)								// 结点无左孩子 
		{
			p->lflag = 1;									// 设置前驱线索标识
			p->lchild = pre;								// 左孩子指向结点遍历前驱
		}
		if (pre->rchild == NULL)							// 结点无右孩子
		{
			pre->rflag = 1;								// 设置后继线索标识
			pre->rchild = p;								// 右孩子指向结点遍历后继
		}
		pre = p;											// 前驱指向当前结点
		InThread(p->rchild);								// 中序线索化右子树
	}
}


template<class DT>										// 构建线索二叉树
ThrBTNode<DT>* CreateInThread(ThrBTNode<DT>*& bt)
{
	ThrBTNode<DT>* root;
	root = new ThrBTNode<DT>;								// 创建头结点
	root->lflag = 0;
	root->rflag = 1;
	root->rchild = bt;
	if (bt == NULL)
		root->lchild = root;
	else
	{
		root->lchild = bt;
		pre = root;
		InThread(bt);									// 中序线索化二叉树
		pre->rchild = root;								// 设置循环链表
		pre->rflag = 1;
		root->rchild = pre;
	}
	return root;
}




//算法5.15												中序遍历中序线索二叉树
template<class DT>
void InThrBiTree(ThrBTNode<DT>* bt)
{
	ThrBTNode<DT>* p;
	p = bt->lchild;										// 从根结点开始
	while (p != bt)										// 结点非空
	{
		while (p->lflag == 0)								// 有左孩子
			p = p->lchild;									// 一路左行
		cout << p->data;									// 访问结点							
		while (p->rflag == 1 && p->rchild != bt)				// 有后继线索且非空
		{
			p = p->rchild;								// 转向后继
			cout << p->data << " ";							// 访问后继结点
		}
		p = p->rchild;								// 无后继线索，转向右子树	
	}
}

template <class DT>										// 显示线索二叉树
void DispBiTree(ThrBTNode<DT>* bt, int level)
{
	if (bt)												// 空二叉树不显示
	{
		DispBiTree(bt->rchild, level + 1);					// 显示右子树
		cout << endl;										// 显示新行
		for (int i = 0; i < level - 1; i++)
			cout << "   ";									// 确保在第level列显示节点
		cout << bt->data;									// 显示节点
		DispBiTree(bt->lchild, level + 1);					// 显示左子树  
		cout << endl;
	}//if
}//DisplayBTree

//算法5.9												销毁二叉树
template <class DT>
void DestroyThrBiTree(ThrBTNode<DT>*& bt)
{
	if (bt)
	{
		DestroyThrBiTree(bt->lchild);
		DestroyThrBiTree(bt->rchild);
		delete bt;
	}
}

void dispmenu()
{															// 显示主菜单
	cout << endl;
	cout << "1-创建二叉树\n";
	//cout<<"2-先序线索化二叉树的先序遍历\n";
	//cout<<"3-先序遍历先序线索化二叉树\n";
	cout << "4-中序线索化二叉树\n";
	cout << "5-中序遍历中序线索二叉树\n";
	cout << "6-显示二叉树\n";
	cout << "7-退出\n";
}

// 测试数据
string  fbt = "a b d # # e # # c f # # g # #";				// 满二叉树最后一层每个叶结点后有两个#
string  cbt = "a b d # # e # # c # #";						// 完全二叉树每个叶结点后有两个#
string  gbt = "a b # d # # c e # # #";						// 一般二叉树
string  obt = "a b c d # # # # #";							// 左斜树

int main()
{

	//char pause;
	int level;
	ThrBTNode<char>* bt;


	system("cls");											// 清屏

	int choice;
	do
	{
		dispmenu();											//显示主菜单
		cout << "Enter choice(1~7):";
		cin >> choice;
		switch (choice)
		{
		case 1:											//创建二叉树 
			cout << "测试数据参考：" << endl;
			cout << "满二叉树：" << fbt << endl;
			cout << "完全二叉树：" << cbt << endl;
			cout << "一般二叉树：" << gbt << endl;
			cout << "左斜二叉树：" << obt << endl;
			cout << "请按先序序列的顺序输入二叉树,#为空指针域标志：" << endl;
			CreateBiTree(bt);
			break;
		case 2://先序线索化二叉树

			//PreThread(bt);
			//cin.get(pause);
			//system("pause");
			break;
		case 3://先序遍历先线索化二叉树

			//PreOrDerBiTree(bt);
			 //cin.get(pause);
			//system("pause");
			//breCreateInThread(bt);	
		case 4:										//中序线索化二叉树
			bt = CreateInThread(bt);
			cout << "中序线索化成功！";
			cout << endl;
			break;
		case 5:										//中序遍历中序线索二叉树
			cout << "中序遍历序列为：" << endl;
			cout << endl;
			InThrBiTree(bt);
			break;
		case 6:											//显示二叉树
			cout << "2-显示二叉树" << endl;
			level = 1;
			DispBiTree(bt, level);
			cout << endl;
			break;
		case 7://退出
			cout << "结束运行!" << endl;
			DestroyThrBiTree(bt);
			break;
		default://非法选择
			cout << "Invalid choice\n";
			break;
		}
	} while (choice != 7);

	return 0;
}