二叉搜索樹的隨機化建立方法
二叉搜索數(shù)是一棵二叉樹，其中每一個內(nèi)部節(jié)點都有一個相關(guān)的關(guān)鍵字，并有負有以下的性質(zhì)。任意節(jié)點的關(guān)鍵字大于（或者等于）該節(jié)點左子樹的所有關(guān)鍵字，并小于（或者等于）該節(jié)點右子樹的所有關(guān)鍵字。
#include <stdlib.h>
#include <iostream.h>
static int maxKey = 1000;
typedef int Key;
class Item{
private:
Key keyval;
float info;
public:
Item()
{keyvalue = maxKey;}
Key key()
{return keyvalue;}
int null()
{
return keyvalue ==maxKey;
}
void rand()
{
keyval = 1000*::rand()/RAND_MAX;
}
int scan(istream& is=cin)
{
return(is>>keyvalue>>info )!=0);
}
void show(ostream& os=cout)
{
os<<keyvalue<<" "<<info<<endl;
}
};
ostream& operator<<(ostream &os,Item &X)
{
X.show(os);
return os;
}
template <class Item,class Key>
class ST
{
private:
struct node
{
Item item;
node *l,*r;
node(Item x)
{
item = x;
l = 0;
r = 0;
}
};
typedef node * link;
link head;
struct node nullitem;
void insertR(link &h,Item x)
{
if(h == 0)
{
h = new node(x);
return;
}
if(x.key()<h->item.key())
{
insertR(h->l,x);
}
else
{
insertR(h->r,x);
}
}
Item searchR(link &h,Key v)
{
if(h == 0)
return nullitem;
if(h->item.key() == v)
{
return h->Item;
}
else if(h->item.key()<v)
{
searchR(h->right,v);
}
else
{
searchR(h->left,v);
}
}
}
public:
ST(int)
{
}
int count();
Item search(Key);
void insert(Item);
void remove(Item);
Item select(int);
void show(ostream &);
};