cccccran
2015-12-31 03:55
采纳率: 100%
浏览 1.8k
已采纳

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

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条回答 默认 最新

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

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

    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • CavanWang 2015-12-31 05:45

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

    评论
    解决 无用
    打赏 举报
  • CavanWang 2015-12-31 06:06

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

    评论
    解决 无用
    打赏 举报
  • 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;
    }
    }

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题