exam5.cpp

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

#include<iostream>
#include"exam3.h"
#include<fstream>
#include<string>
#include<vector>
using namespace std;
template<class T>
struct Tnode{				//森林的结点结构
	T data;
	Tnode<T> *child,*brother;
};
//****************************************************************
template<class T>
struct lnode
{
	int tag;
	union
	{
		T data;
		lnode<T> *sublist;
	}val;
	lnode<T> *link;
};
//****************************************************************
template<class T>
class GL{
public:
	void disGL(lnode<T> *p)
	{
		if(p!=NULL)
		{
			if(p->tag==1)
			{
				cout<<"(";
				if(p->val.sublist==NULL)
				cout<<" ";
				else disGL(p->val.sublist);
			}
			else cout<<p->val.data;
		}
		

	}
};
//****************************************************************
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);
	void show(Tnode<T>* p);
	BTnode<T> *root;
};
template<class T>
Tree<T>::Tree()				//构造函数
{
	root=NULL;				//初始化根结点
}
//*********************************************************************
/*template <class T>						
void TBT<T>::fcreatTree(ifstream& f,TBTnode<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 TBT<T>::filecreat(TBTnode<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);
	}
}
//****************************************************************
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)?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)		//层次遍历森林
{
	
}
//****************************************************************
template<class T>
void Tree<T>::display2(Tnode<T>* p)		//输出一个森林中每个结点的值及其对应的层次数
{
	
}
//****************************************************************
template<class T>
void Tree<T>::show(Tnode<T>* p)			//输出一个森林的广义表形式	
{
	if(p!=NULL)
	{
		cout<<"("<<p->data;
		show(p->child);
		if(p->brother!=NULL)
		{
			cout<<"),";
			show(p->brother);
		}
		else cout<<
	}
}
void main()
{
}