Status Delete(BiTree *p)
{
BiTree q,s;
/*情况二：删除结点p的右子树或左子树为空*/
if((*p)->lchild==NULL) //a.右子树空则只需重接它的左子树
{
q=*p; *p=(*p)->lchild; free(q);
}
else if((*p)->rchild==NULL) //b.只需重接它的右子树
{
q=*p; *p=(*p)->rchild; free(q); //将指针p指向的结点
}
//情况三：左右子树均不为空
else
{
q=*p; s=(*p)->lchild;
while(s->rchild) //转左，然后向右到尽头(找待删结点的前驱)
{
q=s; s=s->rchild;
}
(*p)->data=s->data; //s指向被删结点的直接前驱
if(q!=*p)
q->rchild=s->lchild; //重接q的右子树
else
q->lchild=s->lchild; //重接q的左子树
free(s);
}
return TRUE;
}
源码分析： q=*p; *p=(*p)->rchild; free(q); 作用：将指针p指向的结点赋值给新结点q，并使p指针指向的左结点，即实现了重接右子树，再释放结点q.
三、二叉排序树总结 二叉排序树是以链接的方式存储，保持了链接存储结构在执行插入或删除操作时不用移动元素的优点，只要找到合适的插入和删除位置后，仅需修改链接指针即可。插入删除的时间性能比较好，而对于二叉排序树的查找，走的就是从根结点到要查找的结点的路径，其比较次数等于给定值的结点在二叉排序树的层数。极端情况，最少为1次，即跟结点就是要找的结点，最多也不会超过树的深度，即二叉排序树的查找性能取决于二叉排序树的形状。
|