exam3.h

森林的层次遍历、广义表形式输出等关于森林的一些基本操作

#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();												//构造函数
	~BT();												//析构函数
	void createBinTree(BTnode<T> * &root);				//以先序输入构造链表二叉树
	void createBinTree();								//以顺序方式构造二叉树
	void inOrder(BTnode<T> *p);					//以中序遍历二叉树
	int height(BTnode<T> *p);							//求二叉树的高度
	int Nodecount(BTnode<T> *p);						//求二叉树的结点个数
	BTnode<T>* trans(vector<T> a,int i);				//将将按顺序方式存储在数组中的二叉树转换为二叉链表形式
	void filecreat(BTnode<T> * &root);					//文件读取构造二叉树
	void fcreatTree(ifstream& f,BTnode<T> *&p);			//文件读取构造二叉树的递归
	void swap(BTnode<T> * &root);						//交换二叉树中每个结点的左右孩子指针的值
	void create(BTnode<T>* &root);						//创建拓展二叉树
	void destroy(BTnode<T>* &p);						//销毁二叉树
	BTnode<T> *root;
};
template <class T>						
BT<T>::BT()													//构造函数
{
	root=NULL;
}
template <class T>
void BT<T>::createBinTree(BTnode<T> * &root)				//以先序输入构造链表二叉树
{
	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()								//以顺序方式构造二叉树
{
	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){					//将将按顺序方式存储在数组中的二叉树转换为二叉链表形式
	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)						//交换二叉树中每个结点的左右孩子指针的值
{
	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)			//文件读取构造二叉树的递归
{
	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)			//文件读取构造二叉树
{
    char ch[40];char a;string s;
	cout<<"请输入文件的绝对路径："<<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)			//创建拓展二叉树
{
	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){				//复制二叉树
	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>							//析构函数
BT<T>::~BT()
{
	destroy(root);
}