#include <iostream>
#include <strstream>
#include <iomanip>
#include <stack>

using namespace std;


//定義二叉樹節(jié)點類型
template<class T>class BinaryTree;
template<class T>struct BTreeNode
{
	 private:
		 BTreeNode<T>*left;   //左子樹指針
		 BTreeNode<T>*right;  //右子樹指針
	 public:
		 T data;  //數據域
		 //構造函數
		 BTreeNode():left(NULL),right(NULL){}
		 BTreeNode(T item,BTreeNode<T>*left1=NULL,BTreeNode<T>*right1=NULL):data(item),left(left1),right(right1){}
		 BTreeNode<T>*&Left(){return left;}
		 BTreeNode<T>*&Right(){return right;}
		 friend class BinaryTree<T>;//二叉樹類為二叉樹結點類的友元類
};
//二叉樹類定義
template<class T>class BinaryTree
{
	private:
		BTreeNode<T>* root;
	public:
		//構造函數,初始化二叉樹為空
		BinaryTree(){root=NULL;}
		//根據字符數組a的二叉樹廣義表建立對應的二叉樹存儲結構
		void CreateBTree(char* a);
		//判斷二叉樹是否為空
		bool BTreeEmpty() {return root==NULL;}
		//按中序遍歷輸出二叉樹中的所有結點
		void TraverseBTree();
		//用于遍歷的遞歸函數
		void Traverse(BTreeNode<T>*&BT);
		//用于中序遍歷的非遞歸函數
		//void InOrder(BTreeNode<T>*&p);
		void InOrder();


};

//根據字符數組a的二叉樹廣義表建立對應的二叉樹存儲結構
template<class T>
void BinaryTree<T>::CreateBTree(char *a)
{
	BTreeNode<T> *s[80];  //S數組作為存儲二叉樹中根結點指針的棧
	int top=-1;          //top作為s棧的棧頂指針
	root=NULL;           //給樹根指針置空
	BTreeNode<T> *p=NULL;//定義P為指向二叉樹結點的指針
//用K作為處理結點的左子樹和右子樹的標記,K=1處理左子樹,K=2處理右子樹
	int k;
	istrstream ins(a);//把字符串a定義為輸入字符串流對象ins
	char ch;
	ins>>ch;//從ins流對象順序讀入一個字符
	while (ch!='@')
	{    //每循環(huán)一次處理一個讀入的字符,直到掃描到'@'字符為止
		switch(ch)
		{
		case'(':top++; s[top]=p;k=1;break;
		case')':top--;break;
		//case',':top++;k=2;break;
		case ',':k=2;break;
	    default:p=new BTreeNode<T>;
		//default:p=new  BTreeNode<char> (ch);
			p->data=ch;
			p->left=p->right=NULL;
			cout<<setw(2)<<p->data;
			if (root==NULL) root=p;
			else
			{
				if(k==1) 
					s[top]->left=p;
				else 
					s[top]->right=p;
			}
		}
		ins>>ch;
	}

}

//按中序遍歷輸出二叉樹中的所有結點
template<class T>
void BinaryTree<T>::TraverseBTree()
{
	Traverse(root);
}
//用于中序遍歷的遞歸函數

template<class T>
void BinaryTree<T>::Traverse(BTreeNode<T> *&BT)
{
if (BT!=NULL)
{
	//cout<<BT->data<<' ';
	Traverse(BT->left);
	cout<<BT->data<<" ";
	Traverse(BT->right);
}
};

//中序遍歷的非遞歸函數
template<class T>
//void BinaryTree<T>::InOrder(BTreeNode<T> *&p)
void BinaryTree<T>::InOrder()
{
	stack<BTreeNode<T>*> s;
	BTreeNode<T> *p=root;
	do{
		while (p!=NULL){
		s.push(p);
		p=p->left;
		}
		if(!s.empty()){
		p=s.top();
		cout<<p->data<<" ";
		s.pop();
		p=p->right;
		}
	}while(p!=NULL||!s.empty());
}