C++ programming help: My function for removing a node with two children in a bin

Question

C++ programming help:

My function for removing a node with two children in a binary tree is not working! Any help is much appreciated.

Thanks

#include "EmployeeDatabase.h"
#include "EmployeeRecord.h"
#include "CustomerList.h"
#include <iostream>
#include <iomanip>
#include <string>

EmployeeDatabase::

EmployeeDatabase(void)
{
    //cout<<"Constructor reached ";
    m_pRoot = NULL;
}

EmployeeDatabase::~EmployeeDatabase(void)
{
    //cout<<"destructor reached ";
    destroyTree(m_pRoot);
    m_pRoot = NULL;
}

bool EmployeeDatabase:: addEmployee(EmployeeRecord *e)
{
    //cout<<"Add Employee Function reached ";

    EmployeeRecord *temp = m_pRoot;
    EmployeeRecord *back = NULL;

    while (temp != NULL)
    {
        back = temp;
        if (e-> getID() < temp->getID())
            temp = temp -> m_pLeft;
        else
            temp = temp -> m_pRight;
    }

    if (back == NULL)
        m_pRoot = e;
    else
    {
        if ( e-> getID() < back -> getID())
            back -> m_pLeft = e;
        else
            back -> m_pRight = e;
    }           
    return true;
}

EmployeeRecord *EmployeeDatabase:: getEmployee(int ID)
{
    //cout<<"Get Employee Function reached ";

    EmployeeRecord *temp = m_pRoot;

    while ((temp != NULL) && (temp -> getID() != ID))
    {
        if (ID < temp-> getID())
            temp = temp -> m_pLeft;
        else
            temp = temp -> m_pRight;
    }

    if (temp == NULL)
    {
        return NULL;
        cout<<"Invalid store"<<temp;
    }   
    else
        return temp;
}

EmployeeRecord *EmployeeDatabase::removeEmployee(int ID)
{
    EmployeeRecord *back = NULL;
    EmployeeRecord *temp = m_pRoot;
    EmployeeRecord *delParent = NULL;
    EmployeeRecord *delNode =NULL;
    //cout<<"Remove Employee Function reached ";
    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<<"ID not found...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;
        }
        cout<<"Removed store "<<temp<<endl;
    }
    else //THERE IS A RIGHT CHILD ON DELNODE
    {
         //cout<<"Remove Employee Function for 1 right child reached ";

        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;
                return delNode;
            }
        }
     
       else // DELETING NODE WITH 2 CHILDREN
        {
            EmployeeRecord *del = new EmployeeRecord();
            del -> destroyCustomerList();
//            EmployeeRecord *back = NULL;
            EmployeeRecord *left = NULL;
            EmployeeRecord *right = NULL;
//            EmployeeRecord *temp = NULL;
             //cout<<"Remove Employee Function for 2 children reached ";
            // 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;
            temp = delNode->m_pLeft;
            back = delNode;
            while(temp->m_pRight != NULL)
            {
                back = temp;
                temp = temp->m_pRight;
            }
            *delNode = *temp;
            delNode -> m_pLeft =left;
            delNode -> m_pRight = right;
           
            delete temp;
            return del;
           
        }
    }
}

Explanation / Answer

For the variable delNode (where you're intending to delete the node with two children):

first it's mandatory to evaluate and find out the minimum valued number in the right subtree and then the node which you intend to remove(the one with two children) has to be replaced with this minimum valued node.  

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.