Hiya,
I am having an issue when i try to delete a node with 2 children it either doesn't delete anything, or wigs out in various manners deleting the wrong node or replacing a node with a various memory location, and I have been staring my code down for several hours giving it the evil eye. Help a college student out? It would be greatly appreciated!
As follows, here is the delete function:
void BST::dele(){//pain.. so much pain... lots of advil
bool found = false;//initialize a bool type to "find" the element to be deleted
if(root == NULL) return;//well if the tree's empty, nothing to be found right?
current = root;//set the current to the root to traverse the tree in search of the element
node* parent;//create a parent node for use once the node has been deleted
while(current != NULL){//traverse the tree
if(current->data == value){
found = true;
break;//i dont understand why this fixed my infinit loop problem, but it did
}
else{
parent = current;//make sure they're pointing to the same thing BEFORE you change current, this is
if(value < current->data) current = current->leftchild;//important for reattaching the leaf nodes of the
else current = current->rightchild;//deleted node
}
}
if(found != true)return;//if the element wasnt found, we're done here.. yay!
if((current->leftchild == NULL && current->rightchild != NULL) || (current->leftchild != NULL &&
current->rightchild == NULL)){//Case 1: the node to be deleted has only one child node
if(current->leftchild == NULL && current->rightchild != NULL){//has a right child but no left child
if(parent->leftchild == current){
parent->leftchild = current->rightchild;
current->node::~node();//to be perfectly honest i had to look up this delete thing... this was new to me
}
else{//depending on which child the current pointer contains (either right or left child) the
parent->rightchild = current->rightchild;//parent node will attach its child node to the current
current->node::~node();//pointers child
}
}
else{//has a left child but no right child
if(parent->leftchild == current){
parent->leftchild = current->leftchild;
current->node::~node();
}
else{
parent->rightchild = current->leftchild;
current->node::~node();
}
}
size--;//for keeping track of how large my list is
return;
}
elseif(current->leftchild == NULL && current->rightchild == NULL){//node with no children
if(parent->leftchild == current) parent->leftchild = NULL;
else parent->rightchild = NULL;
current->node::~node();
size--;
return;
}
else{//node has 2 children... the painful part
node* seek;//a temp pointer to find the node we want
seek = current->leftchild;
if(seek->leftchild == NULL && seek->rightchild == NULL){//first check if the node has children
current = seek;//and if it doesnt, easy swaps
seek->node::~node();
current->leftchild = NULL;
}
else{//but if it does..
if((current->leftchild)->rightchild != NULL){//move down to the largest value in the left subtree
node* righttemp;
node* right2temp;//if you get this reference, i will high five the jesus out of you
right2temp = current->leftchild;
righttemp = (current->leftchild)->rightchild;
while(righttemp->rightchild != NULL){//find the largest value
right2temp = righttemp;
righttemp = righttemp->rightchild;
}
current->data = righttemp->data;//once found, set the largest value to the current value
righttemp->node::~node();//delete the largest value's original position
right2temp->rightchild = NULL;//make sure the parent of the largest value's original position
}//is nown null
else{
node* temp;
temp = current->leftchild;
current->data = temp->data;
current->leftchild = temp->leftchild;
temp->node::~node();
}
}
size--;
return;
}
}
I feel like it's a simple error, but I could use an extra set of eyes. please and thank you!
