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++进行编码，它是一个重要的工具。