//程序用法：本程序二叉樹的構造過程采用廣義表作為輸入，預先把節點信息以廣義表字符串形式存儲在文本
//文件中，程序運行首先從文件中讀出節點信息構造二叉樹。
//注意：文件中每一個字母代表一個節點元素值；
//      每個根結點作為由子樹構成的表的名字放在前面；
//      每個結點的左孩子與右孩子用逗號隔開，若只有右孩子而無左孩子，逗號不能省略；
//      整個廣義表以@作為結尾!!!，切記。
#include<iostream>
#include<fstream>
#include<limits>
#include<queue>//為了避免代碼過于冗余，在此不自定義隊列類，使用系統容器代替。
#include<stack>//同上
using namespace std;

char read(char *A)//從字符數組讀取字符
{
	static count=0;
	return A[count++];
}

//樹結點類:
class BinaryTree;
class BinTreeNode{
friend class BinaryTree;
private:
	BinTreeNode *leftChild,*rightChild;//左右孩子指針
	char data;//節點元素
public:
	BinTreeNode():leftChild(NULL),rightChild(NULL){}
	BinTreeNode(char d,BinTreeNode *lp=NULL,
		BinTreeNode *rp=NULL):data(d),leftChild(lp),rightChild(rp){}
	char GetData()//獲取節點元素
	{
		return data;
	}
	BinTreeNode *GetLeftChild()//取得左孩子指針
	{
		return leftChild;
	}
	BinTreeNode *GetRightChild()//取得右孩子指針
	{
		return rightChild;
	}
	void SetData(char d)//設置節點元素值
	{
		data=d;
	}
	void SetLeftChild(BinTreeNode *p)//設置左孩子指針
	{
		leftChild=p;
	}
	void SetRightChild(BinTreeNode *p)//設置右孩子指針
	{
		rightChild=p;
	}
};

//二叉樹鏈表類
class BinaryTree{
private:
	BinTreeNode *root;//根結點
	void destroy(BinTreeNode *p);//銷毀結點P
	void PreOrderTravers(BinTreeNode *r);//前序遍歷
	void InOrderTravers(BinTreeNode *r);//中序遍歷
	void PostOrderTravers(BinTreeNode *r);//后序遍歷
	int length(BinTreeNode *n);//求樹的深度
public:
	BinaryTree():root(NULL){}
	BinaryTree(char d)
	{
		root=new BinTreeNode(d);
	}
	virtual~BinaryTree()
	{
		destroy(root);
	}
    bool IsEmpty(){return root==NULL? true:false;}//判斷樹非空
    void build(char *A);//建立二叉樹
	int length(){return length(root);};//求樹的深度接口
    void PreOrderTravers()//前序遍歷接口
	{
		PreOrderTravers(root);
	}
	void InOrderTravers()//中序遍歷接口
	{
		InOrderTravers(root);
	}
	void PostOrderTravers()//后序遍歷接口
	{
		PostOrderTravers(root);
	}
	void LevelOrderTravers();//層次遍歷
};
//成員函數實現
void BinaryTree::build(char *A)//建立二叉樹，由廣義表輸入
{
	stack<BinTreeNode*> t;
	BinTreeNode *p;
	int flag;
    do
	{
		char ch=read(A);
		switch(ch)
		{
		case '@':return;
		case '(':{t.push(p);flag=1;}break;
		case ')':t.pop();break;
		case ',':flag=2;break;
		default:{
			        p=new BinTreeNode(ch);
                    if(root==NULL)
					{
						root=p;
					}
					else
					{
						if(flag==1)
						{
							t.top()->SetLeftChild(p);
						}
						else
						{
							t.top()->SetRightChild(p);
						}
					}
				}
			break;
		}
	}while(true);
}
int BinaryTree::length(BinTreeNode *n)//求樹深度
{
	if(n==NULL)
	{
		return 0;
	}
	else
	{
		int lclen=length(n->GetLeftChild());
		int rclen=length(n->GetRightChild());
		if(lclen<rclen)
			return rclen+1;
		else
			return lclen+1;
	}
}
void BinaryTree::destroy(BinTreeNode *p)//銷毀二叉樹
{
	if(p!=NULL)
	{
		destroy(p->GetLeftChild());
		destroy(p->GetRightChild());
		delete p;
	}
}
//前序遍歷
void BinaryTree::PreOrderTravers(BinTreeNode *r)
{
	if(r!=NULL)
	{
		cout<<r->GetData()<<" ";
		PreOrderTravers(r->GetLeftChild());
		PreOrderTravers(r->GetRightChild());
	}
}
//中序遍歷
void BinaryTree::InOrderTravers(BinTreeNode *r)
{
	if(r!=NULL)
	{
		InOrderTravers(r->GetLeftChild());
		cout<<r->GetData()<<" ";
		InOrderTravers(r->GetRightChild());
	}
}
//后序遍歷
void BinaryTree::PostOrderTravers(BinTreeNode *r)
{
	if(r!=NULL)
	{
		PostOrderTravers(r->GetLeftChild());
		PostOrderTravers(r->GetRightChild());
		cout<<r->GetData()<<" ";}
}
//層次遍歷
void BinaryTree::LevelOrderTravers()
{
	queue<BinTreeNode*> q;
	BinTreeNode *p=root;
	if(p)
		q.push(p);
	while(!q.empty())
	{
		p=q.front();
		cout<<p->GetData()<<" ";
		if(p->GetLeftChild())
			q.push(p->GetLeftChild());
		if(p->GetRightChild())
			q.push(p->GetRightChild());
		q.pop();
	}
}

void Reset()//輸入異常處理函數
{
	cout<<"輸入非數字字符,請重輸:\n";
	cout<<std::flush;
    std::cin.clear();
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n' );
}
//主函數
void main()
{
	BinaryTree BTree;
	char *A=new char[30];
	ifstream file("node.txt",ios::in);
	if(!file)
	{
		cout<<"節點文件打開失敗,請先配置好二叉樹的節點文件!";
		return;
	}
	file.getline(A,30);
	file.close(); 
	BTree.build(A);
	cout<<"二叉樹構造完畢!"<<endl;
	do
	{
		cout<<endl;
		cout<<"\t\t\t****請選擇操作****\n";
        cout<<"\t\t\t****1.先根遍歷****\n";
	    cout<<"\t\t\t****2.中根遍歷****\n";
        cout<<"\t\t\t****3.后根遍歷****\n";
        cout<<"\t\t\t****4.層次遍歷****\n";
     	cout<<"\t\t\t****5.樹的深度****\n";
    	cout<<"\t\t\t****6.退出模擬****\n";
    	cout<<"請選擇:";
	    int s;//選擇
		while(!(cin>>s))
			 Reset();
	    switch(s)
		{
     	case 1:cout<<endl<<"先根遍歷結果:"<<endl;BTree.PreOrderTravers();break;
	    case 2:cout<<endl<<"中根遍歷結果:"<<endl;BTree.InOrderTravers();break;
	    case 3:cout<<endl<<"后根遍歷結果:"<<endl;BTree.PostOrderTravers();break;
        case 4:cout<<endl<<"層次遍歷結果:"<<endl;BTree.LevelOrderTravers();break;
		case 5:cout<<endl<<"該二叉樹的深度為:";cout<<BTree.length();break;
		case 6:return;
     	default:cout<<"請正確選擇!\n";break;
		}
	}while(true);
}