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 ;
}
你需要p 和另外一个可以保证随时指向p的父亲的指针 二者每次一块循环前行
是p的parent 指向p的leftChild 把p摘掉前，先把p的内容拷贝给b，然后p的parent指向p的leftChild，然后p就可以放心释放了
你的删除顶端元素也是个递归 就是“复制找到的子树的节点的data到顶端元素的data 然后重排找到的那个节点为根得子树（地柜调用)"， 这个函数就是DeleteEle要做的
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;
}
}