二叉排序树的删除算法_二叉排序树的删除 代码_二叉排序树的删除(2)

{

if (!*T)//不存在和key相等的数据

{

return false;

}

else

{

if ((*T)->data == key)//找到和key相等的数据了，删除掉

return Delete(T);

else if ((*T)->data > key)

return DeleteTree(&(*T)->lchild, key);

else

{

return DeleteTree(&(*T)->rchild, key);

}

}

}

//删除操作的具体代码

//删除结点p，并重接它的左子树或者右子树

bool Delete(BTree *p)

{

BTree q, s;

if ((*p)->rchild == NULL)//右子树空就只需要重接它的左子树

{

q = *p; *p = (*p)->lchild; free(q);

}

else if ((*p)->lchild == NULL)//左子树空就只需要重接它的右子树

{

q = *p; *p = (*p)->rchild; free(q);

}

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;

}

//后面的删除代码可能有点理解不了...但是时间有限...有空我在详细修改一下...见谅

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-32406-2.html