从二叉查找树中删除节点

Question

我正在尝试创建一个从二叉查找树中删除节点的函数。我得到了第三种情况，节点有两个孩子在工作，但是我的代码不工作，节点有1个孩子或没有孩子。

这是我从书中直接复制的代码。我从书中得到的这段代码是否错误？

template <class elemType> 
void bSearchTreeType<elemType>::deleteFromTree 
(nodeType<elemType>* &p) 
{ 
nodeType<elemType> *current; //pointer to traverse the tree 
nodeType<elemType> *trailCurrent; //pointer behind current 
nodeType<elemType> *temp; //pointer to delete the node 
if (p == NULL) 
cout << "Error: The node to be deleted is NULL." 
<< endl; 
else if (p->lLink == NULL && p->rLink == NULL) 
{ 
temp = p; 
p = NULL; 
delete temp; 
} 
else if (p->lLink == NULL) 
{ 
temp = p; 
p = temp->rLink; 
delete temp; 
} 
else if (p->rLink == NULL) 
{ 
temp = p; 
p = temp->lLink; 
delete temp; 
} 

Answer 1

您确定您的代码与2个孩子完美合作吗？因为你提供的上述片段只需要处理3个案例：（1）没有孩子，（2）有一个孩子指着左边，（3）有一个孩子指着右边......最后一个案例，有两个孩子，根本不存在...

所以要回答你的问题：是的，上面的代码，如你所提供的，似乎是错误的（又称不完整）。

我设法追查你正在使用的来源。你在上面显示的函数中有下面的代码（在你的流else if之后附加）还是缺失？

else 
{ 
    current = p->llink; 
    trailCurrent = NULL; 

    while(current->rlink != NULL) 
    { 
     trailCurrent = current; 
     current = current->rlink; 
    } //end while 

    p->info = current->info; 

    if(trailCurrent == NULL) //current did not move; 
          //current == p->llink; adjust p 
     p->llink = current->llink; 
    else 
     trailCurrent->rlink = current->llink; 

    delete current; 
}//end else