#include
#include
#include
using?namespace?std;
struct?stuinfo							//學生信息結構體
{
	char?name[20];
	double?math;
	double?chin;
};
struct?infonode							//二叉搜索樹的節點
{
	stuinfo?info;
	infonode?*left;
	infonode?*right;
};
class?BST								//二叉搜索樹的類表示
{
public:
	BST（）;										//構造函數
	void?input（ifstream?&）;						//輸入函數，實質是插入函數
	infonode?*?insert（stuinfo?pinfonode?*q）;	//插入操作的遞歸實現
	void?inorder（infonode?*pofstream?&）;		//中序輸出
	void?file3（ifstream?&）;						//處理第三個輸入文件
	void?del（infonode?*pstuinfo?inf）;			//刪除操作
	void?file4（ifstream?&ofstream?&）;			//處理第四個輸入文件
	void?search（infonode?*ofstream?&doubledouble?double?double）;//查找操作
	void?pre（infonode?*）;						//尋找所給節點的直接前驅，并將給定節點所在子樹置空
	infonode?*root;								//根節點
	bool?cm;									//1是數學，0是語文
};
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）;			//調用insert函數
	}
}
infonode?*BST::insert（stuinfo?pinfonode?*q）
{
	if（root?==?NULL）
	{
		root=new?infonode;
		root->info.math=-1;		//標記math=-1為葉子結點
		root=?insert（proot）;	//調用insert2函數
	}
	else
	{
		if（q->info.math?==?-1）
		{
			q->info=p;
			q->left=NULL;
			q->right=NULL;
			return?q;
		}
		else
		{
			if（cm）								//是數學樹
			{
				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）;			//遞歸調用
				}
				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								//語文樹
			{
				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）;					//中序輸出的遞歸實現
		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）	//如果匹配，則進行刪除操作
	{
		if（p->left?==?NULL?&&?p->right?==?NULL）						//如果沒有子樹
		{
			pre（p）;													//找到前驅并將前驅的子樹置空
			delete?p;
			p=NULL;
		}
		else?if（p->left