数据用的是P1801的样例，函数 in_ 用来插入，函数 cout_ 为中序遍历寻找第i小的数并输出 贴代码

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

typedef struct mmm *position_;
typedef position_ tree;

int i,j,m,n,a;
struct mmm{
	long data_;
	tree left_;
	tree right_;
};
tree tree_all;
////
tree in_( tree tree_in, int x)
{
	cout<<"in"<<" ";
	if(!tree_in)
	{
		tree_in = new mmm;
		tree_in->data_ = x;
		tree_in->left_ = NULL;
		tree_in->right_ = NULL;
	}
	else
	{
		if( x> tree_in->data_)
		{
			in_ ( tree_in->right_, x);
		}
		if( x< tree_in->data_)
		{
			in_ ( tree_in->left_, x);
		}
	}
	return 0;
}
////
tree cout_(tree tree_in ,int x)
{
	cout<<"cout"<<" ";
	if(tree_in->left_)
	{
		cout_ ( tree_in->left_, x);
	}
	a+=1;
	if(a>=x)
	{
		if(a==x) cout<<tree_in->data_<<endl;
		return 0;
	}
	if(tree_in->right_ )
	{
		cout_ ( tree_in->right_, x);
	}
	return 0;
}
////
int main(){
	cin>>m>>n;
	int x[m+1],y[n+1];
	////
	for(i=0;i<m;i++)
	{
		cin>>x[i];
	}
	for(i=0;i<n;i++)
	{
		y[i]=0;
	}
	for(i=0;i<n;i++)
	{
		cin>>j;
		y[j]+=1;
	}
	////
	j=1;
	for(i=0;i<m;i++)
	{
		in_ ( tree_all, x[i]);
		if(y[i])
		{
			while(y[i]!=0)
			{
				cout_( tree_all, ++j);
				y[i]-=1;
				a=0;
			}
		}
	}
	return 0;
}

贴结果

in in cout