struct node* delete(struct node* node, struct node* pnode, int target)
{
struct node* rchild;
struct node* rchildparent;
if(node==NULL)
{
return(node);
}
if(target == node->data)
{
if(node->left == NULL && node->right == NULL) //leaf node
{
if(pnode == NULL) //special case deleting the root node
{
return(NULL);
}
if(pnode->left == node)
{
pnode->left = NULL;
}
else
{
pnode->right = NULL;
}
}
else
{
if(node->left ==NULL) //one child
{
if(pnode == NULL) //deleting root having no left child
{
struct node* temp = node;
node = node->right;
return(node);
}
if(pnode->left == node)
{
pnode->left = node->right;
}
else
{
pnode->right = node->right;
}
}
else if(node->right ==NULL) //one child
{
if(pnode == NULL) //deleting root having no right child
{
struct node* temp = node;
node = node->left;
return(node);
}
if(pnode->left == node)
{
pnode->left = node->left;
}
else
{
pnode->right = node->left;
}
}
else //two children
{
rchild = node->right;
rchildparent=node;
while(rchild->left != NULL)
{
rchildparent=rchild;
rchild = rchild->left;
}
node->data=rchild->data;
if(rchildparent == node)
{
rchildparent->right=rchild->right;
}
else
{
rchildparent->left=NULL;
}
}
}
return(node);
}
else if(target < node->data)
{
return(delete(node->left,node,target));
}
else
{
return(delete(node->right,node,target));
}
}
c3RydWN0IG5vZGUqIGRlbGV0ZShzdHJ1Y3Qgbm9kZSogbm9kZSwgc3RydWN0IG5vZGUqIHBub2RlLCBpbnQgdGFyZ2V0KQp7CiAgICBzdHJ1Y3Qgbm9kZSogcmNoaWxkOwogICAgc3RydWN0IG5vZGUqIHJjaGlsZHBhcmVudDsKICAgIGlmKG5vZGU9PU5VTEwpCiAgICB7CiAgICAgICAgcmV0dXJuKG5vZGUpOwogICAgfQoKICAgIGlmKHRhcmdldCA9PSBub2RlLT5kYXRhKQogICAgewogICAgICAgIGlmKG5vZGUtPmxlZnQgPT0gTlVMTCAmJiBub2RlLT5yaWdodCA9PSBOVUxMKSAvL2xlYWYgbm9kZQogICAgICAgIHsKICAgICAgICAgICAgaWYocG5vZGUgPT0gTlVMTCkgLy9zcGVjaWFsIGNhc2UgZGVsZXRpbmcgdGhlIHJvb3Qgbm9kZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBmcmVlKG5vZGUpOwogICAgICAgICAgICAgICAgcmV0dXJuKE5VTEwpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKHBub2RlLT5sZWZ0ID09IG5vZGUpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHBub2RlLT5sZWZ0ID0gTlVMTDsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHBub2RlLT5yaWdodCA9IE5VTEw7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZnJlZShub2RlKTsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgaWYobm9kZS0+bGVmdCA9PU5VTEwpIC8vb25lIGNoaWxkCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGlmKHBub2RlID09IE5VTEwpIC8vZGVsZXRpbmcgcm9vdCBoYXZpbmcgbm8gbGVmdCBjaGlsZAogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHN0cnVjdCBub2RlKiB0ZW1wID0gbm9kZTsKICAgICAgICAgICAgICAgICAgICBub2RlID0gbm9kZS0+cmlnaHQ7CiAgICAgICAgICAgICAgICAgICAgZnJlZSh0ZW1wKTsKICAgICAgICAgICAgICAgICAgICByZXR1cm4obm9kZSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBpZihwbm9kZS0+bGVmdCA9PSBub2RlKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHBub2RlLT5sZWZ0ID0gbm9kZS0+cmlnaHQ7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcG5vZGUtPnJpZ2h0ID0gbm9kZS0+cmlnaHQ7CiAgICAgICAgICAgICAgICB9ICAgCiAgICAgICAgICAgICAgICBmcmVlKG5vZGUpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGVsc2UgaWYobm9kZS0+cmlnaHQgPT1OVUxMKSAvL29uZSBjaGlsZAogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpZihwbm9kZSA9PSBOVUxMKSAvL2RlbGV0aW5nIHJvb3QgaGF2aW5nIG5vIHJpZ2h0IGNoaWxkCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgc3RydWN0IG5vZGUqIHRlbXAgPSBub2RlOwogICAgICAgICAgICAgICAgICAgIG5vZGUgPSBub2RlLT5sZWZ0OwogICAgICAgICAgICAgICAgICAgIGZyZWUodGVtcCk7CiAgICAgICAgICAgICAgICAgICAgcmV0dXJuKG5vZGUpOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaWYocG5vZGUtPmxlZnQgPT0gbm9kZSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBwbm9kZS0+bGVmdCA9IG5vZGUtPmxlZnQ7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcG5vZGUtPnJpZ2h0ID0gbm9kZS0+bGVmdDsKICAgICAgICAgICAgICAgIH0gICAKICAgICAgICAgICAgICAgIGZyZWUobm9kZSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZSAvL3R3byBjaGlsZHJlbgogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICByY2hpbGQgPSBub2RlLT5yaWdodDsKICAgICAgICAgICAgICAgIHJjaGlsZHBhcmVudD1ub2RlOwogICAgICAgICAgICAgICAgd2hpbGUocmNoaWxkLT5sZWZ0ICE9IE5VTEwpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgcmNoaWxkcGFyZW50PXJjaGlsZDsKICAgICAgICAgICAgICAgICAgICByY2hpbGQgPSByY2hpbGQtPmxlZnQ7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICBub2RlLT5kYXRhPXJjaGlsZC0+ZGF0YTsKICAgICAgICAgICAgICAgIGlmKHJjaGlsZHBhcmVudCA9PSBub2RlKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIHJjaGlsZHBhcmVudC0+cmlnaHQ9cmNoaWxkLT5yaWdodDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICByY2hpbGRwYXJlbnQtPmxlZnQ9TlVMTDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIGZyZWUocmNoaWxkKTsKICAgICAgICAgICAgfQogICAgICAgIH0gICAKICAgICAgICByZXR1cm4obm9kZSk7CiAgICB9CiAgICBlbHNlIGlmKHRhcmdldCA8IG5vZGUtPmRhdGEpCiAgICB7CiAgICAgICAgcmV0dXJuKGRlbGV0ZShub2RlLT5sZWZ0LG5vZGUsdGFyZ2V0KSk7CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgcmV0dXJuKGRlbGV0ZShub2RlLT5yaWdodCxub2RlLHRhcmdldCkpOwogICAgfQp9Cg==