题目描述
编程输入N个不同的大于零的整数，用二叉排序树按由小到大的顺序输出。然后删除其中的一个数X找出其中第K大的那个数，最后将其按由小到大的顺序输出。
输入
共四行，第一行一个整数N；第二行是N个互不相等的正整数（1≤N≤2000000）；第三行一个整数X；第四行是整数K。
输出
第一行是N个排序后的整数；第二行是第K大的那个数；第三行是剩下N-1个数。
样例输入 Copy
5
9 5 22 73 1
5
2
样例输出 Copy
1 5 9 22 73
9
1 9 22 73

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
using namespace std;
const int N=2000005;
int n,ans;
struct Node
{
	int f,l,r,x,num;
}a[N];

void add(int u,int v)
{
	a[u].num++;
	if(a[v].x<a[u].x)
		if(a[u].l==0){a[u].l=v; a[v].f=u;}
		else add(a[u].l,v);
	else
		if(a[u].r==0){a[u].r=v; a[v].f=u;}
		else add(a[u].r,v);
}

void init()
{
	int x;
	cin>>n;
	scanf("%d",&a[1].x);
	for(int i=1;i<=n;i++) a[i].num=1;
	for(int i=2;i<=n;i++)
	{
		scanf("%d",&a[i].x);
		add(1,i);
	}
}

void kill(int u,int z)
{
	int v=a[u].l;
	if(a[u].l==0 && a[u].r==0)
	{
		if(z==0) a[a[u].f].l=0;
			else a[a[u].f].r=0;
		return;
	}
	else if(a[u].l==0 && a[u].r!=0)
	{
		v=a[u].r;
		a[u].x=a[v].x;
		a[u].r=a[v].r;
		return;
	}
	else
	{
		while (a[v].r!=0){a[v].num--;v=a[v].r;}
		a[u].x=a[v].x;
		if(a[a[v].f].r==v) a[a[v].f].r=a[v].l;
		else a[a[v].f].l=a[v].l;
	}
}

void Delete(int u,int x)
{
	a[u].num--;
	if(a[u].x==x)
	{
		if(a[u].x<a[a[u].f].x) kill(u,0);
		else kill(u,1);
		return;
	}
	if(x<a[u].x) Delete(a[u].l,x);
	else Delete(a[u].r,x);
}

void find(int u,int k)
{
	if(k==a[a[u].l].num+1){ans=a[u].x; return;}
	else if(a[a[u].l].num+1<k) find(a[u].r,k-a[a[u].l].num-1);
	else find(a[u].l,k);
}

void out(int u)
{
	if(u==0) return;
	out(a[u].l);
	cout<<a[u].x<<' ';
	out(a[u].r);
}

int main()
{
	//freopen("bst.in","r",stdin);
	//freopen("bst.out","w",stdout);
	init();
	int x,k;
	cin>>x>>k;
	out(1);
	//cout<<endl;
	Delete(1,x);
	find(1,k);
	cout<<endl<<ans<<endl;
	out(1);
	cout<<endl;
	//for(int i=1;i<=n;i++)
	//	printf("%d %d %d %d %d\n",a[i].x,a[i].f,a[i].l,a[i].r,a[i].num);
	return 0;
}