C语言实现：二叉排序树结点的删除

Question

struct BSTree
{
int data;
struct BSTree *lchild;
struct BSTree *rchild;
};

若p为二叉排序树t中的一个叶子结点，如何在t中把p结点删除？？
t为BST的根结点，要求最后遍历t得到的树中不含p

我知道结点的删除在结构体中加一个struct BSTree *parents; 可以成功实现，但想知道如果没有定义指向双亲结点的指针，如何删除叶子节点？

Answer 1

void DeleTree(BTree T,int data)
{
BTree *p=T,*f=T,temp;
/寻找需要删除的点*/
while(*p)
{
if((*p)->key==data)
break;
else if(data>(*p)->key)

{
f=p;
(*p)=(*p)->rchild;
}
else if(data<(*p)->key)
{
f=p;
(*p)=(*p)->lchild;
}
}/*找到后,p为目标结点,f为其父结点*/

if(!(*p))                          //找不到
    printf("错误,无此数据");
//以下为找到的情况
else if( (*p)->lchild==NULL )      //情况1:p无左子树  
{
    if( (*f)->rchild=(*p) )        //p为f的右子树
        (*f)->rchild=(*p)->rchild; //直接将p的右子树连接在f的右子树上
    else if( (*f)->lchild=(*p) )   //p为f的左子树
        (*f)->lchild=(*p)->rchild; //直接将p的右子树连接在f的右子树上
    free(*p);
}
else if( (*p)->rchild==NULL )      //情况2:p无右子树
{
    if( (*f)->rchild=(*p) )        //p为f的右子树
        (*f)->rchild=(*p)->lchild; //直接将p的左子树连接在f的右子树上
    else if( (*f)->lchild=(*p) )   //p为f的左子树
        (*f)->lchild=(*p)->lchild; //直接将p的左子树连接在f的右子树上
    free(*p);
}
else if( (*p)->lchild==NULL && (*p)->rchild==NULL )//情况3:p无左子树和右子树
{
    if( (*f)->rchild=(*p) )                        //p为f的右子树
        (*f)->rchild=NULL;                         //f的右子树直接置空
    else if( (*f)->lchild=(*p) )                   //p为f的左子树    
        (*f)->lchild=NULL;                         //f的右子树直接置空
    free(*p);
}
else if( (*p)->lchild!=NULL && (*p)->rchild!=NULL )//情况4:p有左子树和右子树
{
    if( (*f)->rchild=(*p) )                        //p为f的右子树
    {
        temp=(*p)->lchild;                         //temp为p的左子树
        while(temp->rchild)                        //在temp的右支寻找空位
            temp=temp->lchild;
        temp->rchild=(*p)->rchild;                 //将p的右子树连接在temp的右子树上
        (*f)->rchild=(*p)->lchild;                 //再将p的左子树连接在f的左子树上
        free(*p);
    }
    else if( (*f)->lchild=(*p) )
    {
        temp=(*p)->lchild;
        while(temp->rchild)
            temp=temp->lchild;
        temp->rchild=(*p)->rchild;
        (*f)->lchild=(*p)->lchild;
        free(*p);       
    }
}