抛出异常：读取访问 violation.during BST 删除许多元素

Question

所以我在删除期间遇到异常问题（抛出异常：读取访问冲突。 parent 是 0x158398。）就像有时是不同的数字等，并且总是关于 parent object/pointer，我的代码工作没有任何错误，异常直到 100k objects 然后有时工作有时不是，因为 100 万甚至没有工作 anymore.If 任何人都可以提供帮助会很棒。在 post 下方 post 正在输入代码：

节点Class:

template <class T>
class Node {

public:
    T data;
    Node<T>* Left = NULL;
    Node<T>* Right = NULL;
};

求右子树最小值的代码：

Node<T>* findMin(Node<T>* node)
    {
        while (node->Left != NULL)
            node = node->Left;
        return node;
    }

删除代码：

void Delete(Node<T>*& node) {

    if (node == NULL)
        return;

    Node<T>* parent = findParentForDelete(this->root, node);
    Node<T>* temp = NULL;


    //leafs
    if (node->Left == NULL && node->Right == NULL) {
        if (node == root) {
            delete root;
            root = NULL;
            return;
        }
        else {
            if (parent->Left == node)   //line with exception
                parent->Left = NULL;
            else
                parent->Right = NULL;
            delete node;
            node = NULL;
            return;
        }
    }
    //1 child left not null
    else if (node->Left != NULL && node->Right == NULL)
    {
        if (node == root) {
            temp = root->Left;

            delete root;
            root = NULL;

            root = temp;
            return;

        }
        else {
            if (parent->Left == node)
                parent->Left = node->Left;
            else
                parent->Right = node->Left;

            delete node;
            node = NULL;
            return;

        }
    }
    //1 child Right not null
    else if (node->Left == NULL && node->Right != NULL)
    {
        if (node == root) {
            temp = root->Right;

            delete root;
            root = NULL;

            root = temp;
            return;
        }
        else {
            if (parent->Left == node)
                parent->Left = node->Right;
            else
                parent->Right = node->Right;

            delete node;
            node = NULL;
            return;
        }
    }
    //2 childs
    else if (node->Left != NULL && node->Right != NULL)
    {
        temp = findMin(node->Right);
        T data = temp->data;
        Delete(temp);
        node->data = data;
}
}

发现 parent:

Node<T>* findParentForDelete(Node<T>* node, Node<T>*& nodeToFind)
    {
        if (node == NULL)
            return NULL;

        if (node->Left == NULL && node->Right == NULL)
            return NULL;

        if ((node->Left != NULL && node->Left == nodeToFind)
            || (node->Right != NULL && node->Right == nodeToFind))
            return node;

        if (node->data->age > nodeToFind->data->age)
            return findParentForDelete(node->Left, nodeToFind);

        if (node->data->age < nodeToFind->data->age)
            return findParentForDelete(node->Right, nodeToFind);
    }

Answer 1

findParentForDelete 并不总是 return 一个值。

如果您要查找的节点的年龄与树中其他节点的年龄相同，则不会 return 值，因此该值 return 发送给调用者将是一个垃圾值。

如果在编译时提高警告级别，大多数编译器都会为此发出警告。

抛出异常：读取访问 violation.during BST 删除许多元素

Exception thrown: read access violation.during BST Deletion for many elements

c++

algorithm

data-structures

binary-search-tree