C++ BST 内存错误 - 我的删除有什么问题？

Question

我遇到的问题是我的树只能成功删除一个节点一次。当我尝试让它删除更多内容时，它会因段错误(核心转储)错误而崩溃。我似乎无法指出它出错的确切位置，但它应该是我在内存分配和释放方面做错的事情，我只是看不到它。

这是我的插入、删除、删除助手和叶子(因为它在删除内部调用):

插入:

/*********************************************************
 Function: insert
 Arguments: const T &x (a T variable)
 Returns: void
 Notes: If the tree is empty, the function will set the node 
    as the root. Otherwise, it will look for the appropiate 
    place (in terms of a BST) to place it as long as its data 
    is not already existent inside the tree. 
*********************************************************/
template<class T> void binSTree<T>::insert(const T &x)
{
    BinTreeNode *newnode, *current, *parentOfCurrent; /* newnode will be the inserted node, current and parentOfCurrent will be traversing the while loop to find an appropiate space to insert */
    newnode = new BinTreeNode; /* allocates storage space */
    newnode->info = x; /* sets newnode's data equal to x */
    newnode->left = newnode->right = NULL; /* sets newnode's left and right children equal to NULL */

    if (root == NULL)   { /* if the tree is empty, it will place newnode on the root */
        root = newnode;
        cout << "added to root\n";
        return;         }
    current = root; /* sets current at the root */
    while(current != NULL)  { /* while current is not NULL, it will search for a place to insert the new node */
    parentOfCurrent = current; /* sets the parent equal to current */ 
        if(current->info == x) /* if the variable is found inside the tree, then it will error and exit */
        {
            cout << x << " already exists in tree. Duplicates not allowed!\n";
            return;
        }
        else if(current->info > x) /* otherwise, if the variable is less than the data on the tree currently, it will move left */ 
            current = current->left; 
        else                       /* otherwise, if the variable is greater than the data on the tree currently, it will move right */          current = current->right;
                            }
    /* the new node is placed where current would be in */ 
    if (parentOfCurrent->info > x) 
        parentOfCurrent->left = newnode;
    else
        parentOfCurrent->right = newnode;
}

删除和 privRemove:

template <class T> bool binSTree<T>::remove(const T &x)
{
    BinTreeNode *current, *parentOfCurrent; /* current for tranversing the tree in the while loop and parentofCurrent to help */
    bool found = false; /* the booleans that is to be returned */
    if (root == NULL)   { /* Checks if the tree is empty, if it is, it returns found (false) and exits */
        return found;
                        }
    current = root; /* sets current equal to root */ 
    while(current != NULL) /* loops repeats until current is equal to NULL */
    {
        if(current->info == x)  { /* if the current data from the tree is equal tox, then it breaks the loop and sets found equal to true */
            found = true;
            break;
                                }
        else    { /* otherwise, it will search for the next place to go in the tree */
            parentOfCurrent = current; /* parentOfCurrent is set to current before current is set to one of its children */ 
            if(current->info > x) /* if x is less than the data on current, then it will move left */
                current = current->left;
            else   /* if x is greater than the data on current, then it will move right */
                current = current->right;
                }
    }
    if(found == true) { /* if it was found, it will pass current via the parent to the private remove function */ 
        if (current == root)
            privRemove(root);
        else if (parentOfCurrent->info > x) {  /* if current is to the left of the parent */
            found = leaf( parentOfCurrent->left );
            if(found == true)
                privRemove(parentOfCurrent->left);
                                            }
        else {  /* if current is to the right of the parent */
            found = leaf( parentOfCurrent->left );
            if(found == true)
                privRemove(parentOfCurrent->right);
             }
                      }
    return found;
}
/*********************************************************
 Function: privRemove
 Arguments: BinTreeNode* &node (the node that is to be deleted)
 Returns: void
 Notes: This private remove function will take in the node that 
    is provided by the public remove function, and, after ensuring
    that the node passed is not NULL, then it will delete it.
*********************************************************/
template <class T> void binSTree<T>::privRemove(BinTreeNode* &node) 
{
    BinTreeNode *temp; /* initializes temp in order to hold the information of node */ 
    if(root != NULL )  /* if the node is not NULL */
    {
        temp = node;
        delete node;
        node = temp;
    }
}

叶子:

/*********************************************************
 Function: leaf
 Arguments: BinTreeNode* node
 Returns: boolean
 Notes: This function will check if the node in the argument 
  is a leaf by checking if both of its children are NULL. If 
  they are, it returns true. Otherwise, it returns false. 
*********************************************************/
template <class T> bool binSTree<T>::leaf(BinTreeNode* node) const
{
    bool isLEaf = false; /* the boolean variable it is to return */ 
    if(node->left == NULL && node->right == NULL) /* checks if the node has no children */
        isLEaf = true;  /* if it does, it sets isLEaf equal to true */
    return isLEaf;  /* after going through the if statement, it returns the variable isLeaf */
}

应该注意的是，我的节点是在类 header 中声明的结构，并且变量 root 以 BinTreeNode* root 的形式声明为 protected 变量；它在 binSTree 构造函数中被初始化为 NULL。另外，我只能删除树叶。

Answer 1

在我看来，您做错的地方在于 privRemove 方法...假设您已尝试删除一个节点，并且在该节点上调用了 privRemove。

与:

delete node;

你释放内存节点指向。

然后您将节点重新分配给它之前的值:

node=temp;

因此它现在指向与之前相同的位置(在函数内部和外部，因为您通过引用传递了它)。

现在在下一次删除时你最终会遇到同一个节点并测试它是否为 NULL，但它不是，因为你给了它一个值所以它指向它之前拥有的内存(node = temp)，所以node 指向内存中不为 NULL 的某个位置，因此您会认为它是合法节点，但事实并非如此，它指向已释放的内存。当您在其上调用方法时...bhumm!