//困扰了我很久！ 这个程序在G++和VS.Net 2005下结果分别为3和-1！ 

#include <iostream>
#include <conio.h>
using namespace std;
const int MAXN = 200001;

///////////  binary searh tree
typedef struct{
    int b,e,c;
    int left,right;
}Node;

int idx;
Node bst[2*MAXN];

void make_bst(int _lower,int _upper)
{
    ++idx;
    int v=idx;
    bst[v].b=_lower;
    bst[v].e=_upper;
    bst[v].c=0;
    if(_upper-_lower>=1){
        bst[v].left=idx+1;
        make_bst(_lower,(_lower+_upper)/2);
        bst[v].right=idx+1;
        make_bst((_lower+_upper)/2+1,_upper);
    }
}

void insert_bst(int _root,int _value)
{
    ++bst[_root].c;
    if(bst[_root].b==bst[_root].e)return;
    if(_value>=bst[bst[_root].left].b && _value<=bst[bst[_root].left].e)
        insert_bst(bst[_root].left,_value);
    else insert_bst(bst[_root].right,_value);
}

void delete_bst(int _root,int _value)
{
    --bst[_root].c;
    if(bst[_root].b==bst[_root].e)return;
    if(_value>=bst[bst[_root].left].b && _value<=bst[bst[_root].left].e)
        delete_bst(bst[_root].left,_value);
    else delete_bst(bst[_root].right,_value);
}

int find_bst(int _root,int k)
{
    if(bst[_root].b==bst[_root].e){
        if(k<=bst[_root].c) return bst[_root].b;
        else { puts("cannot find"); return -1; }
    }
    if(k<=bst[bst[_root].right].c)find_bst(bst[_root].right,k);
    else find_bst(bst[_root].left,k-bst[bst[_root].right].c);   
    /// return -1;   加上这样一句，结果就正确了，但是该函数显然在puts("cannot find")那里就返回了 
}

int main()
{
idx=0; make_bst(1,8);
insert_bst(1,3);
insert_bst(1,3);
cout<<find_bst(1,3)<<endl;
}

• 自己昏了...当我没说过 (1760) Renegade 2006-08-30 01:16:23