http://blog.csdn.net/arcsinsin/article/details/10238505
假设被删结点是*p,其双亲是*f,不失一般性,设*p是*f的左孩子,下面分三种情况讨论:
⑴ 若结点*p是叶子结点,则只需修改其双亲结点*f的指针即可。
⑵ 若结点*p只有左子树PL或者只有右子树PR,则只要使PL或PR 成为其双亲结点的左子树即可。
⑶ 若结点*p的左、右子树均非空,先找到*p的中序前趋结点*s(注意*s是*p的左子树中的最右下的结点,它的右链域为空),然后有两种做法:
① 令*p的左子树直接链到*p的双亲结点*f的左链上,而*p的右子树链到*p的中序前趋结点*s的右链上。
② 以*p的中序前趋结点*s代替*p(即把*s的数据复制到*p中),将*s的左子树链到*s的双亲结点*q的左(或右)链上。(在下面的演示算法中用的就是此方法)
//删除二叉排序树中的一个节点 //在二叉排序树T中删除关键字为key的结点 void DelBST(BTree *T,int key){ BTree *p=T,*f,*q,*s,*root=T; while(p){ if(p->data==key) break; //找到关键字为key的结点 f=p;//记下关键字key节点的父节点 p=(key<p->data)?p->lchild:p->rchild;//分别在*p的左、右子树中查找 } if(!p) return;//二叉排序树中无关键字为key的结点 if(p->lchild==NULL&&p->rchild==NULL){//p没有左右子树 if(p==T) T=NULL;//删除的是根节点 else if(p==f->lchild) f->lchild=NULL; else f->rchild=NULL; free(p); } else if(p->lchild==NULL&&p->rchild!=NULL)//p无左子树有右子树 { if(f->lchild==p) f->lchild=p->rchild; //将p的右子树链接到其父结点的左链上 else f->rchild=p->rchild; //将p的右子树链接到其父结点的右链上 free(p); } else if(p->rchild==NULL&&p->lchild!=NULL)//p有左子树无右子树 { if (f->lchild==p) f->lchild=p->lchild; //将p的左子树链接到其父结点的左链上 else f->rchild=p->lchild; //将p的左子树链接到其父结点的右链上 free(p); } else if(p->lchild!=NULL&&p->rchild!=NULL)//p既有左子树又有右子树 { q=p; s=p->lchild;//转左 while(s->rchild){//然后向右到尽头 q=s; s=s->rchild;//s指向被删节点的“前驱”(中序前驱) } p->data=s->data;//以p的中序前趋结点s代替p(即把s的数据复制到p中) if(q!=p) q->rchild=s->lchild;//重接q的右子树 else q->lchild=s->lchild;//重接q的左子树。 free(s); } }