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; 
    } 
} 

leaf：

/********************************************************* 
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 */ 
} 

應該注意的是，我的節點是在類頭部中聲明的結構，並且變量root以BinTreeNode * root形式聲明爲受保護的變量;它在binSTree構造函數中被初始化爲NULL。另外，我只允許刪除葉子。

Answer 1

在我看來，你做錯了什麼是在privRemove方法裏面...... 想象一下，你已經嘗試刪除一個節點，並在該節點上調用privRemove。

有：

delete node; 

你釋放內存節點指向。

然後重新分配節點將其與之前的值：

node=temp; 

所以現在像以前一樣指向同一個位置（內部和功能的，因爲你通過它引用外）。

現在在下一個刪除你最終會遇到同一個節點，並測試它是否爲NULL，但它不是因爲你給它一個值，所以它指向它之前的內存（node = temp），所以節點指向內存中不是NULL的地方，所以你會認爲它是一個合法的節點，但它不是，它指向已經釋放的內存。當你調用一個方法... bhumm！