从BST删除节点时出错

Question

当我通过GPS移除一个节点时，当我试图打印二叉树时，会出现堆栈溢出。下面是我的一些代码。我不能理解它将如何工作良好，如果我删除的名称，但不是，如果我删除的坐标，因为我正在使用相同的删除方法。

我得到的确切错误是“Exe:0xC00000FD中0x013214D6处的未处理异常：堆栈溢出（参数：0x00000001,0x00152FFC）”。在按坐标删除后，在打印函数中会出现这种情况，但如果按名称删除，则不会出现这种情况。

bool BinaryTree::DeleteByName(string city)
{
    if (GetRoot() != NULL)
    {
        return (DeleteByName(GetRoot(), city));
    }
    return false;
}

TreeNode* BinaryTree::DeleteByName(TreeNode *node, string city)
{
    if (node == NULL)
    {
        return node;
    }
    else if (city < node->Data.name)
    {
        node->Left = DeleteByName(node->Left, city);
    }
    else if (city > node->Data.name)
    {
        node->Right = DeleteByName(node->Right, city);
    }
    else
    {
        if (node->Left == NULL && node->Right == NULL)
        {
            delete node;
            node = NULL;
        }
        else if (node->Left == NULL)        
        {
            TreeNode* temp = node;
            node = node->Right;
            delete temp;
        }
        else if (node->Right == NULL)
        {
            TreeNode* temp = node;
            node = node->Left;
            delete temp;
        }
        else
        {
            cout << "Else";
            TreeNode* temp = MinPtr(node->Right);
            node->Data = temp->Data;
            node->Right = DeleteByName(node->Right, temp->Data.name);
        }
    }
    return node;
}

bool BinaryTree::DeleteByCoord(pair<double, double> coords)
{
    if (GetRoot() == NULL)
    {
        return false;
    }
    else
    {
        return DeleteByCoord(GetRoot(), coords);
    }
}

bool BinaryTree::DeleteByCoord(TreeNode* node, pair<double, double> coords)
{
    bool result;

    if (node == NULL)
    {
        return false;
    }
    else
    {
        if (node->Data.coordinates.first == coords.first && node->Data.coordinates.second == coords.second)
        {
            return (DeleteByName(node, node->Data.name));           
        }

        result = DeleteByCoord(node->Left, coords);
        if (result == true)
        {
            return result;
        }

        return DeleteByCoord(node->Right, coords);
    }
}




void BinaryTree::Insert(City city)
{
    TreeNode* temp = new TreeNode(city);
    if (GetRoot() == NULL)
    {
        root = temp;
    }
    else
    {
        Insert(temp, GetRoot());
    }
}

void BinaryTree::Insert(TreeNode* toAdd, TreeNode* addHere)
{
    if (toAdd->Data < addHere->Data)
    {
        if (addHere->Left != NULL)
        {
            Insert(toAdd, addHere->Left); 
        }
        else
        {
            addHere->Left = toAdd;
        }
    }
    else if (toAdd->Data > addHere->Data)
    {
        if (addHere->Right != NULL)
        {
            Insert(toAdd, addHere->Right);
        }
        else
        {
            addHere->Right = toAdd;
        }
    }
}

void BinaryTree::InOrderTraversal(TreeNode* node)
{
    if (node != NULL)
    {
        InOrderTraversal(node->Left);
        cout << node->Data << endl;
        InOrderTraversal(node->Right);
    }
}

void BinaryTree::InOrderTraversal()
{
    InOrderTraversal(GetRoot());
}

TreeNode* BinaryTree::GetRoot()
{
    return root;
}

TreeNode* BinaryTree::MinPtr(TreeNode* node)
{
    while (node->Left != NULL)
    {
        node = node->Left;
    }   
    return node;
}

Answer 1

删除节点时，还需要更新指向已删除节点的父指针。注意这里：

当您直接调用DeleteByName时，它搜索所需节点并返回空指针，该空指针自动设置为父节点指针：

else if (city < node->Data.name)
{
    node->Left = DeleteByName(node->Left, city);
}
else if (city > node->Data.name)
{
    node->Right = DeleteByName(node->Right, city);
}

但从坐标方法调用DeleteByName时，不会重置父级的左/右指针：

if (node->Data.coordinates.first == coords.first && node->Data.coordinates.second == coords.second)
{
    return (DeleteByName(node, node->Data.name));           
}

else
{
    if (node->Left == NULL && node->Right == NULL)
    {
        delete node;
        node = NULL;
    }
    //... same here
}

null