Reputation: 296
I have a binary search tree consists of nodes like:
struct ProductNode
{
Product data;
ProductNode* left;
ProductNode* right;
};
and I have a delete function that takes ProductNode pointer parameter:
void ProductCategory::deleteandnull(ProductNode * p)
{
if(p!=NULL)
{
delete p;
p=NULL;
}
}
I have no problem with deletion methods. The left and right pointers are NULL when a new leaf added but when I use this function I see there is no deletion and this operation does not change the binary search tree. What is that problem?
Upvotes: 1
Views: 3455
Reputation: 3723
Procedure :
1. At first locate the node to be deleted.
2. If the node is a leaf node :
i. If the node is left child of the parent , make null the left pointer of its parent node and free the space for the node.
ii. If the node is right child of the parent , make null the right pointer of its parent node and free the space for the node.
3. If the node has one child
i. If the node to be deleted is a left chile of its parent , then make link between the left pointer of its parent node and the child node to be deleted. Then delete the node.
ii.If the node to be deleted is a right child of its parent , then make link between the right pointer of its parent node and the child node to be deleted. Then delete the node.
4. If the node to be deleted has two child :
i. Locate the node with maximum value from the left sub-tree of the node to be deleted.
ii. Replace the node value to be deleted by the node found in step 4(i)
5. Now we get updated output
node* Delete(node *root, int data)
{
if(root == NULL) return root;
else if(data < root->data) root->left = Delete(root->left,data);
else if (data > root->data) root->right = Delete(root->right,data);
else
{
///Case 1: No child
if(root->left == NULL && root->right == NULL)
{
delete root;
root = NULL;
}
///Case 2: One child
else if(root->left == NULL)
{
struct node *temp = root;
root= root->right;
delete temp;
}
else if(root->right == NULL)
{
struct node *temp = root;
root = root->left;
delete temp;
}
///case 3: 2 children
else
{
node *temp = FindMin(root->right);
root->data = temp->data;
root->right = Delete(root->right,temp->data);
}
}
return root;
}
Upvotes: 1
Reputation: 6434
EDIT: This answer was based on the assumption that the OP was concluding "there is no deletion" because he was expecting to see a NULL pointer in the calling location. If that is not the case he will need to clarify what is leading to that conclusion. As is there is no reason to think the OP's code is not deleting whatever p points to.
p
is passed by value into the deleteandnull
function. Therefore only a local copy of the pointer is set to NULL
. Assuming you have code like this somewhere:
ProductNode *ptr = // Somehow initialize to the parent of the node to delete
.
.
deleteandnull(ptr->left);
You need to add this after the call to deletandnull
ptr->left = NULL;
Note that it is not necessary to test for NULL before calling delete
. It will do so itself. And since p
in deleteandnull
is a local, there is no point to setting it to NULL
. So the whole code might as well be reduced to:
ProductNode *ptr = // Somehow initialize to the parent of the node to delete
.
.
delete ptr->left;
ptr->left = NULL;
All that said, in modern C++ you should not be using bare pointers, new
and delete
. Prefer to use smart pointers, for instance as in the Boost library.
Upvotes: 1
Reputation: 979
use this instead :
void ProductCategory::deleteRightChild(ProductNode * p)
{
if(p->right!=NULL)
{
delete p->right;
p->right = NULL;
}
}
write an equivalent fonction for left child.
your function does not work because you dont change the content of the parent node. it still has the adress of the deleted node so (if this content was realllocated elsewhere and changed) it can access to it... !
but the memory is really deallocated.
Upvotes: 3