Re: Need help find error with Binary tree code
parent-> is Null here and its trying to become curr, but breaks(code crashes) here.
Code:
template <class S> bool BST<S>::Remove(const S &d)
{
//Locate the element
bool found = false;
if(isEmpty())
{
cout<<" This Tree is empty! "<<endl;
return false;
}
Node* curr;
Node* parent;
curr = root;
while(curr != NULL)
{
if(curr->count == d)
{
found = true;
break;
}
else
{
parent = curr;
if(d>curr->count) curr = curr->right;
else curr = curr->left;
}
}
if(!found)
{
cout<<" count not found! "<<endl;
return false;
}
// 3 cases :
// 1. We're removing a leaf node
// 2. We're removing a node with a single child
// 3. we're removing a node with 2 children
// Node with single child
if((curr->left == NULL && curr->right != NULL)|| (curr->left != NULL
&& curr->right == NULL))
{
if(curr->left == NULL && curr->right != NULL)
{
if(parent->left == curr) <--------------------------------------------Problem Area
{
parent->left = curr->right;
delete curr;
}
else
{
parent->right = curr->right;
delete curr;
}
}
else // left child present, no right child
{
if(parent->left == curr)
{
parent->left = curr->left;
delete curr;
}
else
{
parent->right = curr->left;
delete curr;
}
}
return true;
}
//We're looking at a leaf node
if( curr->left == NULL && curr->right == NULL)
{
if(parent->left == curr) parent->left = NULL;
else parent->right = NULL;
delete curr;
return true;
}
//Node with 2 children
// replace node with smallest value in right subtree
if (curr->left != NULL && curr->right != NULL)
{
Node* chkr;
chkr = curr->right;
if((chkr->left == NULL) && (chkr->right == NULL))
{
curr = chkr;
delete chkr;
curr->right = NULL;
}
else // right child has children
{
//if the node's right child has a left child
// Move all the way down left to locate smallest element
if((curr->right)->left != NULL)
{
Node* lcurr;
Node* lcurrp;
lcurrp = curr->right;
lcurr = (curr->right)->left;
while(lcurr->left != NULL)
{
lcurrp = lcurr;
lcurr = lcurr->left;
}
curr->count = lcurr->count;
delete lcurr;
lcurrp->left = NULL;
}
else
{
Node* tmp;
tmp = curr->right;
curr->count = tmp->count;
curr->right = tmp->right;
delete tmp;
}
}
return true;
}
}
Re: Need help find error with Binary tree code
A new problem other then my remove function not working is when i compile under KDE, runing command g++ -g *.cpp -o test
i get
in member function 'bool BST<S>::Insert(const S&)'
error: '->' cannot appear in a constant-expression
error: parse error in template argument list
for the line if( t->count < parent->count)
parent->left =t;