#include
#include
#include
using?namespace?std;
struct?stuinfo							//學(xué)生信息結(jié)構(gòu)體
{
	char?name[20];
	double?math;
	double?chin;
};
struct?infonode							//二叉搜索樹的節(jié)點(diǎn)
{
	stuinfo?info;
	infonode?*left;
	infonode?*right;
};
class?BST								//二叉搜索樹的類表示
{
public:
	BST（）;										//構(gòu)造函數(shù)
	void?input（ifstream?&）;						//輸入函數(shù)，實(shí)質(zhì)是插入函數(shù)
	infonode?*?insert（stuinfo?pinfonode?*q）;	//插入操作的遞歸實(shí)現(xiàn)
	void?inorder（infonode?*pofstream?&）;		//中序輸出
	void?file3（ifstream?&）;						//處理第三個(gè)輸入文件
	void?del（infonode?*pstuinfo?inf）;			//刪除操作
	void?file4（ifstream?&ofstream?&）;			//處理第四個(gè)輸入文件
	void?search（infonode?*ofstream?&doubledouble?double?double）;//查找操作
	void?pre（infonode?*）;						//尋找所給節(jié)點(diǎn)的直接前驅(qū)，并將給定節(jié)點(diǎn)所在子樹置空
	infonode?*root;								//根節(jié)點(diǎn)
	bool?cm;									//1是數(shù)學(xué)，0是語(yǔ)文
};
BST::BST（）
{
	root=NULL;
}

void?BST::input（ifstream?&in）
{
	while（!in.eof（））
	{
		stuinfo?tem;
		in>>tem.name;
		in>>tem.chin;
		in>>tem.math;
		insert（temroot）;			//調(diào)用insert函數(shù)
	}
}
infonode?*BST::insert（stuinfo?pinfonode?*q）
{
	if（root?==?NULL）
	{
		root=new?infonode;
		root->info.math=-1;		//標(biāo)記math=-1為葉子結(jié)點(diǎn)
		root=?insert（proot）;	//調(diào)用insert2函數(shù)
	}
	else
	{
		if（q->info.math?==?-1）
		{
			q->info=p;
			q->left=NULL;
			q->right=NULL;
			return?q;
		}
		else
		{
			if（cm）								//是數(shù)學(xué)樹
			{
				if（q->info.math?				{
					if（q->right?==?NULL）		//遇空
					{
						q->right=new?infonode;
						q->right->left=NULL;
						q->right->right=NULL;
						q->right->info.math=-1;
					}
					insert（pq->right）;			//遞歸調(diào)用
				}
				else
				{
					if（q->left?==?NULL）
					{
						q->left=new?infonode;
						q->left->left=NULL;
						q->left->right=NULL;
						q->left->info.math=-1;
					}
					insert（pq->left）;
				}
			}
			else								//語(yǔ)文樹
			{
				if（q->info.chin?				{
					if（q->right?==?NULL）
					{
						q->right=new?infonode;
						q->right->left=NULL;
						q->right->right=NULL;
						q->right->info.math=-1;
					}
					insert（pq->right）;
				}
				else
				{
					if（q->left?==?NULL）
					{
						q->left=new?infonode;
						q->left->left=NULL;
						q->left->right=NULL;
						q->left->info.math=-1;
					}
					insert（pq->left）;
				}
			}
		}
	}
	return?NULL;
}
void?BST::inorder（infonode?*p?ofstream?&out）
{
	if（p?==?NULL）
		return;
	else
	{
		inorder（p->leftout）;					//中序輸出的遞歸實(shí)現(xiàn)
		out<info.name<<‘?‘<info.chin<<‘?‘<info.math<		inorder（p->rightout）;
	}
}
void?BST::file3（ifstream?&in）
{
	while（!in.eof（））
	{
		stuinfo?tem;
		in>>tem.name;
		in>>tem.chin;
		in>>tem.math;
		del（roottem）;
	}
}
void?BST::del（infonode?*pstuinfo?inf）
{
	if（p?==?NULL）
		return;
	else?if（inf.chin?==?p->info.chin?&&?inf.math?==?p->info.math）	//如果匹配，則進(jìn)行刪除操作
	{
		if（p->left?==?NULL?&&?p->right?==?NULL）						//如果沒有子樹
		{
			pre（p）;													//找到前驅(qū)并將前驅(qū)的子樹置空
			delete?p;
			p=NULL;
		}
		else?if（p->left