#include <iostream>
#include<fstream>
#include<string>
#include<vector>
using namespace std;
template <class T>
struct BTnode
{
    T data;
    BTnode<T> *Lchild,*Rchild;
};
template <class T>
class BT{
public:
	BT();												//構(gòu)造函數(shù)
	~BT();												//析構(gòu)函數(shù)
	void createBinTree(BTnode<T> * &root);				//以先序輸入構(gòu)造鏈表二叉樹
	void createBinTree();								//以順序方式構(gòu)造二叉樹
	void inOrder(BTnode<T> *p);					//以中序遍歷二叉樹
	int height(BTnode<T> *p);							//求二叉樹的高度
	int Nodecount(BTnode<T> *p);						//求二叉樹的結(jié)點(diǎn)個(gè)數(shù)
	BTnode<T>* trans(vector<T> a,int i);				//將將按順序方式存儲(chǔ)在數(shù)組中的二叉樹轉(zhuǎn)換為二叉鏈表形式
	void filecreat(BTnode<T> * &root);					//文件讀取構(gòu)造二叉樹
	void fcreatTree(ifstream& f,BTnode<T> *&p);			//文件讀取構(gòu)造二叉樹的遞歸
	void swap(BTnode<T> * &root);						//交換二叉樹中每個(gè)結(jié)點(diǎn)的左右孩子指針的值
	void create(BTnode<T>* &root);						//創(chuàng)建拓展二叉樹
	void destroy(BTnode<T>* &p);						//銷毀二叉樹
	BTnode<T> *root;
};
template <class T>						
BT<T>::BT()													//構(gòu)造函數(shù)
{
	root=NULL;
}
template <class T>
void BT<T>::createBinTree(BTnode<T> * &root)				//以先序輸入構(gòu)造鏈表二叉樹
{
	T x;
	cin>>x;
	if(x=='.')
    {
        root=NULL;
    }
    else
    {
		root=new BTnode<T>;
        root->data =x;
        createBinTree(root->Lchild);
        createBinTree(root->Rchild);
    }
}
template <class T>
void BT<T>::createBinTree()								//以順序方式構(gòu)造二叉樹
{
	T x;
	cin>>x;
	vector<T> v;
	while(x!='.')
	{
		v.push_back(x);
		cin>>x;
	}
}
template <class T>
void BT<T>::inOrder(BTnode<T> *p)				//以中序遍歷二叉樹
{
	if(p!=NULL)
    {
        inOrder(p->Lchild);
        cout<<p->data<<"  ";
        inOrder(p->Rchild);
    }
}
template <class T>
int BT<T>::height(BTnode<T> *p)					//求二叉樹的高度
{
	int h1,h2;
	if(p==NULL)return 0;
	h1=height(p->Lchild);
	h2=height(p->Rchild);
	return (h1>h2)?(h1+1):(h2+1);
}
template <class T>
int BT<T>::Nodecount(BTnode<T> *p)						//求二叉樹的高度
{
	int h1,h2;
	if(p==NULL)return 0;
	h1=Nodecount(p->Lchild);
	h2=Nodecount(p->Rchild);
	return (1+h1+h2);
}
template <class T>
BTnode<T>* BT<T>::trans(vector<T> a,int i){					//將將按順序方式存儲(chǔ)在數(shù)組中的二叉樹轉(zhuǎn)換為二叉鏈表形式
	BTnode<T> *bt;
	if(i<a.size()&&a[i]!=-1)
	{
		bt=new BTnode<T>;
		bt->data=a[i];
		bt->Lchild=trans(a,2*i);
		bt->Rchild=trans(a,2*i+1);
	}
	else 
		return NULL;
}
template <class T>
void BT<T>::swap(BTnode<T> * &root)						//交換二叉樹中每個(gè)結(jié)點(diǎn)的左右孩子指針的值
{
	BTnode<T> *p;
	if(root!=NULL)
	{
		p=new BTnode<T>;
		p=root->Lchild;
		root->Lchild=root->Rchild;
		root->Rchild=p;
		swap(root->Lchild);
		swap(root->Rchild);
	}
}
template <class T>
void BT<T>::fcreatTree(ifstream& f,BTnode<T> *&p)			//文件讀取構(gòu)造二叉樹的遞歸
{
	char ch1,ch2;
	p=new BTnode<T>;
	f>>p->data;
	f>>ch1;f>>ch2;
	if(ch1=='0')
		fcreatTree(f,p->Lchild);
	else p->Lchild=NULL;
	if(ch2=='0')
		fcreatTree(f,p->Rchild);
	else p->Rchild=NULL;
}
template <class T>
void BT<T>::filecreat(BTnode<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 BT<T>::create(BTnode<T>* &root)			//創(chuàng)建拓展二叉樹
{
	T x;
	cin>>x;
	if(x!='.')
	{
		root=new BTnode<T>;
		root->data=x;
		create(root->Lchild);
		create(root->Rchild);
	}
	else
		root=NULL;
}
template <class T>
void copy(BTnode<T> *bt,BTnode<T> *newbt){				//復(fù)制二叉樹
	if(bt!=NULL)
	{
		newbt->data=bt->data;
		copy(bt->Lchild,newbt->Lchild);
		copy(bt->Rchild,newbt->Rchild);
	}
	else
		newbt=NULL;
}
template <class T>
void BT<T>::destroy(BTnode<T>* &p)				//銷毀二叉樹
{
	if(p!=NULL)
        {
            destroy(p->Lchild);
            destroy(p->Rchild);
            delete p;
        }
}
template <class T>							//析構(gòu)函數(shù)
BT<T>::~BT()
{
	destroy(root);
}