void InsertBST(BiNode<int> *&r, BiNode<int>*s)
{
if ( r == NULL)
r = s;
else if (s->data<r->data )
InsertBST(r->lch, s);
else
InsertBST(r->rch, s);
}
void Create(BiNode<int> *&R, int r[], int n)
{
for (int i=0; i<n; i++)
{
BiNode<int> * s = new BiNode<int> ;
s->data = r[i];
s->lch = s->rch = NULL;
InsertBST(R, s);
}
}
template <class T> void Delete(BiNode<T> *&R)
{
BiNode<T> *q,*s;
if(R->lch==NULL)
{
q=R; R=R->rch; delete q;
}
else if (R->rch==NULL)
{
q=R; R=R->lch; delete q;
}
else
{
q = R;
s = R->lch; //s是R的前驱， q是s的双亲
while(s->rch!=NULL)
{
q = s; s = s->rch;
}
R->data = s->data;
if(q!=R)
q->rch = s->lch;
else
R->lch = s->lch; //q=R表示s为R的左孩子
delete s;
}
}
