胡学刚版 数据结构 实验3代码 合工大

#include 

using namespace std;
#define RIGHT 1
#define LEFT -1
#define ROOT 0
#define MAX 59
#define HEADSPACE 20

typedef char elementtype;

class tree
{
public:
	tree（）{father=NULL;lchild=NULL;rchild=NULL;self=this;};//初始化
	tree* getfather（）const{return father;};//获取父结点指针
	tree* getlchild（）const{return lchild;};//获取左孩子结点指针
	tree* getrchild（）const{return rchild;};//获取右孩子结点指针
	tree* getself（）const{if（this!=NULL）return self;else return NULL;};//获取自身指针;
	elementtype getdata（）const{return data;};//获取结点值
	bool empty（）const{return lchild==NULL&&rchild==NULL&&data==‘\0‘;};//判断树是否为空
	bool intree（tree *add）const;//判断结点是否在树内
	bool setdata（elementtype da）{data=da;return true;};//设置结点值
	bool setfather（tree *add）{father=add;return true;};//设置父结点指针
	bool setlchild（tree *add）{deletelchild（）;lchild=add;if（getlchild（）!=NULL）getlchild（）->setfather（getself（））;return true;};//设置左孩子指针
	bool setrchild（tree *add）{deleterchild（）;rchild=add;if（getrchild（）!=NULL）getrchild（）->setfather（getself（））;return true;};//设置右孩子指针
	bool resetlchild（tree *add）{lchild=add;if（getlchild（）!=NULL）getlchild（）->setfather（getself（））;return true;}//重设左孩子指针
	bool resetrchild（tree *add）{rchild=add;if（getrchild（）!=NULL）getrchild（）->setfather（getself（））;return true;}//重设右孩子指针
	bool getadd（elementtype datree *&add）const;//按值查找结点
	bool insertlchild（tree *add）;//插入左子树
	bool insertrchild（tree *add）;//插入右子树
	bool deletelchild（）;//删除左子树
	bool deleterchild（）;//删除右子树
	bool deleteself（）;//删除整棵树
	int gettype（）const;//获取结点是什么类型的孩子 根，左孩子，右孩子
	int getfrool（）const;//获取结点的层数
	bool gethigh（int &n）const;//获取树高

private:
	tree *father*lchild*rchild*self;
	elementtype data;
};

bool tree::intree（tree *add）const
{
	if（empty（）&&add==NULL）
		return true;
	tree *p=add;
	while（p!=NULL&&p!=self）
		p=p->getfather（）;
	if（p==self）
		return true;
	else
		return false;
}

bool tree::insertlchild（tree *add）
{
	if（add->getfather（）!=NULL）
	{
		if（add->gettype（）==RIGHT）
			add->getfather（）->setrchild（NULL）;
		else
			add->getfather（）->setlchild（NULL）;
	}
	if（lchild!=NULL）
		return false;
	lchild=add;
	add->setfather（getself（））;
	return true;
}

bool tree::insertrchild（tree *add）
{
	if（add->getfather（）!=NULL）
	{
		if（add->gettype（）==RIGHT）
			add->getfather（）->setrchild（NULL）;
		else
			add->getfather（）->setlchild（NULL）;
	}
	if（rchild!=NULL）
		return false;
	rchild=add;
	add->setfather（getself（））;
	return true;
}

bool tree::getadd（elementtype datree *&add）const
{
	tree *p=getself（）;
	if（p!=NULL）
	{
		if（p->data==da）
		{
			add=p;
			return true;
		}
		return （p->getlchild（）->getadd（daadd））||（p->getrchild（）->getadd（daadd））;
	}
	else
		return false;
}

int tree::gettype（）const
{
	if（getfather（）==NULL）
	{
		return ROOT;
	}
	else
	{
		if（self==getfather（）->getlchild（））
		{
			return LEFT;
		}
		else
			return RIGHT;
	}
}

int tree::getfrool（）const
{
	int n=0;
	tree *p=getself（）;
	do{
		p=