AuthorChen
cccccran
采纳率100%
2015-12-31 03:55 阅读 1.7k
已采纳

数据结构排序二叉树的节点删除问题

2

void Delete(BiTree &b,int x){
if(!b)
return;
else{
if(x==b->data)
DeleteEle(b);
else if(x>b->data)
Delete(b->rightChild,x);
else
Delete(b->leftChild,x);
return ;
}
}
void DeleteEle(BiTree &b){
BiTree p,q,s;
if(!b->leftChild){
b=b->rightChild;
}
else if(!b->rightChild){
b=b->leftChild;
}
else{
q=b->leftChild;
if(!q->rightChild){
b=q;
}
else{
p=q->rightChild;
while(p->rightChild){
p=p->rightChild;
}
b->data=p->data;
//.................问题为下面这条语句。会导致错误答案
//为何?
p=p->leftChild;
}
}
return ;
}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

4条回答 默认 最新

  • 已采纳
    wangxugangzy05 CavanWang 2015-12-31 05:47

    你需要p 和另外一个可以保证随时指向p的父亲的指针 二者每次一块循环前行

    点赞 评论 复制链接分享
  • wangxugangzy05 CavanWang 2015-12-31 05:45

    是p的parent 指向p的leftChild 把p摘掉前,先把p的内容拷贝给b,然后p的parent指向p的leftChild,然后p就可以放心释放了

    点赞 评论 复制链接分享
  • wangxugangzy05 CavanWang 2015-12-31 06:06

    你的删除顶端元素也是个递归 就是“复制找到的子树的节点的data到顶端元素的data 然后重排找到的那个节点为根得子树(地柜调用)", 这个函数就是DeleteEle要做的

    点赞 评论 复制链接分享
  • wangxugangzy05 CavanWang 2015-12-31 07:07

    else{
    q=b->leftChild;
    if(!q->rightChild){
    b=q;
    }
    else{
    p=q->rightChild;
    while(p->rightChild){
    p=p->rightChild;
    }
    b->data=p->data;
    //.................问题为下面这条语句。会导致错误答案
    //为何?
    p=p->leftChild;
    }
    } 对以上代码的逻辑进行修改:

    else{
    if ( !b->leftChild->rightChild)
    {
    p = b->leftChild;
    b->data = p->leftChild;
    b->leftChild = p->leftChild;
    }else
    {
    p = b->leftChild;
    q = p->rightChild;
    while( q->rightChild)
    {
    p = q;
    q = q->rightChild;
    }
    b->data = q->data;
    p->rightChild = q->leftChild;
    }
    }

    点赞 评论 复制链接分享

相关推荐