二叉排序树

BTree Search(BTree bt, keytype k)
{
    /*伪代码
    if(bt=NULL或bt->key=k)
    return bt;
    if(k>bt->key)
    return Search(bt->rchild,k)
    else 
    return Search(bt->lchild,k)
    */
    if (bt == NULL || bt->key == k)
        return bt;
    if (k > bt->key)
        return Search(bt->rchild, k);
    else
        return Search(bt->lchild, k);
}

int Insert(BTree &bt, keytype k)
{
    /*伪代码
    if(bt=NULL)
    {
       建立新节点bt;
       bt->key=k;
       bt左右孩子都为空;
     }
     if(bt->key=k)
     不需要插入，return 0;
     if(k>bt->key)
     return Insert(bt->rchild,k);
     if(k<bt->key)
     return Insert(bt->lchild,k);
      */
    if (bt == NULL)
    {
        bt = new BTNode;
        bt->key = k;
        bt->rchild = NULL;
        bt->lchild = NULL;
        return 1;
    }
    else if (k == bt->key)
        return 0;
    else if (k > bt->key)
        return Insert(bt->rchild, k);
    else
        return Insert(bt->lchild, k);
}

BTree Creat(int n)
{
    /*
    创建头指针,设为空;
    用循环依次输入、插入节点;
    return 根节点;
    */
    BTree bt = NULL;
    int i, x;
    for (i = 0; i < n; i++)
    {
        cin >> x;
        Insert(bt, x);
    }
    return bt;
}

int Delete1(BTree &bt,keytype k)
{
    /*伪代码
    if(bt为空)
    return 0;
    else if(k>bt->key) return Delete1(bt->rchild,k);
    else if(k<bt->key) return Delete1(bt->lchild,k);
    else {
       Delete2(bt);
       return 1;
     }
    */
    if (bt == NULL)
        return 0;
    if (k > bt->key)
        return Delete1(bt->rchild, k);
    if (k < bt->key)
        return Delete1(bt->lchild, k);
    if (k == bt->key)
    {
        Delete2(bt);
        return 1;
    }
}
void Delete2(BTree& bt)
{
    /*伪代码
    if(bt->rchild和bt->lchild都为空)
        free(bt);
    if(bt->rchild为空)
    {
       将它父亲的左孩子指向它的左孩子;
       free(bt);
    }
    if(bt->lchild为空)
    { 
       将它父亲的右孩子指向它的右孩子;
       free(bt);
    }
    */
    BTree p;
    if (bt->rchild == NULL && bt->lchild == NULL)
        free(bt);
    if (bt->rchild == NULL)
    {
        p = bt;
        bt = bt->lchild;
        free(p);
    }
    if (bt->lchild == NULL)
    {
        p = bt;
        bt = bt->rchild;
        free(p);
    }
    if (bt->lchild != NULL && bt->rchild != NULL)
        Delete3(bt, bt->lchild);
}
void Delete3(BTree& bt,BTree& t)
{
    /*伪代码
    if(t->rchild不为空) Delete3(bt,t->rchild);
    else {
    将t->key赋给bt;
    free(bt);
    }
    */
    BTree p;
    if (t->rchild != NULL)
        Delete3(bt, t->rchild);
    else {
        bt->key = t->key;
        p = t;
        t = t->lchild;
        free(p);
    }
}