//定義類InThrBiTree中的成員函數，文件名為inthrbitree.cpp
#include<iostream>
#include<string>
#include"inthrbitree.h"
using namespace std;
/*
 *前置條件：中序線索二叉樹不存在
 *輸    入：無
 *功    能：構造一棵中序線索二叉樹
 *輸    出：無
 *后置條件：產生一棵中序線索二叉樹 
 */
template <class T>
InThrBiTree<T>::InThrBiTree( )
{ 
	ThrNode<T>* pre = NULL;
	this->root = Creat( );    
	ThrBiTree(root);
}
/*
 *前置條件：中序線索二叉樹已存在
 *輸    入：無
 *功    能：釋放中序線索二叉鏈表中各結點的存儲空間
 *輸    出：無
 *后置條件：中序線索二叉樹不存在 
 */
template <class T>
InThrBiTree<T>::~InThrBiTree(void)
{
    Release(root);
}
/*
 *前置條件：中序線索二叉樹已經存在
 *輸    入：無
 *功    能：獲取指向中序線索二叉樹根結點的指針
 *輸    出：指向中序線索二叉樹根結點的指針
 *后置條件：中序線索二叉樹不變 
 */
template <class T>
ThrNode<T>* InThrBiTree<T>::Getroot( )
{
	return root;
}
/*
 *前置條件: 中序線索二叉樹已經存在
 *輸    入: 無
 *功    能: 查找結點p的后繼結點
 *輸    出：輸出指向結點p的后繼結點的指針
 *后置條件：中序線索二叉樹不變
 */
template <class T>
ThrNode<T>* InThrBiTree<T>::Next(ThrNode<T>* p)
{
	ThrNode<T>* q;
    if (p->rtag==Thread)   q = p->rchild;  //右標志為1，可直接得到后繼結點
    else{   
        q = p->rchild;            //工作指針初始化
        while (q->ltag==Child)    //查找最左下結點
		{
            q = q->lchild;
		}
	}
    return q;
}

/*
 *前置條件：中序線索二叉樹已經存在
 *輸    入：無
 *功    能：中序遍歷一棵線索二叉樹
 *輸    出：線索二叉樹結點數據的一個線性排序
 *后置條件：中序線索二叉樹不變
 */
template <class T>
void InThrBiTree<T>::InOrder(ThrNode<T> *root)
{
    ThrNode<T>* p = root;
    if (root==NULL)  return;     //如果線索鏈表為空，則空操作返回   
    while (p->ltag==Child)       //查找中序遍歷序列的第一個結點p并訪問
    {
        p = p->lchild;
    }
    cout<<p->data<<" ";
    while (p->rchild!=NULL)      //當結點p存在后繼，依次訪問其后繼結點
    {
        p = Next(p);
        cout<<p->data<<" ";
    }
	cout<<endl;
}
/*
 *前置條件：二叉樹不存在
 *輸    入：結點的數據值
 *功    能：構造一棵二叉樹,構造函數調用
 *輸    出：指向根結點的指針
 *后置條件：產生一棵二叉樹
 */
template <class T>
ThrNode<T>* InThrBiTree<T>::Creat( )
{
	ThrNode<T> *root;
	T ch;
	cout<<"請輸入創建一棵二叉樹的結點數據"<<endl;
	cin>>ch;
    if (ch=="#") root = NULL;
    else{	
		 root=new ThrNode<T>;      //生成一個結點
         root->data = ch;
         root->ltag = Child;
		 root->rtag = Child;
         root->lchild = Creat( );   //遞歸建立左子樹
         root->rchild = Creat( );   //遞歸建立右子樹
    } 
	return root;
}
/*
 *前置條件：二叉樹已經存在
 *輸    入：無
 *功    能：給二叉樹建立線索
 *輸    出：無
 *后置條件：產生一棵中序線索二叉樹
 */
template <class T>
void InThrBiTree<T>::ThrBiTree(ThrNode<T> *root)
{
   if (root==NULL) return;         //遞歸結束條件
   ThrBiTree(root->lchild);  
   if (!root->lchild){             //對root的左指針進行處理
        root->ltag = Thread;   
        root->lchild = pre;        //設置pre的前驅線索
   }
   if (!root->rchild) root->rtag = Thread;          //對root的右指針進行處理
   if(pre != NULL){
     if (pre->rtag==Thread)  pre->rchild = root;    //設置pre的后繼線索
   }
   pre = root;
   ThrBiTree(root->rchild);
}
/*
 *前置條件：中序線索二叉樹已經存在
 *輸    入：無
 *功    能：釋放中序線索二叉樹的存儲空間，析構函數調用
 *輸    出：無
 *后置條件：中序線索二叉樹不存在
 */
template<class T>
void InThrBiTree<T>::Release(ThrNode<T>* root)
{
  if (root!=NULL){                 
	  Release(root->lchild);   //釋放左子樹
      Release(root->rchild);   //釋放右子樹
      delete root;
  }  
}