(*ppTreeNode)->parent = NULL;
}
}
free(pTreeNode);
return TRUE;
}
return TRUE;
} 上面的代码中添加的内容表示了我们介绍的这一情形。为此，我们可以设计一种测试用例。依次插入10、6、5、15，然后删除10即可。
static void test6()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == insert_node_into_tree(&pTreeNode, 5));
assert(TRUE == insert_node_into_tree(&pTreeNode, 15));
assert(TRUE == delete_node_from_tree(&pTreeNode, 10));
assert(6 == pTreeNode->data);
assert(NULL == pTreeNode->parent);
assert(15 == pTreeNode->right_child->data);
assert(pTreeNode = pTreeNode->right_child->parent);
assert(NULL == pTreeNode->parent);
free(pTreeNode->left_child);
free(pTreeNode->right_child);
free(pTreeNode);
}
static void test6()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == insert_node_into_tree(&pTreeNode, 5));
assert(TRUE == insert_node_into_tree(&pTreeNode, 15));
assert(TRUE == delete_node_from_tree(&pTreeNode, 10));
assert(6 == pTreeNode->data);
assert(NULL == pTreeNode->parent);
assert(15 == pTreeNode->right_child->data);
assert(pTreeNode = pTreeNode->right_child->parent);
assert(NULL == pTreeNode->parent);
free(pTreeNode->left_child);
free(pTreeNode->right_child);
free(pTreeNode);
} 如果上面的测试用例通过，表示我们添加的代码没有问题。
2）左节点不是当前左子树的最大节点，情形如下所示
/*
*
* 10 ======> 8
* / \ / \
* 6 15 5 15
* \
* 8
*/
/*
*
* 10 ======> 8
* / \ / \
* 6 15 5 15
* \
* 8
*/ 此时，我们应该用10左侧的最大节点8代替删除的节点10即可。
STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data)
{
TREE_NODE* pTreeNode;
TREE_NODE* pLeftMax;
if(NULL == ppTreeNode || NULL == *ppTreeNode)
return FALSE;
pTreeNode = find_data_in_tree_node(*ppTreeNode, data);
if(NULL == pTreeNode)
return FALSE;
if(*ppTreeNode == pTreeNode){
if(NULL == pTreeNode->left_child && NULL == pTreeNode->right_child){
*ppTreeNode = NULL;
}else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){
*ppTreeNode = pTreeNode->left_child;
pTreeNode->left_child->parent = NULL;
}else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){
*ppTreeNode = pTreeNode->right_child;
pTreeNode->right_child->parent = NULL;
}else{
pLeftMax = find_max_node(pTreeNode->left_child);
if(pLeftMax == pTreeNode->left_child){
*ppTreeNode = pTreeNode->left_child;
(*ppTreeNode)->righ