mercredi 30 novembre 2016

Understanding how to delete nodes on a Binary Tree

So i am currently studying how to delete nodes on a binary tree although i cannot get over one misunderstanding. i have check the code multiple times and it does work every time. this code comes from Tony Gaddis' C++ From Control Structures through Objects book.

void intBinTree::remove(int num)
{
    deleteNode(num, root);
}

void intBinTree::deleteNode(int num, treeNode*& nodePtr)
{
    if (num < nodePtr->value)
        deleteNode(num, nodePtr->left);
    else if (num > nodePtr->value)
        deleteNode(num, nodePtr->right);
    else
        makeDeletion(nodePtr);
}

void intBinTree::makeDeletion(treeNode*& nodePtr)
{
    treeNode* tempNodePtr = nullptr;

    if (nodePtr == nullptr)
        cout << "Cammot delete empty node" <<  endl;
    else if (nodePtr->right == nullptr)
    {
        tempNodePtr = nodePtr;
        nodePtr = nodePtr->left;
        delete tempNodePtr;
    }
    else if (nodePtr->left == nullptr)
    {
        tempNodePtr = nodePtr;
        nodePtr = nodePtr->right;
        delete tempNodePtr;
    }
    else
    {
        tempNodePtr = nodePtr->right;

        while (tempNodePtr->left)
            tempNodePtr = tempNodePtr->left;

        tempNodePtr->left = nodePtr->left;
        tempNodePtr = nodePtr;
        nodePtr = nodePtr->right;
        delete tempNodePtr;
    }
}

What i am failing to grasp is around the MakeDeletion function.

void intBinTree::makeDeletion(treeNode*& nodePtr)
{
    treeNode* tempNodePtr = nullptr;

    if (nodePtr == nullptr)
        cout << "Cammot delete empty node" <<  endl;
    else if (nodePtr->right == nullptr)
    {
        tempNodePtr = nodePtr;
        nodePtr = nodePtr->left; //where the book says it reattaches child
        delete tempNodePtr;
    }
    else if (nodePtr->left == nullptr)
    {
        tempNodePtr = nodePtr;
        nodePtr = nodePtr->right; //where the books says it reattaches child
        delete tempNodePtr;
    }
    else
    {
        tempNodePtr = nodePtr->right;

        while (tempNodePtr->left)
            tempNodePtr = tempNodePtr->left;

        tempNodePtr->left = nodePtr->left;
        tempNodePtr = nodePtr;
        nodePtr = nodePtr->right; //where the book says it reattaches subtree
        delete tempNodePtr;
    }
}

At first glance it seems like all it does is simply move pointers and leaves subtrees severed. but somehow it works flawlessly and i want to understand how.

Any help would be appreciated.

Aucun commentaire:

Enregistrer un commentaire