#include<iostream>
#include"exam1.h"
#include"exam3.h"
#include<fstream>
#include<string>
using namespace std;
template<class T>
struct Tnode{				//森林的結(jié)點(diǎn)結(jié)構(gòu)
	T data;
	Tnode<T> *child,*brother;
};
//****************************************************************
template<class T>
class Tree{
public:
	Tree();
	~Tree();
	void filecreat(Tnode<T> * &root);				//文件讀取構(gòu)造二叉樹
	void fcreatTree(ifstream& f,Tnode<T> *&p);		//文件讀取構(gòu)造二叉樹的遞歸
	void trans(Tnode<T>* p,BTnode<T>* &root);
	int height(Tnode<T>* p);
	int Nodecount(Tnode<T>* p);
	void display1(Tnode<T>* &p);
	void display2(Tnode<T>* p,int i);
	void exch_to(Tnode<T>* p);
	void show(Tnode<T>* p);
	Tnode<T> *root;
};
template<class T>
Tree<T>::Tree()				//構(gòu)造函數(shù)
{
	root=NULL;				//初始化根結(jié)點(diǎn)
}
//*********************************************************************
template <class T>						
void Tree<T>::fcreatTree(ifstream& f,Tnode<T> *&p)//讀取文件的遞歸程序
{
	int a1,a2;char ch1,ch2;								
	p=new Tnode<T>;
	f>>p->data;
	f>>a1;f>>a2;f>>ch1;f>>ch2;	
	if(ch1=='0')
		fcreatTree(f,p->child);
	else p->child=NULL;
	if(ch2=='0')
		fcreatTree(f,p->brother);
	else p->brother=NULL;
}
template <class T>
void Tree<T>::filecreat(Tnode<T> * &root)			//從文件中讀取構(gòu)造二叉樹
{
    char ch[40];char a;string s;
	cout<<"請(qǐng)輸入文件的絕對(duì)路徑："<<endl;
	cin>>ch;
	ifstream input(ch);
	if(!input)
	{
		cout<<"打開文件失敗！"<<endl;
		return;
	}
	getline(input,s);input>>a;
	if(a=='1') 
	{
		root=NULL;
		return;
	}
	else fcreatTree(input,root);
	input.close();
}
//****************************************************************
template<class T>
void Tree<T>::trans(Tnode<T>* p,BTnode<T>* &root)	//將樹(森林)的孩子兄弟鏈表形式轉(zhuǎn)換成二叉樹形式
{
	if(p!=NULL)
	{
		root=new BTnode<T>;
		root->data=p->data;
		trans(p->brother,root->Rchild);
		trans(p->child,root->Lchild);
	}
	else root=NULL;
}
//****************************************************************
template<class T>
int Tree<T>::height(Tnode<T>* p)		//求森林的高度
{
	if(p==NULL)return 0;
	int h1,h2;
	h1=height(p->brother);
	h2=height(p->child);
	return (h1>(h2+1))?h1:(h2+1);
}
//****************************************************************
template<class T>					//求森林的結(jié)點(diǎn)
int Tree<T>::Nodecount(Tnode<T>* p)
{
	if(p==NULL)return 0;
	else return Nodecount(p->brother)+Nodecount(p->child)+1;
}
//****************************************************************
template<class T>
void Tree<T>::display1(Tnode<T>* &p)		//層次遍歷森林
{
	if(p!=NULL)
	{
		List<Tnode<char>*> l;node<Tnode<char>*>* t;
		l.head->data=p;int i=1;
		while(i<Nodecount(p))
		{
			t=l.get_point(i);
			if(t->data->brother!=NULL)
				l.InsElem(t,t->data->brother);
			if(t->data->child!=NULL)
				l.Insert(t->data->child);i++;
		}
		t=l.head;
		while(t!=NULL)
		{
			cout<<t->data->data<<"  ";
			t=t->next;
		}
	}
}
//****************************************************************
template<class T>
void Tree<T>::display2(Tnode<T>* p,int i)		//輸出一個(gè)森林中每個(gè)結(jié)點(diǎn)的值及其對(duì)應(yīng)的層次數(shù)
{
	if(p!=NULL)
	{
		display2(p->brother,i);
		cout<<p->data<<"  level:"<<i<<"\x09";
		i++;
		display2(p->child,i);
		i--;
	}
}
//****************************************************************
template<class T>
void Tree<T>::exch_to(Tnode<T>* p)
{
	if(p!=NULL)
	{
		cout<<p->data;
		if(p->child!=NULL)
		{
			cout<<"(";
			exch_to(p->child);
		}
		if(p->child==NULL&&p->brother==NULL)
			cout<<"))";
		if(p->brother!=NULL)
		{
			cout<<",";exch_to(p->brother);
		}
	}
}
//****************************************************************
template<class T>
void Tree<T>::show(Tnode<T>* p)			//輸出一個(gè)森林的廣義表形式	
{
	cout<<"(";
	exch_to(p);
	cout<<")"<<endl;
}
//****************************************************************
template<class T>
Tree<T>::~Tree()
{
}
/*void main()
{
	Tree<char> t;BT<char> b;
	t.filecreat(t.root);
	t.display2(t.root,1);cout<<endl;
	t.show(t.root);
}*/