I've got the following code:
#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;
}
For some reason when executing, the program crashes on the insert(22222) while there is no problem on the previous calls and I can't understand why. The problem must be between lines 26-30 and I always put NULL values in the Node constructor so I'm confused why the loop doesn't break.
For some reason when executing, the program crashesUse your debugger to determine the reason for the problem.