马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
Status DeleteBST(BiTree *T, int key)
{
if( !*T )
{
return FALSE;
}
else
{
if( key == (*T)->data ) //如果找到关键字 执行Delete
{
return Delete(T);
}
else if( key < (*T)->data )
{
return DeleteBST(&(*T)->lchild, key);
}
else
{
return DeleteBST(&(*T)->rchild, key);
}
}
}
Status Delete(BiTree *p)
{
BiTree q, s;
if( (*p)->rchild == NULL ) //如果没有右孩子
{
q = *p; // 这一步，q *p是目标节点的地址
*p = (*p)->lchild; //这一步，*p变成目标节点左孩子的地址，则代替目标点成为双亲的左孩子
free(q); //释放原来目标节点的地址
}
else if( (*p)->lchild == NULL )
{
q = *p;
*p = (*p)->rchild;
free(q);
}
else
{
q = *p;
s = (*p)->lchild; //s=目标data节点的左孩子 左子树
while( s->rchild ) //while 寻找目标节点左子树的最大值s q是最大值data的双亲
{
q = s; //s的双亲
s = s->rchild;
}
(*p)->data = s->data;//目标点的data等于目标节点子树的最大data
if( q != *p )//这里到free那里不是很懂。另外我的注释有错么？
{
q->rchild = s->lchild;
}
else
{
q->lchild = s->lchild;
}
free(s);
}
return TRUE;
}
这儿没看懂
if( q != *p )//
{
q->rchild = s->lchild;
}
else
{
q->lchild = s->lchild;
}
42 不要看到【等于】就是备份（虽然系统内部确实是复制了一份），初始化而已，让 53 用。
43 换一个角度，s 是 p 的左孩子，有时候需要，有时候不需要，只是用指来指去的，会有盲点，个人看法。
45 这是一个循环，应该是【找到叶子节点】
47 循环体内部，所以应该把循环条件也说一下。s 的右孩子不为空的情况下，q 指向了 s，然后 s 指向了自己的右孩子。当找到叶子节点，即待删除目标的直接前驱，跳出循环。
51 将待删除目标的资料覆盖为它的直接前驱的资料 -> 62 删除直接前驱。
在特殊情况下，45 失败了，即 p 的左孩子（s）没有右孩子。此时 q == *p。因为被删除的是 s 。所以把 s 的左孩子给了 q ，即给 p。
如果 45 成功，q != *p，但是要检查 s 是否有右孩子，一样进行维护。
最后释放叶子节点
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2018-9-8 11:58:52
置顶卡
千斤顶
显身卡
发表于 2018-9-8 13:11:38
楼主
还有十二天，准备出去投简历了