Я пытаюсь завершить функцию удаления.
Вот псевдокод, обратите внимание на конец:
Я не знаю, если псевдокод неправильный, хотя.
Вот как я это интерпретировал:
Node* minNode = Minimum(toDelete->right);
int tmp = 0;
tmp = minNode->val;
// delete(&tmp);
free(minNode);
minNode=NULL;
toDelete->val=tmp;
кроме того, как только он удаляет его, он начинает заполнять триллион нулей при печати.
Что я делаю, имеет смысл?
Остальная часть кода, который у меня есть, верна, или я так думаю. Это только облажается в этом сценарии.
Вот и минимальная функция
Node* BST::Minimum(Node *curr) {
// if (curr->left != NULL) {
// return(Minimum(curr->left));
// }
// return curr;
Node* node = curr;
while (node->left != NULL) {
node = node->left;
}
return node;
}
Это какой-то ужасный псевдокод, и на первый взгляд он даже не выглядел правильно (если это дерево двоичного поиска, как BST
будет указывать, то обведенная часть не так). В Интернете доступна гораздо лучшая информация о бинарных деревьях поиска.
В любом случае, вы пытаетесь найти наименьший элемент в правом поддереве, так как он будет меньше, чем все другие элементы в правом поддереве, но больше, чем все другие элементы в левом поддереве.
Похоже, ваша минимальная функция верна. Вам нужно удалить ссылку на minNode после того, как вы ее освободите. Так (minNode->parent)->left
= NULL или что-то немного более утомительное, если у вас нет родительского указателя. Прямо сейчас left
просто указывает на пустое место в памяти, что приводит к совершенно случайному поведению.
Других решений пока нет …