我的想法也是先对auxilary排序，然后线性的构造树，在然后遍历输出。
可是超时了，那位帮忙看看吧。
import java.io.*;
import java.util.*;
public class Main
{
	public static void main(String [] args)throws Exception
	{
		System.out.println("YES");
		Scanner cin=new Scanner(System.in);
		int n=cin.nextInt();
		KA [] input=new KA[n];
		KA [] output=new KA[n];
		for(int i=1;i<=n;i++)
		{
			input[i-1]=new KA(i,cin.nextInt(),cin.nextInt());
		}
		Arrays.sort(input);
		KATree kaTree=new KATree(input[0]);
		KATree.output=output;
		for(int i=1;i<n;i++)
			kaTree.add(input[i]);
			
		kaTree.pre();
		
		for(int i=0;i<n;i++)
		{
			if(output[i].parent==null)
				System.out.print(0);
			else
				System.out.print(output[i].parent.index);
			System.out.print(" ");
			
			if(output[i].left==null)
				System.out.print(0);
			else
				System.out.print(output[i].left.index);
			System.out.print(" ");
			
			if(output[i].right==null)
				System.out.print(0);
			else
				System.out.print(output[i].right.index);
			System.out.println();
		}

	}
}
class KATree
{
	public static KA [] output;
	private static int flag=0;
	KA root=null;
	public KATree(KA root)
	{
		this.root=root;
	}
	public void add(KA t)
	{
		KA p=root,pf=root;
		while(p!=null)
		{
			pf=p;
			if(t.key>p.key)			
				p=pf.right;
			else
				p=pf.left;
		}
		if(t.key>pf.key)
			pf.right=t;
		else
			pf.left=t;
		t.parent=pf;
	}
	public void pre()
	{
		preprint(root);
	}
	private void preprint(KA node)
	{
		if(node!=null)
		{
			output[node.index-1]=node;
			preprint(node.left);
			preprint(node.right);
		}
	}
}
class KA implements java.lang.Comparable
{
	public int index;
	public int key;
	public int auk;
	public KA left=null;
	public KA right=null;
	public KA parent=null;
	public KA(int c,int a,int b)
	{
		index=c;
		key=a;
		auk=b;
	}
	public int compareTo(Object o)
	{
		KA t=(KA)o;
		if(auk<t.auk)return -1;
		if(auk>t.auk)return 1;
		return 0;
	}
	public String toString()
	{
		return "["+index+" "+key+" "+auk+"]";
	}

}

• ft,弄反了吧？是按k排序啊，建树的时候才需要用到aux (2296) frkstyc 2005-05-12 22:30:50