从二叉搜索树中删除

我正试图从二叉树函数中删除。我有点失落，所以我试图处理它的情况下，开始如果我试图删除的价值是在BST的根。为了测试我的函数，我首先调用printcontents（）函数来打印树的所有内容，然后调用remove（8）[8此时是我的根目录中的值），然后调用printcontents（）。我这样做的方式是试图用树左侧的“最右侧”值替换根。当我第二次调用printcontents时，它会正确打印新的根值，但当它继续打印内容并达到该值以前的位置时，它将有一个随机的长整数“-572 ......” （虽然我不认为这个数字很重要），然后我的程序崩溃了。我看到我的根的价值正在被取代，但之后会发生什么？从二叉搜索树中删除

这是我的删除功能：

void BinarySearchTree::remove(int value) { 

     Node* tmp = head; 
     Node* tmp2 = head; 


    if (head->data == value && head->left != NULL) { 

     tmp=tmp->left; 

     while (tmp->right != NULL) { 
      tmp=tmp->right; 

     } 

     while (tmp2->right->right != NULL) { 
      tmp2=tmp2->right; 

     } 

     if (tmp->left == NULL) {  

     head->data = tmp->data; 
     tmp2->right = NULL; 
     delete tmp; 

     } 

     if (tmp->left != NULL) { 

      head->data = tmp->data; 
      tmp2->right = tmp->left; 
      delete tmp; 

     } 




}

这显然是不完整的，但我也测试只能处理其中的根源去除，并且左侧由最右边的值替换的情况下树（假设有一个左边，有），并且我觉得它在逻辑上应该是有效的，所以也许是当我“删除tmp”时出现错误。我不知道发布我的整个程序是否必要，但如果是这样，请告诉我！

来源

2013-10-24 FrostyStraw

永远不会被忽视如此糟糕大声笑 – FrostyStraw

我可以建议您不要为root写作，您为什么不把它视为在CLRS中处理：这是两个不同的情况。 1.当要删除的节点是一个叶子 2.当要删除的节点是非叶子（在这种情况下，将其替换为inorder后继/前任）。

根删除显然属于第二种情况。这只是一个建议。

来源

2013-10-24 04:17:19

从二叉搜索树中删除

回答

相关问题