c++ - 删除二叉搜索树的根节点

Question

我有这个功能可以删除二叉搜索树中的一个节点，除了我要求它删除根节点的情况外，它似乎可以正常工作。它应该取左边最右边的值并用它替换节点；然而，一旦发生这种情况，新根节点的子节点指针似乎并不指向原始根节点的子节点。代码如下:

bool delete_node(Node*& root, TYPE data) {
Node* toDelete;
Node* parent;

// This function is defined appropriately elsewhere, and finds the target to be deleted
toDelete = find(data, root);

if (!toDelete) {
    return false;
}

// This function is defined appropriately elsewhere, and finds the parent of the node to be deleted
parent = find_parent(root, toDelete);

// Other cases left out because they work
// If the target node has two children:
if (toDelete->left && toDelete->right) 
{

    // find rightmost child on left that is a leaf
    Node *replacement = toDelete->left;
    while (replacement->right) 
    {
        replacement = replacement->right;
    }

    // set the target node's data
    toDelete->data = replacement->data;
    if (parent) 
    {
        if ( parent->data < toDelete->data ) 
        {
            parent->right = replacement;
        } else
        {
            parent->left = replacement;
        }
    } else 
    {
        // if node has no parents, then it is the root and should be replaced with replacement
        // This line here is what seems to be causing my trouble...I think
        root = replacement;
    }
    parent = find_parent(toDelete, replacement);
    if (parent) 
    {
        if (parent->left == replacement)
            parent->left = NULL;
        else
            parent->right = NULL;
    }
    delete toDelete;
    return true; 
}
}

提前致谢!

Answer 1

我最终想到的是:跟踪父节点，该节点位于替换要删除的节点的节点之上。那么就会有两种情况需要考虑:父节点是要删除的节点，父节点不是要删除的节点。通过在正确的情况下替换树的适当部分，树的结构和不变量保持正常，要删除的节点已成功删除。从技术上讲，这将是要删除的节点上的数据。

else if (toDelete->left != NULL && toDelete->right != NULL) {

    // find rightmost child on left that is a leaf
    Node* replacement = toDelete->left;
    parent = toDelete;
    // parent is now the parent of the replacement
    while ( replacement->right ) {
        parent = replacement;
        replacement = replacement->right;
    } // By the end, parent will be the node one above replacement

    toDelete->key = replacement->key;

    if (parent == target) 
        parent->left = replacement->left;
    else 
        parent->right = replacement->left;

    delete replacement;
    return true;
}