还没有写删除操作，所以感觉实用性不大 操作含义如图所示
#include <cstdio> #include <iostream> using namespace std; int tot=1; int root=1; struct tree{ int val; int lt; int rt; int size; int fat; }; tree a[99999]; int num; void insert(int t,int v)//插入 { if(!t) return; if(v>a[t].val) { if(!a[t].rt) { a[++tot].val=v; a[tot].size=1; a[t].rt=tot; a[tot].fat=t; } else insert(a[t].rt,v); } else { if(!a[t].lt) { a[++tot].val=v; a[tot].size=1; a[t].lt=tot; a[tot].fat=t; } else insert(a[t].lt,v); } a[t].size=a[a[t].lt].size+a[a[t].rt].size+1; } int check1(int t,int k) { int b=0; while(1) { if(a[a[t].lt].size==k-(1+b)) break; if(a[a[t].lt].size>k-1) t=a[t].lt; else { b+=a[a[t].lt].size+1; t=a[t].rt; } } return a[t].val; } int check2(int t,int k) { int b=0; while(1) { if(a[t].val==k) break; if(a[t].val>k) t=a[t].lt; else { b+=a[a[t].lt].size+1; t=a[t].rt; } } return a[a[t].lt].size+1+b; } int check3(int t,int k) { int fat; while(1) { if(a[t].val==k) return a[t].val; if(a[t].val<k) { if(a[t].rt) fat=t,t=a[t].rt; else return a[fat].val; } if(a[t].val>k) { if(a[t].lt) fat=t,t=a[t].lt; else return a[t].val; } } } int main() { int n; scanf("%d",&n); int x,y; scanf("%d%d",&x,&y); a[1].val=y; a[1].size=1; for(int i=2;i<=n;i++) { scanf("%d%d",&x,&y); if(x==1) { insert(1,y); } if(x==3) { printf("%d\n",check1(1,y)); } if(x==4) { printf("%d\n",check2(1,y)); } if(x==5) { printf("%d\n",check3(1,y)); } if(x==6) { int k=check2(1,y); printf("%d\n",check1(1,k-1)); } if(x==7) { int k=check2(1,y); printf("%d\n",check1(1,k+1)); } } return 0; }