0

我正在尝试创建一个函数来从二叉搜索树中删除一个节点。我得到了第三种情况，节点有 2 个孩子在工作，但我的代码不起作用，因为节点有 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;
}
4

1 回答 1

0

您确定您的代码与 2 个孩子完美配合吗？因为您提供的上述代码段仅处理 3 种情况：（1）没有孩子，（2）左 ptr 指向的 1 个孩子，（3）右 ptr 指向的 1 个孩子...最后一种情况，有 2 个孩子, 根本不存在...

因此，回答您的问题：是的，您提供的上述代码似乎是错误的（又名不完整）。

我设法找到了你使用的东西的来源。您在上面显示的函数中是否有以下代码（附加在您的流之后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
于 2012-04-29T02:31:14.023 回答