I'm doing a binary search tree deletion algorithm but having problems with deletions. The constructors for my BinaryTreeNode class has to nullify the elements of the BinaryTreeNode[2] arrays because by default they are not null, otherwise it would mess up my insertions and searches. But when I delete, they do not revert to a null status. So if I delete one by using a pointer then the deleted one reains a value other than 0x0. Anyone know what's going on?
Here's the incomplete function
Code:
void BSTree::Delete(int x)
{
if(root == NULL)
{
std::cout << "-- Tree is empty --" << std::endl;
return;
}
BinaryTreeNode* rt = root;
BinaryTreeNode* advance = NULL;
while(true)
{
//delete based on deletion rules
if(rt->data == x)
{
//if both children are empty, delete and return
if(rt->child[0] == NULL && rt->child[1] == NULL)
{
delete rt;
std::cout << "-- " << x << " has been deleted --" << std::endl;
return;
}
//..other deletion rules.
}
else
{
size_t dir = x < rt->data ? 0 : 1;
if(rt->child[dir] == NULL)
{
std::cout << "-- "<< x
<<" not found, cannot delete --" << std::endl;
return;
}
else
rt = rt->child[dir];
}
}
}