【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】
2.4 删除节点的左右子树都存在，此时又会分成两种情形
1）左节点是当前左子树的最大节点，此时只需要用左节点代替根节点即可
/*
*
* 10 ======> 6
* / \ / \
* 6 15 5 15
* /
* 5
*/
/*
*
* 10 ======> 6
* / \ / \
* 6 15 5 15
* /
* 5
*/ 代码该怎么编写呢？
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)->right_child = pTreeNode->right_child;
(*ppTreeNode)->right_child->parent = *ppTreeNode;
(*ppTreeNode)->parent = NULL;
}
}
free(pTreeNode);
return TRUE;
}
return TRUE;
}
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)->right_child = pTreeNode->right_child;
(*ppTreeNode)->right_child->parent = *ppTreeNode;