#include<iostream>
#include<string>
#include"bitree.h"
using namespace std;

/*
 *前置條件：二叉樹不存在
 *輸    入：無
 *功    能：構造一棵二叉樹
 *輸    出：無
 *后置條件：產生一棵二叉樹 
 */
template<class T>
BiTree<T>::BiTree( )
{
	this->root = Creat( );
}
/*
 *前置條件：二叉樹已存在
 *輸    入：無
 *功    能：釋放二叉鏈表中各結點的存儲空間
 *輸    出：無
 *后置條件：二叉樹不存在 
 */
template<class T>
BiTree<T>::~BiTree(void)
{
	Release(root);
}
/*
 *前置條件：二叉樹已存在
 *輸    入：無
 *功    能：獲取指向二叉樹根結點的指針
 *輸    出：指向二叉樹根結點的指針
 *后置條件：二叉樹不變 
 */
template<class T>
BiNode<T>* BiTree<T>::Getroot( )
{
	return root;
}
template<class T>
void BiTree<T>::Leaf(BiNode<T> *root)
{  if(root==NULL)
     cout<<"無葉子結點"<<endl;
   else if(root->lchild==NULL && root->rchild==NULL)
   {cout<<"葉子結點為:"<<root->data<<" ";}
   else if(root->lchild==NULL && root->rchild!=NULL)
	   Leaf(root->rchild);
   else if(root->lchild!=NULL && root->rchild==NULL)
       Leaf(root->lchild);
   else
   { Leaf(root->lchild);
     Leaf(root->rchild);
   }
	//if(root==NULL)
		//return(0);
	//if(root->lchild==NULL&&root->rchild==NULL)
	    //return(1);
	 //return(Leafcount(root->lchild)+Leafcount(root->rchild));
}
template<class T>
int BiTree<T>::Leafcount(BiNode<T> *root)
{  if(root==NULL)
      return(0);
   if(root->lchild==NULL && root->rchild==NULL)
      return(1);
   //else
   /*{ Leaf(root->lchild);
     Leaf(root->rchild);
   }*/
	//if(root==NULL)
		//return(0);
	//if(root->lchild==NULL&&root->rchild==NULL)
	    //return(1);
	 return(Leafcount(root->lchild)+Leafcount(root->rchild));
}

/*
 *前置條件：二叉樹已存在
 *輸    入：無
 *功    能：前序遍歷二叉樹
 *輸    出：二叉樹中結點的一個線性排列
 *后置條件：二叉樹不變 
 */
template<class T>
void BiTree<T>::PreOrder(BiNode<T> *root)
{
	if(root==NULL)  return;
	else{		
		cout<<root->data<<" ";
        PreOrder(root->lchild);
		PreOrder(root->rchild);
	}
}

/*
 *前置條件：二叉樹已存在
 *輸    入：無
 *功    能：中序遍歷二叉樹
 *輸    出：二叉樹中結點的一個線性排列
 *后置條件：二叉樹不變 
 */
template <class T>
void BiTree<T>::InOrder (BiNode<T> *root)
{
    if (root==NULL)  return;      //遞歸調用的結束條件	          
    else{	
        InOrder(root->lchild);    //中序遞歸遍歷root的左子樹
        cout<<root->data<<" ";    //訪問根結點的數據域
        InOrder(root->rchild);    //中序遞歸遍歷root的右子樹
	}
}
/*
 *前置條件：二叉樹已存在
 *輸    入：無
 *功    能：后序遍歷二叉樹
 *輸    出：二叉樹中結點的一個線性排列
 *后置條件：二叉樹不變 
 */
template <class T>
void BiTree<T>::PostOrder(BiNode<T> *root)
{ 
    if (root==NULL)   return;       //遞歸調用的結束條件
    else{	
        PostOrder(root->lchild);    //后序遞歸遍歷root的左子樹
        PostOrder(root->rchild);    //后序遞歸遍歷root的右子樹
        cout<<root->data<<" ";      //訪問根結點的數據域
	}
}

/*
 *前置條件：二叉樹已存在
 *輸    入：無
 *功    能：層序遍歷二叉樹
 *輸    出：二叉樹中結點的一個線性排列
 *后置條件：二叉樹不變
 */
template <class T>
void BiTree<T>::LeverOrder(BiNode<T> *root)
{
	const int MaxSize = 100;

	int front = 0;
	int rear = 0;  //采用順序隊列，并假定不會發生上溢

	BiNode<T>* Q[MaxSize];
    BiNode<T>* q;

	if (root==NULL) return;
	else{
		Q[rear++] = root;
		while (front != rear)
		{
			q = Q[front++];
     		cout<<q->data<<" "; 		
    		if (q->lchild != NULL)    Q[rear++] = q->lchild;		
			if (q->rchild != NULL)    Q[rear++] = q->rchild;
		}
	}
}

/*
 *前置條件：空二叉樹
 *輸    入：數據ch;
 *功    能：初始化一棵二叉樹,構造函數調用
 *輸    出：無
 *后置條件：產生一棵二叉樹
 */
template <class T>
BiNode<T>* BiTree<T>::Creat( )
{
	BiNode<T>* root;
	T ch;
	cout<<"請輸入創建一棵二叉樹的結點數據"<<endl;
	cin>>ch;
    if (ch=="#") root = NULL;
    else{ 
	     root = new BiNode<T>;       //生成一個結點
         root->data=ch;
         root->lchild = Creat( );    //遞歸建立左子樹
         root->rchild = Creat( );    //遞歸建立右子樹
    } 
    return root;
}

/*
 *前置條件：二叉樹已經存在
 *輸    入：無
 *功    能：釋放二叉樹的存儲空間，析構函數調用
 *輸    出：無
 *后置條件：二叉樹不存在
 */
template<class T>
void BiTree<T>::Release(BiNode<T>* root)
{
  if (root != NULL){                  
	  Release(root->lchild);   //釋放左子樹
      Release(root->rchild);   //釋放右子樹
      delete root;
  }  
}
//#include<iostream>
//#include<string>
//#include"bitree.cpp"
//using namespace std;
 
void main()
{	
	BiTree<string> bt; //創建一棵樹
	BiNode<string>* root = bt.Getroot( );  //獲取指向根結點的指針 

	cout<<"------前序遍歷------ "<<endl;
	bt.PreOrder(root);
	cout<<endl;
	cout<<"------中序遍歷------ "<<endl;
	bt.InOrder(root);
	cout<<endl;
	//cout<<"------后序遍歷------ "<<endl;
	//bt.PostOrder(root);
	//cout<<endl;
	//cout<<"------層序遍歷------ "<<endl;
	//bt.LeverOrder(root);
	//cout<<endl;
	bt.Leaf(root);
	cout<<endl;
	cout<<"葉子總數為:"<<" ";
	cout<<bt.Leafcount(root)<<endl;
	cout<<endl;
}