exam5.h

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

#include<iostream>
#include"exam1.h"
#include"exam3.h"
#include<fstream>
#include<string>
using namespace std;
template<class T>
struct Tnode{				//森林的结点结构
	T data;
	Tnode<T> *child,*brother;
};
//****************************************************************
template<class T>
class Tree{
public:
	Tree();
	~Tree();
	void filecreat(Tnode<T> * &root);				//文件读取构造二叉树
	void fcreatTree(ifstream& f,Tnode<T> *&p);		//文件读取构造二叉树的递归
	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()				//构造函数
{
	root=NULL;				//初始化根结点
}
//*********************************************************************
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)			//从文件中读取构造二叉树
{
    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 Tree<T>::trans(Tnode<T>* p,BTnode<T>* &root)	//将树(森林)的孩子兄弟链表形式转换成二叉树形式
{
	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>					//求森林的结点
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)		//输出一个森林中每个结点的值及其对应的层次数
{
	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)			//输出一个森林的广义表形式	
{
	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);
}*/