对于这个题构造树的时候需要的比教的次数跟2n很接近，对于找第三个数来说没什么优势，如果是找地n个,n比较大的时候这才会有实际意义。

你说的是对的， 第三也许体现不出rank的优势。

我修改后的代码基本实现了。

#include<iostream>         
using namespace std;       
struct BiNode{             
    long key;              
    BiNode *pre;           
    BiNode *next;          
    BiNode(long n){ key =n ;pre=NULL; next=NULL;}
};                                               
class BiTree{                                    
private:                                         
    static int Rank;                             
    void BiTreeInsert(BiNode *&root,long n)      
        {                                        
            if( NULL == root)                    
            {                                    
                root= new BiNode(n);             
            }                                    
            else                                 
            {                                    
                if( root->key > n )              
                    BiTreeInsert(root->pre ,n);  
                if(root->key < n )               
                    BiTreeInsert(root->next,n);  
            }                                    
        }                                        
    void BiTreeRank(BiNode * root, int r , long & key ,bool & status)
        {                                                            
            if( NULL == root)                                        
            {                                                        
                return ;                                             
            }                                                        
            else                                                     
            {                                                        
                BiTreeRank( root->next, r , key, status);            
                Rank++;                                              
                if( Rank == r)                                       
                {                                                    
                    key=root->key;                                   
                    status =true;                                    
                }                                                    
                BiTreeRank( root->pre, r, key, status);              
            }                                                        
        }                                                            
    void BiTreeShow(BiNode * root )                                  
        {                                                            
            if(NULL == root)                                         
                return ;                                             
            BiTreeShow(root->pre);                                   
            cout<<root->key<<" ";                                    
            BiTreeShow(root->next);                                  
        }                                                            
    void BiTreeDestroy(BiNode *root){                                
        if( NULL == root)                                            
            return ;                                                 
        BiTreeDestroy(root->pre);                                    
        BiTreeDestroy(root->next);                                   
        delete root;                                                 
    }                                                                
public:                                                              
    BiNode *root;                                                    
    BiTree(){ root = NULL ;}                                         
    ~BiTree()                                                        
        {                                                            
            BiTreeDestroy(root);                                     
        }                                                            
    void insert(long n){ BiTreeInsert(root, n);}                     
    long rank(int r)                                                 
        {                                                            
            long k;                                                  
            bool sta=false;                                          
            Rank=0;                                                  
            BiTreeRank(root,r, k,sta);
            if( sta == true )
                return k;
            else
                return -1;
        }
    void show(){ BiTreeShow( root);}
};
int BiTree::Rank=0;
int main()
{
    int n;
    long key;
    while(cin>>n)
    {
        if ( 0 == n)
            break;
        BiTree *tree=new BiTree();
        for( int i=0;i<n;i++)
        {
            cin>>key;
            tree->insert(key);
        }

        //tree->show();
        //cout<<endl;
        int rank_key ;
        rank_key=tree->rank(3);
        if( rank_key == -1  )
            cout<<"NO such score!"<<endl;
        else
            cout<<rank_key<<endl;
    }
    return 0;
}

额。   太深奥了， 初学者。。

- -|||没人知道QuickSelect算法么……

选择

类似 快速排序， 比快速排序简单

两位能不能写代码密码，我没听说过那个Q S

快速选择和快排差不多，使用跟快排一样的方法把序列大于和小于参考值分成两部分，如果参考值前面有k个则选择前半部分作为新的序列，如果小于k个，选择后半部分作为新的序列，然后用同样的方法处理新序列（其实就是一个递归，跟快排的区别就是把其中一部分直接丢弃不处理），直到参考值刚好时第k个（即前面部分有k-1个）。这种方法在随机化的情况下大概要进行2n次比较，最坏的情况为n^2次比较。

对于k<=3的情况跟直接找需要的比较次数很接近甚至更大，而且编码相比直接找复杂，这时候没什么优势。

编码其实很简单，partition五行可以搞定，quickselect最多四行。

那就搞定他。

话说这题N久以前我就过了的吧……