鱼C论坛

 找回密码
 立即注册
查看: 1768|回复: 8

[已解决]数据结构第七十五讲,顺序树的删除问题

[复制链接]
发表于 2018-9-8 11:58:52 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
  1. Status DeleteBST(BiTree *T, int key)
  2. {
  3.     if( !*T )
  4.     {
  5.         return FALSE;
  6.     }
  7.     else
  8.     {
  9.         if( key == (*T)->data )  //如果找到关键字  执行Delete
  10.         {
  11.             return Delete(T);
  12.         }
  13.         else if( key < (*T)->data )
  14.         {
  15.             return DeleteBST(&(*T)->lchild, key);
  16.         }
  17.         else
  18.         {
  19.             return DeleteBST(&(*T)->rchild, key);
  20.         }
  21.     }
  22. }

  23. Status Delete(BiTree *p)
  24. {
  25.     BiTree q, s;
  26.    
  27.     if( (*p)->rchild == NULL )   //如果没有右孩子
  28.     {
  29.         q = *p;                                        // 这一步,q *p是目标节点的地址
  30.         *p = (*p)->lchild;                //这一步,*p变成目标节点左孩子的地址,则代替目标点成为双亲的左孩子
  31.         free(q);                                //释放原来目标节点的地址
  32.     }
  33.     else if( (*p)->lchild == NULL )
  34.     {
  35.         q = *p;
  36.         *p = (*p)->rchild;
  37.         free(q);
  38.     }
  39.     else
  40.     {
  41.         q = *p;
  42.         s = (*p)->lchild;  //s=目标data节点的左孩子  左子树
  43.         
  44.         while( s->rchild )        //while 寻找目标节点左子树的最大值s   q是最大值data的双亲
  45.         {
  46.             q = s;                //s的双亲
  47.             s = s->rchild;
  48.         }
  49.         
  50.         (*p)->data = s->data;//目标点的data等于目标节点子树的最大data
  51.         
  52.         if( q != *p )//[color=Red]这里到free那里不是很懂。另外我的注释有错么?[/color]     
  53.         {
  54.             q->rchild = s->lchild;
  55.         }
  56.         else
  57.         {
  58.             q->lchild = s->lchild;
  59.         }
  60.         
  61.         free(s);
  62.     }
  63.    
  64.     return TRUE;
  65. }
复制代码




这儿没看懂


        if( q != *p )//
        {
            q->rchild = s->lchild;
        }
        else
        {
            q->lchild = s->lchild;
        }
最佳答案
2018-9-8 14:19:51
我是大甲鱼 发表于 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 是否有右孩子,一样进行维护。

最后释放叶子节点
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-9-8 13:11:38 | 显示全部楼层
前面的注释可以,但应该是用 q 把删除目标给复制一份,然后在删除目标只有单一孩子的情况下,让其孩子替代自己,才来删除。
40 多标注 //如果删除目标有两个孩子,寻找直接前驱。这里用的是左孩子的最大元素。

42、43 的作用?
45 能解释一下吗?为什么可以找到左子树的最大值?这样的注释你能理解?
47 你确定吗?
51 为什么要这样做?
先了解到这里
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-9-8 13:45:40 | 显示全部楼层
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是目标点左子树找到的最大值节点地址。合起来的意思就是,目标节点和左子树最大节点不是同一个点?这句不是很理解
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-8 14:19:51 | 显示全部楼层    本楼为最佳答案   
我是大甲鱼 发表于 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 是否有右孩子,一样进行维护。

最后释放叶子节点
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-9-8 15:02:27 | 显示全部楼层
claws0n 发表于 2018-9-8 14:19
42 不要看到【等于】就是备份(虽然系统内部确实是复制了一份),初始化而已,让 53 用。
43 换一个角度 ...

嗯 知道了 。华硕以前数据结构不是有经典面试题 部分吗 ,怎么没看到了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-8 15:10:58 | 显示全部楼层
我是大甲鱼 发表于 2018-9-8 15:02
嗯 知道了 。华硕以前数据结构不是有经典面试题 部分吗 ,怎么没看到了

不知道
论坛的就只有这些
https://fishc.com.cn/forum.php?mod=forumdisplay&fid=233&filter=typeid&typeid=336
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-9-8 15:27:27 | 显示全部楼层
claws0n 发表于 2018-9-8 15:10
不知道
论坛的就只有这些
https://fishc.com.cn/forum.php?mod=forumdisplay&fid=233&filter= ...

表示学数据结构很是痛苦,为什么面试要考这东西
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-9-8 15:48:30 | 显示全部楼层
我是大甲鱼 发表于 2018-9-8 15:27
表示学数据结构很是痛苦,为什么面试要考这东西

哥哥学得很痛苦吗?还有 24,加油
会数据结构感觉好像很牛逼、很厉害思考、很会解问题……么么
面试问这些,测试员工如何思考

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2018-9-8 16:41:12 | 显示全部楼层
claws0n 发表于 2018-9-8 15:48
哥哥学得很痛苦吗?还有 24,加油
会数据结构感觉好像很牛逼、很厉害思考、很会解问题……么么 ...

还有十二天,准备出去投简历了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 21:04

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表