c++ - 二叉搜索树递归删除

Question

当我试图找到我的删除函数的最大值时，我的程序总是中断。我想要做的是用左树的最大值覆盖用户想要删除的内容，然后删除该节点。一旦它到达第一个 Else，它就会不断中断。递归打破了我的想法。我的缺点在哪里？

这是 remove 函数及其私有(private)递归兄弟。

template<typename TYPE>
bool BinarySearchTree<TYPE>::remove(TYPE& data)
{
    bool found = search(dataOut);
    if(found)
        TRoot = Premove(TRoot, data);
    return found;
}

template<typename TYPE>
Node<TYPE>* BinarySearchTree<TYPE>::Premove(Node<TYPE>* root, TYPE& data)
{
    Node<TYPE>* del;
    Node<TYPE>* max;
    if(root)
    {
        if(root->data > data)
            root->left = Premove(root->left, data);
        else if(root->data < data)
            root->right = Premove(root->right, data);
        else
        {
            if(root->left && root->right)
            {
                max = root->left;
                while(max->data < max->right->data)
                    max = max->right;
                root->data = max->data;
                max = Premove(root, max->data);

            }
            else
            {
                del = root;
                root = (root->right) ? root->right : root->left;
                delete pDel;
            }
        }
    }
    return root;
}

Answer 1

问题很可能出在这里: while(max->data < max->right->data) max = max->right;

您正在用完树(max->right 最终将变为 NULL)。其实，因为是二叉搜索树，所以不需要比较data。 .在可能的情况下向右走就足够了:while (max->right) max=max->right;

另请注意该分支中的最后一个作业:还有两个额外的问题。首先，而不是 max = Premove(...)你应该做root->left = Premove(...) (否则你不会修改 root->left 引用)。其次，您应该调用 Premove对于 root->left而不是 root : root->left = Premove(root->left, max->data); (否则你只会得到无限递归)。