while(1){
if(data < pHead->data){
if(pHead->left){
pHead = pHead->left;
}else{
pNode = create_new_node(data);
pHead->left = pNode;
break;
}
}else{
if(pHead->right){
pHead = pHead->right;
}else{
pNode = create_new_node(data);
pHead->right = pNode;
break;
}
}
}
set_link_for_insert(pHead, 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;
*ppTreeNode = p