C++：在BST中刪除一個節點，或者得到seg故障或者複製節點

Question

所以我已經做了相當多的搜索，但是許多有刪除問題的人與我有完全不同的BST實現。在這個任務中，我們被賦予了一個帶有字段nodeContent的BST類，以及指向root，leftChild和rightChild的指針。本週的任務是創建一個刪除樹中指定節點的函數，然後我們應該能夠遍歷樹來驗證節點已經消失。我認爲自己做的很好，但是當我測試我的代碼時，它或者返回確實已經刪除了該節點，但是我複製的節點已被複制。或者，當我嘗試刪除有兩個孩子的筆記時，出現分段錯誤。我是新來張貼，所以如果我做錯了，我表示歉意。我剛剛試圖查明我出錯的地方！提前致謝。哦，是的，我對這個瘋狂的評論道歉。當我陷入困境，試着通過步驟談論自己時，我添加了很多評論。

  /* 
      void BST::deleteNode(int el) 
      Input: An integer that is to be deleted from the tree 
      Output: Nothing 
      Side Effect: Single node deleted and tree reordered 
      */ 
      void BST::deleteNode(int el) 
      { 
       BSTNode *temp; 
       BSTNode *prev; 
       BSTNode *node = Root; 

       while (node -> nodeContent != el && node != NULL) // start the search 
       { 
       // if the search is less than 
       if(el < node -> nodeContent) 
       { 
        node = node -> leftChild; 
       } 
       else if (el > node -> nodeContent) 
       { 
        node = node -> rightChild; 
       } 

       if (node == NULL) 
       { 
        std::cout << "That item cannot be deleted, " 
           "because it doesn't exist" << std::endl; 
        return; 
       } 
       } 
       // ok, so we found the node 

       // this is if node has two children 
       if (node -> leftChild != NULL && node -> rightChild != NULL) 
       { 
       // first, set temp to rightmost node in left subtree 
       temp = node -> leftChild; 
       while (temp -> rightChild != NULL) 
       { 
        // set prev to the node above node (bad name resolution, I know..) 
        prev = temp; 
        temp = temp -> rightChild; 
       } 
       // now we have our node, temp, and prev set. 
       // time to do some copying 
       // first step: set prev's rightChild to NULL 
       prev -> rightChild = NULL; 
       // ok. now we need to check if temp has a left child 
       if (temp -> leftChild != NULL) 
       { 
        //if it does, set it to prev's rightChild 
        prev -> rightChild = temp -> leftChild; 
       } 
       // done. Now set nodes content to temps content 
       node -> nodeContent = temp -> nodeContent; 
       // good work. now delete temp 
       delete temp; 
       temp = NULL; 
       } 
       // this one is for deleting a node without a right child 
       if (node -> rightChild == NULL && node -> leftChild != NULL) 
       { 
       // using temp this time as the leftChild of the node to be deleted 
       temp = node -> leftChild; 
       // copy the content from child to node's content 
       node -> nodeContent = temp -> nodeContent; 
       // george r.r. martin the heck out of temp, for his watch has ended 
       delete temp; 
       temp = NULL; 
       } 
       // now, if (soon-to-be) deleted node only has a right child 
       if (node -> leftChild == NULL && node -> rightChild != NULL) 
       { 
       // set temp to be nodes rightChild 
       temp = node -> rightChild; 
       // copy content from temp to to node 
       node -> nodeContent = temp -> nodeContent; 
       // delete temp 
       delete temp; 
       temp = NULL; 
       } 
       // the last one should be the easiest, if the node has no children 
       if (node -> leftChild == NULL && node -> rightChild == NULL) 
       { 
       delete node; 
       } 
      } 

Answer 1

您正在使用三個if語句而不是從任何塊返回。所以，想象一下你的第一個陳述得到滿足並且該節點只有一個正確的孩子。這個孩子被刪除了。

現在，代碼轉到第二個if聲明，而這又是真的！然後執行第二個if塊。

我希望這會引導你回答。 另外，要找到發生分段故障的位置正好爲GDB。如果你使用C++進行編碼，它是一個重要的工具。