目标节点的二叉搜索树删除有两个children

Question

这是我的代码，替换是正确的（将目标节点替换为左边最大的节点sub-tree），但是替换后，左右都sub-trees都走了。

这是我的代码：

else if (temp->left != NULL && temp->right != NULL)
    {
        minLeaf = temp->left;
        minLeafMa = temp->left;
        parentRight = parent->right;

        while (minLeaf->right != NULL)
        {
            minLeafMa = minLeaf;
            minLeaf = minLeaf->right;
        }
        if (parent->left == temp)
        {
            parent->left = minLeaf;
            minLeafMa->right = NULL;
        }
        else if (parent->right == temp)
        {
            parent->right = minLeaf;
            minLeafMa->right = NULL;
        }
    }

Answer 1

删除节点 x 和 2 children 的正确方法是找到 x 的中序 successor 或 predecessor，替换 x 的值与 predecessor 或 successor 的值，并在其中任何一个上调用 delete（无论您使用哪个）。

您正在使用此处的predecessor。你在做

parent->left = minLeaf;

将 parent 的左侧指向叶节点（predecessor 节点），导致中间的所有节点都消失了。相反，你应该做的是

temp->data = minLeaf->data;

并在 minLeaf 上递归调用 delete。

目标节点的二叉搜索树删除有两个children

Binary Search Tree deletion of target node has two children

c++

binary-search-tree