数据结构第七十五讲，顺序树的删除问题
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;
} 前面的注释可以，但应该是用 q 把删除目标给复制一份，然后在删除目标只有单一孩子的情况下，让其孩子替代自己，才来删除。
40 多标注 //如果删除目标有两个孩子，寻找直接前驱。这里用的是左孩子的最大元素。
42、43 的作用？
45 能解释一下吗？为什么可以找到左子树的最大值？这样的注释你能理解？
47 你确定吗？
51 为什么要这样做？
先了解到这里 claws0n 发表于 2018-9-8 13:11
前面的注释可以，但应该是用 q 把删除目标给复制一份，然后在删除目标只有单一孩子的情况下，让其孩子替代 ...
42 的作用是将目标节点备份
43 的作用是让s指向目标节点的左孩子，然后以这个左孩子做root，一直往右边寻找最大值
45一直往右遍历寻找最大值
47 当s等于最大值的时候把s备份到q，然后s->rchild==null就开始跳出循环
51 的作用就是把在目标点的左子树找到的最大值赋值给这个目标点，就相当于把这个目标点的data删除了
53 的意思是什么？ *p是目标节点的地址，从else到这里一直没变过，p是目标点左子树找到的最大值节点地址。合起来的意思就是，目标节点和左子树最大节点不是同一个点？这句不是很理解 我是大甲鱼 发表于 2018-9-8 13:45
42 的作用是将目标节点备份
43 的作用是让s指向目标节点的左孩子，然后以这个左孩子做root，一直往右边 ...
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 是否有右孩子，一样进行维护。
最后释放叶子节点 claws0n 发表于 2018-9-8 14:19
42 不要看到【等于】就是备份（虽然系统内部确实是复制了一份），初始化而已，让 53 用。
43 换一个角度 ...
嗯 知道了 。华硕以前数据结构不是有经典面试题 部分吗 ，怎么没看到了 我是大甲鱼 发表于 2018-9-8 15:02
嗯 知道了 。华硕以前数据结构不是有经典面试题 部分吗 ，怎么没看到了
不知道 {:5_96:}
论坛的就只有这些
https://fishc.com.cn/forum.php?mod=forumdisplay&fid=233&filter=typeid&typeid=336 claws0n 发表于 2018-9-8 15:10
不知道
论坛的就只有这些
https://fishc.com.cn/forum.php?mod=forumdisplay&fid=233&filter= ...
表示学数据结构很是痛苦，为什么面试要考这东西 我是大甲鱼 发表于 2018-9-8 15:27
表示学数据结构很是痛苦，为什么面试要考这东西
哥哥学得很痛苦吗？还有 24，加油{:5_108:}
会数据结构感觉好像很牛逼、很厉害思考、很会解问题……么么
面试问这些，测试员工如何思考{:9_227:}
claws0n 发表于 2018-9-8 15:48
哥哥学得很痛苦吗？还有 24，加油
会数据结构感觉好像很牛逼、很厉害思考、很会解问题……么么 ...
{:10_266:}还有十二天，准备出去投简历了
页:
[1]