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