in C++ language... Can someone please review my function for deleting nodes from
ID: 3913719 • Letter: I
Question
in C++ language... Can someone please review my function for deleting nodes from a binary tree? Is my last part correct? Thanks
**when i went to test...I am unable to remove a node with two children **Thanks in advance!!
EmployeeRecord *EmployeeDatabase::removeEmployee(int ID)
{
EmployeeRecord *back = NULL;
EmployeeRecord *temp = m_pRoot;
EmployeeRecord *delParent = NULL;
EmployeeRecord *delNode =NULL;
while((temp != NULL) && (ID != temp->getID()))
{
back = temp;
if(ID < temp -> getID())
temp = temp -> m_pLeft;
else
temp = temp -> m_pRight;
}
if(temp == NULL)
{
//cout<<"Unknown ID...TRY AGAIN ";
return NULL;
}
else
{
delNode = temp;
delParent = back;
}
//CASE 1: deleting node w. no children or 1 child on left
if(delNode -> m_pRight == NULL)
{
if(delParent == NULL)
{
m_pRoot = delNode -> m_pLeft;
delNode -> m_pLeft = NULL;
return delNode;
}
else
{
if(delParent -> m_pLeft == delNode)
delParent -> m_pLeft = delNode -> m_pLeft;
else
delParent -> m_pRight = delNode -> m_pLeft;
delNode -> m_pLeft = NULL;
return delNode;
}
}
else //THERE IS A RIGHT CHILD ON DELNODE
{
if(delNode -> m_pLeft == NULL)
//CASE 2: NO LEFT CHILD SO DELETING NODE WITH 1 CHILD ON THE RIGHT
{
if(delParent == NULL)
{
m_pRoot = delNode -> m_pRight;
delNode -> m_pRight = NULL;
return delNode;
}
else
{
if(delParent -> m_pLeft == delNode)
delParent -> m_pLeft = delNode->m_pRight;
else
delParent -> m_pRight = delNode->m_pRight;
delNode -> m_pLeft = NULL;
cout<<"This signals that its deleting node other than root ";
return delNode;
}
}
else // DELETING NODE WITH 2 CHILDREN
{
EmployeeRecord *del = new EmployeeRecord();
del -> destroyCustomerList();
EmployeeRecord *left;
EmployeeRecord *right;
// Copy the replacement values into the node to be deleted
left = delNode-> m_pLeft;
right= delNode-> m_pRight;
*del = *delNode;
*delNode = *temp;
//del->m_pLeft = NULL;
//del->m_pRight =NULL;
delNode -> m_pLeft =left;
delNode -> m_pRight = right;
temp = delNode->m_pLeft;
back = delNode;
while(temp->m_pRight != NULL)
{
back = temp;
temp = temp->m_pRight;
}
//removing the replacement node from the tree
if (back == delNode)
back->m_pLeft = temp -> m_pLeft;
else
back -> m_pRight = temp -> m_pLeft;
delete temp;
return del;
}
}
}
Explanation / Answer
EmployeeRecord *EmployeeDatabase::removeEmployee(int ID)
{
EmployeeRecord *back = NULL;
EmployeeRecord *temp = m_pRoot;
EmployeeRecord *delParent = NULL;
EmployeeRecord *delNode =NULL;
while((temp != NULL) && (ID != temp->getID()))
{
back = temp;
if(ID < temp -> getID())
temp = temp -> m_pLeft;
else
temp = temp -> m_pRight;
}
if(temp == NULL)
{
//cout<<"Unknown ID...TRY AGAIN ";
return NULL;
}
else
{
delNode = temp;
delParent = back;
}
//CASE 1: deleting node w. no children or 1 child on left
if(delNode -> m_pRight == NULL)
{
if(delParent == NULL)
{
m_pRoot = delNode -> m_pLeft;
delNode -> m_pLeft = NULL;
return delNode;
}
else
{
if(delParent -> m_pLeft == delNode)
delParent -> m_pLeft = delNode -> m_pLeft;
else
delParent -> m_pRight = delNode -> m_pLeft;
delNode -> m_pLeft = NULL;
return delNode;
}
}
else //THERE IS A RIGHT CHILD ON DELNODE
{
if(delNode -> m_pLeft == NULL)
//CASE 2: NO LEFT CHILD SO DELETING NODE WITH 1 CHILD ON THE RIGHT
{
if(delParent == NULL)
{
m_pRoot = delNode -> m_pRight;
delNode -> m_pRight = NULL;
return delNode;
}
else
{
if(delParent -> m_pLeft == delNode)
delParent -> m_pLeft = delNode->m_pRight;
else
delParent -> m_pRight = delNode->m_pRight;
delNode -> m_pLeft = NULL;
cout<<"This signals that its deleting node other than root ";
return delNode;
}
}
else // DELETING NODE WITH 2 CHILDREN
{
/*
EmployeeRecord *del = new EmployeeRecord();
del -> destroyCustomerList();
EmployeeRecord *left;
EmployeeRecord *right;
// Copy the replacement values into the node to be deleted
left = delNode-> m_pLeft;
right= delNode-> m_pRight;
*del = *delNode;
*delNode = *temp;
//del->m_pLeft = NULL;
//del->m_pRight =NULL;
delNode -> m_pLeft =left;
delNode -> m_pRight = right;
temp = delNode->m_pLeft;
back = delNode;
while(temp->m_pRight != NULL)
{
back = temp;
temp = temp->m_pRight;
}
//removing the replacement node from the tree
if (back == delNode)
back->m_pLeft = temp -> m_pLeft;
else
back -> m_pRight = temp -> m_pLeft;
delete temp;
return del;
*/
//we have to replace the node that is deleted
//with smallest element in the right sub tree..
//means left most element in in-order traverse...
//so first we need to find left most element in rigth subtree
EmployeeRecord *left,*back2=NULL;
EmployeeRecord *right,*templ=NULL;
// Copy the replacement values into the node to be deleted
left = delNode-> m_pLeft;
right= delNode-> m_pRight;
//now from right subtre..we are going to find leftmost node..
temp1 = right;
while(temp1->m_pLeft!=NULL)
{
back = temp1;
temp1=temp1->m_pLeft;
}
//now removing links...
if(back!=NULL)
{
back->m_pLeft=temp1->m_pRight;
if(delParent -> m_pLeft == delNode)
delParent -> m_pLeft = temp1;
else
delParent -> m_pRight = temp1;
temp1->m_pLeft = left;
temp1->m_pRight = right;
delNode -> m_pLeft = NULL;
delNode -> m_pRight = NULL;
return delNode;
}
else
{
//means immediate right element is to be replaced
if(delParent -> m_pLeft == delNode)
delParent -> m_pLeft = right;
else
delParent -> m_pRight = right;
delNode -> m_pLeft = NULL;
delNode -> m_pRight = NULL;
return delNode;
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.