免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
查看: 1375 | 回复: 0
打印 上一主题 下一主题

[算法] 算法求助! [复制链接]

论坛徽章:
1
荣誉版主
日期:2011-11-23 16:44:17
1 [报告]
发表于 2003-04-14 12:50 |显示全部楼层

算法求助!

void delnote(bstree *bt,bstree p,bstree q) // q 是p的父结点,p是要 删结点
{
bstree s,r;

if(p->;lchild == NULL) //左子树为空
{
if(p == *bt) //不是用形参给出p的父接点了吗?怎么还要判断?思路不清晰。
*bt = p->;rchild;
                 
else if (q->;lchild == p )
q->;lchild = p->;rchild;
else
q->;rchild = p->;rchild;

}

else if (p->;rchild == NULL) //右子树为空
{
if(p == *bt)
*bt = p->;lchild;

else if(q->;lchild == p)
q->;lchild = p->;lchild;

else
q->;rchild = p->;lchild;

}
else <----- 因该是这里错了
{
        s = p;
        r = s->;rchild;
        while(r->;lchild != NULL) //找最左结点 *r,*s是 *r的父结点
        {
                s =r;
                r = r->;lchild;
        }
        r->;lchild = p->;lchild;
        if(p!=s)
        {
                r->;lchild = p->;lchild; //同上面的语句重复。
                r->;rchild = p->;rchild;
        }
        if(p == *bt)
                *bt = r;  //此处应该删除原先r的父接点指向r的指针。否则会多出这样一条线。

        else if(q->;lchild== p) //删除的是q的左孩子
                q->;lchild =r;  //这里p的右子树怎么办?被整个砍下去了。

        else
                q->;rchild = r; //删除的是q的右孩子
                               //同样,p的左子树呢?
}
free(p);
}

问题写在上面的注释里了。
应该去找本数据结构的书好好看看。p删除后,p的左右子树不同的安排方法应该有不同的删除方法。
还有,写程序应该有一定的缩进,有层次感以增加程序的可读性。
前面,p只有一个子树的时候,删除写得不错。p有两个子树的时候就糊涂了,在“画图”里画一画就明白了。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP