Problem B: 排序二叉树

Problem Description

根据输入的int数组建立一棵二叉排序树，然后根据指令进行相应的操作。指令只有两种Insert x, Delete x。不考虑空树的情况。
Insert x 指令需要你将x插入到建好的二叉排序树中（允许存在相同元素）。
Delete x 指令需要你将值为x的结点删除（只删除一个，而且不保证x一定在二叉排序树中）。

 

 Input Description

 第一行为测试数据的组数n, 下面有n组测试数据。对于每组测试数据，第一行为用空格隔开的int数列，数量不超过1000，你需要用这个数据初始化一棵排序二叉树，下面一行为指令数m, 接下来的m行为m个指令。格式按照题目描述。数据均为int型。

 

 Output Description

 

输出一共有n行，对应每组测试数据，在所有的指令都执行完后，把当前的排序二叉树中序输出，元素之间用空格隔开。

Sample Input

1
1 3 5 2
2
Insert 4
Delete 5

 Sample Output

1 2 3 4

 Hint

本题必须用建立二叉排序树的方式做，会检查代码。

 我的想法：

 我的代码：

#define _CRT_SECURE_NO_WARNINGS 1
 
#include 
#include 
#include 
using namespace std;
 
//二叉链表存储表示
typedef struct BSTNode
{
	int data;
	struct BSTNode *lchild, *rchild;
}BSTNode, *BSTree;
 
char buffer[100];
 
//二叉树的插入
void InsertBST(BSTree &T, int e)
{
	if (!T)//如果该树为空
	{
		//创建新的节点
		BSTree S = new BSTNode;
		S->data = e;
		S->lchild = S->rchild = NULL;
		T = S;
	}
	else if (e < T->data)//在左边
	{
		InsertBST(T->lchild, e);
	}
	else if (e > T->data)
	{
		InsertBST(T->rchild, e);
	}
}
 
void DeleteBST(BSTree &T, int key)
{
	BSTree p = T;
	BSTree f = NULL;
	//从根查找关键字等于key的节点
	while (p)
	{
		if (p->data == key)
		{
			break;
		}
		f = p;//记录上一个p值
		if (key < p->data)
		{
			p = p->lchild;
		}
		else if (key > p->data)
		{
			p = p->rchild;
		}
	}
	if (p == NULL)
	{
		return;
	}
 
	//三种情况：*p左右子树均不为空，无右子树，无左子树
	BSTree q = p;
	if (p->lchild && p->rchild)
	{//左右子树均不为空
		BSTree s = p->lchild;
		while (s->rchild)
		{
			q = s;
			s = s->rchild;//向右到尽头
		}
		p->data = s->data;//改变数据，s指向被删节点的前驱
		if (q != p)
		{
			p->rchild = s->lchild;
		}
		else
		{
			q->lchild = s->lchild;
		}
		delete s;
		return;
	}
	else if (!p->rchild)
	{
		p = p->lchild;
	}
	else if (!p->lchild)
	{
		p = p->rchild;
	}
 
	if (!f)
	{
		T = p;
	}
	else if (q == f->lchild)
	{
		f->lchild = p;
	}
	else
	{
		f->rchild = p;
	}
	delete q;
}
 
void Print(BSTree &T)
{
	if (!T)
	{
		return;
	}
	Print(T->lchild);
	printf("%d ", T->data);
	Print(T->rchild);
}
 
int IsNum(char ch)
{
	if (ch >= '0' && ch <= '9')
	{
		return  1;
	}
	return 0;
}
 
int GetNum(int &i)
{
	int num = 0;
	int n = 1;
	while (IsNum(buffer[i]))
	{
		num = num * n + (buffer[i] - '0');
		n = 10;
		i++;
	}
	return num;
}
 
int main()
{
	int n, k;//表示有n组测试数据
	int elem;
	BSTree T = NULL;
	
	cin >> n;
	getchar();
	while (n--)
	{
		gets(buffer);
		int length = strlen(buffer);
		for (int i = 0; i < length; i++)
		{
			if (IsNum(buffer[i]))
			{
				int num = GetNum(i);
				InsertBST(T, num);
			}
		}
		cin >> k;
		string str;
		while (k--)
		{
			cin >> str;
			if (str == "Insert")
			{
				cin >> elem;
				InsertBST(T, elem);
			}
			else
			{
				cin >> elem;
				DeleteBST(T, elem);
			}
		}
		Print(T);
	}
	return 0;
}