关于P5076这道题，我仔细分析了《深入浅出》书上给出的代码及讲解，发现了一些错误，洛谷的测试数据也有问题。书上的代码可以AC本题，但是与题意不符。

1、查询x的排名，题意为：“排名为比当前的数小的数的个数+1，如有多个相同的数，应输出最小的排名”。假设二叉树中有1 1 4 6 7这5个数，如果查询1的排名应输出1，但是按照书中的程序运行后输出2。

这是由rank函数最后一句决定的：

return a[a[root].left].size+a[root].num;

我认为这里应该改为：return a[a[root].l].size+1;

2、求 x的前驱，题意为：“（前驱定义为小于 x，且最大的数）。若未找到则输出-2147483647。” 还是上面那组样例，如果查1的前驱应输出-2147483647，但是书中的程序运行后无输出。 我认为应该在kth函数中第一行加这么一句：

if(x<1) return -2147483647;

3、书上231页第11行查询后继时不能输出rank+1的数，还是上面那组样例，如果查2的后继应输出4，2排名是3，排名rank+1的数即排第4的数，会输出6。事实上，2的后继应是排名第3。虽然书中讲解有误，但程序是正确的。

else if(opt==4) cout<<rankx(rank(x+1,root),root)<<endl;

通过查找x+1的排名p，再输出排名为p的数，才是x的后继。 下面给出我认为正确的程序：

#include<iostream>
#include<cstdio>
using namespace std;

int n,sum;//sum是二叉搜索树结点编号 

struct node{
	int l,r,val,size,cnt;
}a[10005];

int rank(int x,int root)//查询x的排名
{
	if(root==0) return 1;
	if(x<a[root].val)//去左子树找 
		return rank(x,a[root].l);
	else if(x>a[root].val)//去右子树找
		return a[root].cnt+a[a[root].l].size+rank(x,a[root].r);
	else
		return a[a[root].l].size+1;
}

int rankx(int x,int root)//查询排名为x的数
{
	if(x<1)
		return -2147483647;
	if(x>a[1].size)
		return 2147483647;
	if(x<=a[a[root].l].size)//在左子树中 
		return rankx(x,a[root].l);
	else if(x<=a[a[root].l].size+a[root].cnt)
	//是根
		return a[root].val;
	else//在右子树中 
		return rankx(x-a[a[root].l].size-a[root].cnt,a[root].r);
}

void insert(int x,int root)//插入一个数x
{
	if(x<a[root].val)//插到左子树 
	{
		if(a[root].l==0)//左儿子不存在 
		{
			a[root].l=++sum;
			a[sum].val=x;
			a[sum].l=0;
			a[sum].r=0;
			a[sum].size=1;
			a[sum].cnt=1;
		}
		else//左儿子存在
			insert(x,a[root].l);
	}
	else if(x>a[root].val)
	{
		if(a[root].r==0)//右儿子不存在 
		{
			a[root].r=++sum;
			a[sum].val=x;
			a[sum].l=0;
			a[sum].r=0;
			a[sum].size=1;
			a[sum].cnt=1;
		}
		else//右儿子存在
			insert(x,a[root].r);
	}
	else//x是根结点，cnt+1 
		a[root].cnt++;
	a[root].size++;
}

int main()
{
//	freopen("b2.in","r",stdin);	
//	freopen("a.out","w",stdout);	
	int opt,x;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d",&opt,&x);
		switch(opt)
		{
			case 1://查询x的排名
				printf("%d\n",rank(x,1));break;
			case 2://查询排名为x的数
				printf("%d\n",rankx(x,1));break;
			case 3://求x的前驱
				printf("%d\n",rankx(rank(x,1)-1,1));break;
			case 4://求x的后继
				printf("%d\n",rankx(rank(x+1,1),1));break;
			case 5://插入一个数x
				if(sum==0)
				{
					sum++;
					a[sum].l=0;
					a[sum].r=0;
					a[sum].val=x;
					a[sum].cnt=1;
					a[sum].size=1;						
				}
				else	
					insert(x,1);
		}
	}
	return 0;
}