所以,我的问题是我不明白为什么这不起作用。我在下面评论说,明明是初始化的,却从来没有初始化。我是不是把指针写错了,我是不是把逻辑搞反了我是不是偏离太远了,还是从头开始更好?这是我遇到的最难的任务,所以任何帮助都将是非常有益的。
void Dictionary::remove(string word)
{
if(root == NULL)
{
cout << "list is emptyn";
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;
}
}
}
1。我看到的第一件事:
while(curr != NULL)
{
//stuff
}
正如所写的,似乎在你的循环结束时curr == NULL
Lazy me必须查看循环的内容才能注意到中断。如果循环中有一个更大的块,那么中断就更不明显了。这不是一个好的做法。
使用bool(例如:bool isNodeFound;),它便宜(一个位)并且使它更清晰。= NULL &&!isNodeFound)乍一看更清楚您的意图,而无需查看循环的内容。
2。如果您确实没有在循环中击中断点并且curr == NULL怎么办?您的下一个指令(左)将失败!看来布尔值又会派上用场了!
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
}
试着用同样的心态分析你的代码的其余部分,更清晰和测试,让我知道它是否有效。
大家。有一天,当我需要在BST中删除树节点的函数时,我搜索了这个问题。所以,这个问题很好,我编辑并检查了上面的代码,然后代码真的运行成功。上面的代码遗漏了一些实例,请跟随我下面的解释:
首先,删除的节点是LEAF node。你错过了一个节点是根节点或叶节点的实例(即BST只有一个节点)。因此,parent为NULL, parent->left/right无效。
第二,被删除的节点在左侧或右侧有一个子树。因此,如果删除的节点是根节点,这与First类似。
第三,删除节点有左、右子树。您考虑了"parent",但您不应该使用"if(parent == NULL || parent->left==curr)",就好像parent = NULL一样,以便parent->left无效。你应该让"if(parent == NULL){…} else{if(parent->left == curr)…}".
最后,使用if…else-if…Else代替if…if…如果因为你删除了"curr",那么你将不知道"curr"指向任何地方," If "接下来仍然会被检查为"curr"错误。
下面编辑的代码为任何人需要,
void Dictionary::remove(string word)
{
if(root == NULL)
{
cout << "list is emptyn";
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 == NULL) {
delete curr;
} else {
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
*/
else if((curr->left == NULL && curr->right != NULL) || (curr->left != NULL && curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if (parent == NULL) {
root = curr->right;
curr->right = NULL;
delete curr;
} else {
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 == NULL) {
root = curr->left;
curr->left = NULL;
delete curr;
} else {
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
}
}
else
{
DictionaryNode* temp;
if(parent == NULL)
{
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->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;
}
}
}
}
希望这段代码能在别人需要的时候帮助到他们!