#include<iostream>
#include<string>
using namespace std;
int n=0;
template <class T>
struct BiNode  {
  T data;       
  BiNode<T> *lchild, *rchild;
};
template <class T>
class BiTree
{
public:
    BiTree( ); 
    ~BiTree(void); 
	BiNode<T>* Getroot();  
    void PreOrder(BiNode<T> *root); 
    void InOrder(BiNode<T> *root); 
    void PostOrder(BiNode<T> *root); 
    void LeverOrder(BiNode<T> *root); 
	void PreOrdercount(BiNode<T>*root);
private:
    BiNode<T> *root; 
    BiNode<T> *Creat( ); 
    void Release(BiNode<T> *root); 
};
template<class T>
BiTree<T>::BiTree( )
{
	//int m;
	//cout<<"請輸入結點的個數(shù)："<<endl;
	//cin>>m;
	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>::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); 
        cout<<root->data<<" "; 
        InOrder(root->rchild); 
	}
}
template <class T>
void BiTree<T>::PostOrder(BiNode<T> *root)
{ 
    if (root==NULL)   return; 
    else{	
        PostOrder(root->lchild); 
        PostOrder(root->rchild);
        cout<<root->data<<" "; 
	}
}
template <class T>
void BiTree<T>::LeverOrder(BiNode<T> *root)
{
	const int MaxSize = 100;
	int front = 0;
	int rear = 0;  //采用順序隊列，并假定不會發(fā)生上溢
	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;
		}
	}
}
template <class T>
BiNode<T>* BiTree<T>::Creat( )
{
	BiNode<T>* root;
	T ch;
	cout<<"請輸入創(chuàng)建一棵二叉樹的結點數(shù)據(jù)"<<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;
  }  
}
template<class T>
void BiTree<T>::PreOrdercount(BiNode<T>*root)
{  if(root)
{ 
	if(!root->lchild&&root->rchild||root->lchild&&!root->rchild)  n++;
	PreOrdercount(root->lchild);
	PreOrdercount(root->rchild);
}
}
int main()
{	

	BiTree<string> bt; 
	char e;
	BiNode<string>* root = bt.Getroot( ); 
	while(true)
	{
		cout<<"*************************************"<<endl;
		cout<<"*\t\t實現(xiàn)二叉樹的基本功能\t\t*"<<endl;
		cout<<"*\t\t 1.前序遍歷\t\t\t*"<<endl;
		cout<<"*\t\t 2.中序遍歷\t\t\t*"<<endl;
		cout<<"*\t\t 3.后序遍歷\t\t\t*"<<endl;
		cout<<"*\t\t 4.層序遍歷\t\t\t*"<<endl;
		cout<<"*\t\t 5.計算單枝節(jié)點數(shù)\t\t*"<<endl;
		cout<<"*\t\t 6.退出\t\t\t*"<<endl;
		cout<<"*************************************"<<endl;
		do{
		cout<<"請輸入你的選擇(1-6):";
		cin>>e;
		}while(e<'1'||e>'6');
		switch(e)
		{
		 case'1':
			cout<<"前序遍歷:"<<endl;
			bt.PreOrder(root);
			cout<<endl;
			break;
		 case'2':
			cout<<"中序遍歷:"<<endl;
			bt.InOrder(root);
			cout<<endl;
			break;
		case'3':
			cout<<"后序遍歷:"<<endl;
			bt.PostOrder(root);
			cout<<endl;
			break;
		case'4':
			cout<<"層序遍歷:"<<endl;
			bt.LeverOrder(root);
			cout<<endl;
			break;
		case'5':
			cout<<"計算單枝節(jié)點數(shù):";
			bt.PreOrdercount(root);
			cout<<n<<endl;
			break;
		case'6':
			return 0;
		}
	}
}