Ошибка при работе с указателем на указатель в функциональности бинарного дерева поиска
У меня есть следующий код:
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Node
{
int value;
Node *left, *right;
Node(int value, Node *l = NULL, Node *r = NULL)
{
this->value = value;
left = l;
right = r;
}
};
struct BST
{
Node *root = NULL;
void insert(int value)
{
cout<<"Inserting: "<<value<<endl;
Node **current = &root;
while(*current != NULL)
{
if(value >= (*current)->value)
{
current = &((*current)->right);
}
else current = &((*current)->left);
}
(*current) = new Node(value);
}
void remove(int value)
{
Node *toRemove = search(value);
remove(toRemove);
}
void remove(Node *toReplace)
{
if(toReplace == NULL) return;
Node *toBeReplacedWith = NULL;
if(toReplace->left == NULL && toReplace->right == NULL)
{
delete toReplace;
toReplace = NULL;
return;
}
if((toReplace->left == NULL) ^ (toReplace->right == NULL))
{
if(toReplace->left != NULL) toBeReplacedWith = toReplace->left;
else toBeReplacedWith = toReplace->right;
copyAndDeleteNode(toReplace, toBeReplacedWith);
return;
}
Node *current = toReplace->left;
while(current->right != NULL) current = current->right;
toReplace->value = current->value;
remove(current);
}
Node* search(int value)
{
Node *current = root;
while(current != NULL && current->value != value)
{
if(current->value > value) current = current->left;
else current = current->right;
}
if(current == NULL)
{
cout<<"The node didn't exist in the BST";
}
return current;
}
void traverse()
{
rec_traverse(root);
}
private:
void copyAndDeleteNode(Node *toReplace, Node *toBeReplacedWith)
{
toReplace->value = toBeReplacedWith->value;
toReplace->left = toBeReplacedWith->left;
toReplace->right = toBeReplacedWith->right;
delete toBeReplacedWith;
toBeReplacedWith = NULL;
}
void rec_traverse(Node * current)
{
if(current == NULL) return;
rec_traverse(current->left);
cout<<current->value<<endl;
rec_traverse(current->right);
}
};
int main()
{
BST tree;
for(int i = 0; i < 10; ++i)
{
tree.insert(i);
}
Node *a = tree.search(6);
cout<<"found val: "<<a->value<<endl;
tree.remove(5);
tree.remove(9);
tree.remove(2);
// tree.insert(4);
//tree.insert(15);
tree.insert(6);
tree.insert(22222);
cout<<"Traversing:\n";
tree.traverse();
return 0;
}
По какой-то причине при выполнении программа вылетает на insert(22222) пока нет никаких проблем с предыдущими звонками, и я не могу понять, почему. Проблема должна быть между строками 26-30, и я всегда помещаю значения NULL в конструктор Node, поэтому я запутался, почему цикл не прерывается.
Решение
Одна вещь, прямо сейчас, что это неправильно:
remove(Node* toReplace),
Эта функция не обновляет ваш указатель узла, так как вы передаете указатель по значению. Весь этот код внутри этой функции, которая изменяет toReplace указатель в любом случае выбрасывается, как только remove возвращается.
Например, эти строки:
delete toReplace;
toReplace = NULL;
delete сделано, но установка указателя на NULL ничего не делает, так как опять toReplace является локальной переменной
Вам нужно изменить свой прототип на это:
remove(Node *& toReplace),
Передача ссылки на указатель теперь позволяет обновить значение указателя и отразить его обратно вызывающей стороне.
Кроме того, вы не проверяли состояние своего дерева после того, как удалили листовой узел «9». Если вы сделали это, вы должны были ясно видеть, что у вашего нового конечного узла ‘8’ есть плохой «правильный» указатель. Это вызывает все виды проблем, когда вы пытаетесь добавить узел (22222), который больше, чем 8.
Ваш remove функция неисправна прямо здесь:
if(toReplace->left == NULL && toReplace->right == NULL)
{
delete toReplace;
toReplace = NULL;
return;
}
Итак, вы удалили узел (предположим, что это узел ‘9’). Так как насчет узла, который раньше указывал на «9»? Вы не настраивали его правые (или левые) указатели, чтобы теперь указывать на NULL. Вот где начинается проблема.
Все это можно было бы обнаружить, если бы вы просто посмотрели на свое дерево, чтобы убедиться, что оно по-прежнему корректно после каждой операции. Вы могли просто использовать отладчик или даже распечатать состояние дерева на каждом этапе.
Наконец, в вашей древовидной структуре отсутствует деструктор. Вы выделяете память, но она нигде не освобождается.
Редактировать:
Что должна делать эта линия? Более конкретно, что это такое ^ должен делать?
if((toReplace->left == NULL) ^ (toReplace->right == NULL))
Другие решения