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;
	}
}