pTreeNode->right_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->right_child;
else
pTreeNode->parent->right_child = pTreeNode->right_child;
}
free(pTreeNode);
return TRUE;
}
3.4 删除的节点左右子树均不为空，不过又要分为两种情形：
1） 左节点是删除节点左侧的最大节点 （删除节点6）
/*
*
* 10 ======> 10
* / /
* 6 5
* / \ \
* 5 8 8
*/
static void test14()
{
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, 8));
assert(TRUE == delete_node_from_tree(&pTreeNode, 6));
assert(5 == pTreeNode->left_child->data);
assert(pTreeNode = pTreeNode->left_child->parent);
assert( 8 == pTreeNode->left_child->right_child->data);
assert(pTreeNode->left_child = pTreeNode->left_child->right_child->parent);
free(pTreeNode->left_child->right_child);
free(pTreeNode->left_child);
free(pTreeNode);
}
/*
*
* 10 ======> 10
* / /
* 6 5
* / \ \
* 5 8 8
*/
static void test14()
{
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, 8));
assert(TRUE == delete_node_from_tree(&pTreeNode, 6));
assert(5 == pTreeNode->left_child->data);
assert(pTreeNode = pTreeNode->left_child->parent);
assert( 8 == pTreeNode->left_child->right_child->data);
assert(pTreeNode->left_child = pTreeNode->left_child->right_child->parent);
free(pTreeNode->left_child->right_child);
free(pTreeNode->left_child);
free(pTreeNode);
} 2） 左节点不是删除节点左侧的最大节点（删除节点5）
/*
*
* 10 ======> 10
* / /
* 5 4
* / \ / \
* 2 6 2 6
* \
* 4
*/
static void test15()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 5));
assert(TRUE == insert_node_into_tree(&pTreeNode, 2));
assert(TRUE == insert_node_into_tree(&pTreeNode, 4));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == delete_node_from_tree(&pTreeNode, 5));
assert(4 == pTreeNode->left_child->data);
assert(NULL == pTreeNode->left_child->left_child->right_child);
free(pTreeNode-