}else{
pLeftMaxParent = get_parent_of_one(*ppTreeNode, pLeftMax);
pNode->data = pLeftMax->data;
pLeftMaxParent->right = NULL;
pNode = pLeftMax;
}
}
goto final;
}
pNode = _delete_node_from_tree(*ppTreeNode, pNode);
final:
set_link_for_delete(pNode);
free(pNode);
return TRUE;
}
void set_link_for_delete(TREE_NODE* pNode)
{
if(pNode->prev){
if(pNode->next){
pNode->prev->next = pNode->next;
pNode->next->prev = pNode->prev;
}else
pNode->prev->next = NULL;
}else{
if(pNode->next)
pNode->next->prev = NULL;
}
}
TREE_NODE* _delete_node_from_tree(TREE_NODE* root, TREE_NODE* pNode)
{
TREE_NODE* pLeftMax;
TREE_NODE* pLeftMaxParent;
TREE_NODE* pParent = get_parent_of_one(root, pNode);
if(NULL == pNode->left && NULL == pNode->right){
if(pNode == pParent->left)
pParent->left = NULL;
else
pParent->right = NULL;
}else if(NULL != pNode->left && NULL == pNode->right){
if (pNode == pParent->left)
pParent->left = pNode->left;
else
pParent->right = pNode->left;
}else if(NULL == pNode->left && NULL != pNode->right){
if(pNode == pParent->left)
pParent->left = pNode->right;
else
pParent->right = pNode->right;
}else{
pLeftMax = get_max_node_of_one(pNode->left);
if(pLeftMax == pNode->left){
pNode->left->right = pNode->right;
if(pNode == pParent->left)
pParent->left = pNode->left;
else
pParent->right = pNode->left;
}else{
pLeftMaxParent = get_parent_of_one(root, pLeftMax);
pNode->data = pLeftMax->data;
pLeftMaxParent->right = NULL;
pNode = pLeftMax;
}
}
return pNode;
}
STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data)
{
TREE_NODE* pNode;
TREE_NODE* pLeftMax;
TREE_NODE* pLeftMaxParent;
if(NULL == ppTreeNode || NULL == *ppTreeNode)
return FALSE;
if(NULL == (pNode = find_data_in_tree(*ppTreeNode, data)))
return FALSE;
if(pNode == *ppTreeNode){
if(NULL == pNode->left && NULL == pNode->right)
*ppTreeNode = NULL;
else if(NULL != pNode->left && NULL == pNode->right)
*ppTreeNode = pNode->left;
else if(NULL == pNode->left && NULL != pNode->right)
*ppTreeNode = pNode->right;
else {
pLeftMax = get_max_node_of_one(pNode->left);
if(pNode->left == pLeftMax){
pNode->left->right = pNode->right;