C++二进制搜索树删除

所以，我的问题是我不明白为什么这不起作用。我在下面评论了它在说什么，当它明确时父从未被初始化。我在做指针错误吗？我是否已经将逻辑向后推进，我现在离开了，从头开始更好？这是我遇到的最困难的任务，所以任何帮助都是非常有益的。C++二进制搜索树删除

void Dictionary::remove(string word) 
{ 
if(root == NULL) 
{ 
    cout << "list is empty\n"; 
    return; 
} 
DictionaryNode *curr = root; 
DictionaryNode *parent = NULL;` 

while(curr != NULL) 
{ 
    if(curr->word == word) 
     break; 
    else 
    { 
     parent = curr; 
     if(word > curr->word) 
      curr = curr->right; 
     else 
      curr = curr->left; 
    } 
} 
//LEAF node. 
if(curr->left == NULL && curr->right == NULL) 
{ 
    if(parent->left == curr) // Right here is an access violation. Which doesn't //make sense. 
    { 
     parent->left = NULL; 
    } 
    else 
    { 
     parent->right = NULL; 
    } 
    delete curr; 
} 

/* 
* Node has a single child LEFT or RIGHT 
*/ 
if((curr->left == NULL && curr->right != NULL) || (curr->left != NULL && curr->right == NULL)) 
{ 
    if(curr->left == NULL && curr->right != NULL) 
    { 
     if(parent->left == curr) //if(parent->left == curr) //says parent is //not intialized 
     { 
      parent->left = curr->right; 
      delete curr; 
     } 
     else 
     { 
      parent->right = curr->right; 
      delete curr; 
     } 
    } 

    else 
    { 
     if(parent->left == curr) 
     { 
      parent->left = curr->left; 
      delete curr; 
     } 
     else 
     { 
      parent->right = curr->left; 
      delete curr; 
     } 
    } 

} 

if (curr->left != NULL && curr->right != NULL) 
{ 
    DictionaryNode* temp; 
    if(parent == NULL || parent->left==curr) 
    { 
     temp = curr->right; 
     while(temp->left!=NULL) 
      temp = temp->left; 
     if(parent!=NULL) 
      parent->left = curr->right; 
     else 
      root = curr->right; 
     temp->left = curr->left; 
     curr->left = curr->right=NULL; 
     delete curr; 

    } 

    else if(parent->right==curr) 
    { 
     temp = curr->left; 
     while(temp->right!=NULL) 
      temp = temp->right; 
     parent->right=curr->left; 
     temp->right = curr->right; 
     curr->left = curr->right=NULL; 
     delete curr; 
    } 
    } 

}

来源

2014-03-28 varrick

如果字典中只包含1个元素，该怎么办？ 'curr == root'，'parent == NULL'，'parent-> left'是一个访问冲突。 – timrau

另外，您尝试在'delete curr;'之后访问'curr-> left'。这显然是一个释放的内存读取。 – timrau

首先，谢谢你编辑它我不能为我的生活弄清楚。如果我有一个元素，它的作品。我应该在我的问题上更具体。这是当我去删除它开始抛出我的脸上的错误的东西。 – varrick

1. 第一件事，我看到：

while(curr != NULL) 
{ 
//stuff 
}

因为它是写的，它似乎在你的循环CURR == NULL结束

懒惰的我不得不看你的循环的内容注意到休息。循环中的更大块可能会更不明显。这不是一个好习惯。

使用bool（例如：bool isNodeFound;），它很便宜（一位）并使其更清晰。 while（curr！= NULL & &！isNodeFound）更加清楚你的意图，乍一看，没有看你的循环内容。

2.如果确实没有在循环中打中断并且curr == NULL？你的下一个指令curr-> left会失败！似乎布尔将再次有用！

if(!isNodeFound) 
{ 
//log error if you can "cannot remove node because it is not in dictionary" 
return false; //make your function a bool to return if it succeeded or not 
}

尝试分析你的代码的其余部分用着相同的状态，更加清晰和测试，让我知道，如果它的工作原理。

来源

2014-03-28 00:43:27 vincentB

嗯，看我明白你的意思，但是，我不认为做布尔函数真的会帮助我。事情是，它会删除一些东西，不管它是根节点还是最后一个节点还是最后一个孩子。这只是有时，它给了我访问冲突。我不明白，但我会尝试你所说的。谢谢 – varrick

在技术上bool使用一个字节的空间而不是一个位，因为计算机无法寻址单个位，只能寻址字节。 – isaac9A

std :: vector 可以将bools包装成点！但是我的意思是字节哈哈，谢谢varrick – vincentB

C++二进制搜索树删除

回答

相关问题