Удаление бинарного дерева поиска 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;
}
}
}
Решение
1.
Первое, что я вижу:
while(curr != NULL)
{
//stuff
}
Как написано, кажется, что в конце вашего цикла curr == NULL
Ленивый я должен был посмотреть на содержание вашего цикла, чтобы заметить разрыв. Разрыв может быть еще менее заметным с большим блоком в цикле.
Это не очень хорошая практика.
Используйте bool (например, bool isNodeFound;), это дешево (один бит) и делает его более понятным.
while (curr! = NULL && ! isNodeFound) с первого взгляда более ясно о ваших намерениях, не глядя на содержание вашего цикла.
2.Что, если вы действительно не нажмете на разрыв в цикле и curr == NULL?
Ваша следующая инструкция curr-> left потерпит неудачу!
Похоже, что Boolean снова будет полезен!
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 недействителен.
Во-вторых, удаленный узел имеет поддерево влево или вправо. Таким образом, это похоже на Первый, если удаленный узел является корневым.
В-третьих, удаленный узел имеет левое и правое поддерево. Вы считали «родитель», но не должны использовать «if (parent == NULL || parent-> left == curr)», как если бы parent = NULL, так что parent-> left является недействительным. Вы должны сделать «if (parent == NULL) {…} else {if (parent-> left == curr) …}».
Наконец, используйте if … else-if … else вместо использования if … if … if, потому что вы удалили «curr», тогда вы не узнаете точку «curr» где-нибудь и «if» далее будет проверено с ошибками curr.
Ниже отредактированный код для кого угодно,
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 == 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;
}
}
}
}
Надеюсь, что этот кодекс может помочь другим людям, когда они нуждаются!