排序二叉树删除-3

3 普通节点的删除

3.1 删除的节点没有左子树，也没有右子树

测试用例1： 删除节点6

/* 
*                
*         10          ======>     10 
*        /  \                      \ 
*      6     15                     15 
*                                                          
*/  

static void test8()  
{  
    TREE_NODE* pTreeNode = NULL;  
    assert(TRUE == insert_node_into_tree(&pTreeNode, 10));  
    assert(TRUE == insert_node_into_tree(&pTreeNode, 6));  
    assert(6 == pTreeNode->left_child->data);  
    assert(TRUE == insert_node_into_tree(&pTreeNode, 15));  
    assert(TRUE == delete_node_from_tree(&pTreeNode, 6));  
    assert(NULL == pTreeNode->left_child);  
    free(pTreeNode->right_child);  
    free(pTreeNode);  
}  

测试用例2： 删除节点15

/* 
*                
*         10          ======>     10 
*        /  \                    /  
*      6     15                 6    
*                                                          
*/  

static void test9()  
{  
    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, 15));  
    assert(15 == pTreeNode->right_child->data);  
    assert(TRUE == delete_node_from_tree(&pTreeNode, 15));  
    assert(NULL == pTreeNode->right_child);  
    free(pTreeNode->right_child);  
    free(pTreeNode);  
}  

那么代码应该怎么编写呢？

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)  
{  
    TREE_NODE* pLeftMax;  

    if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){  
        if(pTreeNode == pTreeNode->parent->left_child)  
            pTreeNode->parent->left_child = NULL;  
        else  
            pTreeNode->parent->right_child = NULL;  
    }  

    free(pTreeNode);  
    return TRUE;  
}  

3.2 删除的节点有左子树，没有右子树

测试用例1： 测试节点6

/* 
*                
*         10          ======>     10 
*        /                      /  
*      6                      3    
*     / 
*    3                                                         
*/  

static void test10()  
{  
    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, 3));  
    assert(TRUE == delete_node_from_tree(&pTreeNode, 6));  
    assert(3 == pTreeNode->left_child->data);  
    assert(pTreeNode = pTreeNode->left_child->parent);  
    free(pTreeNode->left_child);  
    free(pTreeNode);  
}  

测试用例2： 删除节点15

/* 
*                
*         10          ======>     10 
*           \                       \ 
*           15                       12 
*            /                     
*           12                                                  
*/  

static void test11()  
{  
    TREE_NODE* pTreeNode = NULL;  
    assert(TRUE == insert_node_into_tree(&pTreeNode, 10));  
    assert(TRUE == insert_node_into_tree(&pTreeNode, 15));  
    assert(TRUE == insert_node_into_tree(&pTreeNode, 12));  
    assert(TRUE == delete_node_from_tree(&pTreeNode, 15));  
    assert(12 == pTreeNode->right_child->data);  
    assert(pTreeNode = pTreeNode->right_child->parent);  
    free(pTreeNode->right_child);  
    free(pTreeNode);  
}  

添加左子树不为空，右子树为空的处理代码，如下所示：

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)  
{  
    TREE_NODE* pLeftMax;  

    if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){  
        if(pTreeNode == pTreeNode->parent->left_child)  
            pTreeNode->parent->left_child = NULL;  
        else  
            pTreeNode->parent->right_child = NULL;  
    }else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){  
        pTreeNode->left_child->parent = pTreeNode->parent;  

        if(pTreeNode == pTreeNode->parent->left_child)  
            pTreeNode->parent->left_child = pTreeNode->left_child;  
        else  
            pTreeNode->parent->right_child = pTreeNode->left_child;  
    }  

    free(pTreeNode);  
    return TRUE;  
}  

3.3 删除的节点左子树为空，右子树节点不为空

测试用例1： 删除数据6

/* 
*                
*         10          ======>    10 
*        /                     /  
*      6                      8    
*       \ 
*        8                                                     
*/  

static void test12()  
{  
    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, 8));  
    assert(TRUE == delete_node_from_tree(&pTreeNode, 6));  
    assert(8 == pTreeNode->left_child->data);  
    assert(pTreeNode = pTreeNode->left_child->parent);  
    free(pTreeNode->left_child);  
    free(pTreeNode);  
}  

测试用例2： 删除数据15

/* 
*                
*        10          ======>    10 
*          \                      \  
*           15                     20  
*             \ 
*             20                                              
*/  

static void test13()  
{  
    TREE_NODE* pTreeNode = NULL;  
    assert(TRUE == insert_node_into_tree(&pTreeNode, 10));  
    assert(TRUE == insert_node_into_tree(&pTreeNode, 15));  
    assert(TRUE == insert_node_into_tree(&pTreeNode, 20));  
    assert(TRUE == delete_node_from_tree(&pTreeNode, 15));  
    assert(20 == pTreeNode->right_child->data);  
    assert(pTreeNode = pTreeNode->right_child->parent);  
    free(pTreeNode->right_child);  
    free(pTreeNode);  
} 

添加左子树为空，右子树不为空的处理情形。代码如下：

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)  
{  
    TREE_NODE* pLeftMax;  

    if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){  
        if(pTreeNode == pTreeNode->parent->left_child)  
            pTreeNode->parent->left_child = NULL;  
        else  
            pTreeNode->parent->right_child = NULL;  
    }else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){  
        pTreeNode->left_child->parent = pTreeNode->parent;  

        if(pTreeNode == pTreeNode->parent->left_child)  
            pTreeNode->parent->left_child = pTreeNode->left_child;  
        else  
            pTreeNode->parent->right_child = pTreeNode->left_child;  
    }else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){  
        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);  
}  

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->left_child->left_child);  
    free(pTreeNode->left_child->right_child);  
    free(pTreeNode->left_child);  
    free(pTreeNode);  
}  

那么针对这两种类型，我们的代码究竟应该怎么处理呢？

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)  
{  
    TREE_NODE* pLeftMax;  

    if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){  
        if(pTreeNode == pTreeNode->parent->left_child)  
            pTreeNode->parent->left_child = NULL;  
        else  
            pTreeNode->parent->right_child = NULL;  
    }else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){  
        pTreeNode->left_child->parent = pTreeNode->parent;  

        if(pTreeNode == pTreeNode->parent->left_child)  
            pTreeNode->parent->left_child = pTreeNode->left_child;  
        else  
            pTreeNode->parent->right_child = pTreeNode->left_child;  
    }else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){  
        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;  
    }else{  
        pLeftMax = find_max_node(pTreeNode->left_child);  
        if(pLeftMax == pTreeNode->left_child){  

            if(pTreeNode == pTreeNode->parent->left_child)  
                pTreeNode->parent->left_child = pTreeNode->left_child;  
            else  
                pTreeNode->parent->right_child = pTreeNode->left_child;  

            pTreeNode->left_child->parent = pTreeNode->parent;  
            pTreeNode->left_child->right_child = pTreeNode->right_child;  
            pTreeNode->right_child->parent = pTreeNode-> left_child;  

        }else{  
            pTreeNode->data = pLeftMax->data;  
            pLeftMax->parent->right_child = pLeftMax->left_child;  
            pLeftMax->left_child->parent = pLeftMax->parent;  
            pTreeNode = pLeftMax;  
        }  
    }  

    free(pTreeNode);  
    return TRUE;  
}  

结束总结：

上面的过程记录了我们的代码是怎么一步一步走过来的。最后我们给出一份完整的节点删除代码：

STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)  
{  
    TREE_NODE* pLeftMax;  

    if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){  
        if(pTreeNode == pTreeNode->parent->left_child)  
            pTreeNode->parent->left_child = NULL;  
        else  
            pTreeNode->parent->right_child = NULL;  
    }else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){  
        pTreeNode->left_child->parent = pTreeNode->parent;  

        if(pTreeNode == pTreeNode->parent->left_child)  
            pTreeNode->parent->left_child = pTreeNode->left_child;  
        else  
            pTreeNode->parent->right_child = pTreeNode->left_child;  
    }else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){  
        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;  
    }else{  
        pLeftMax = find_max_node(pTreeNode->left_child);  
        if(pLeftMax == pTreeNode->left_child){  

            if(pTreeNode == pTreeNode->parent->left_child)  
                pTreeNode->parent->left_child = pTreeNode->left_child;  
            else  
                pTreeNode->parent->right_child = pTreeNode->left_child;  

            pTreeNode->left_child->parent = pTreeNode->parent;  
            pTreeNode->left_child->right_child = pTreeNode->right_child;  
            pTreeNode->right_child->parent = pTreeNode-> left_child;  

        }else{  
            pTreeNode->data = pLeftMax->data;  
            pLeftMax->parent->right_child = pLeftMax->left_child;  
            pLeftMax->left_child->parent = pLeftMax->parent;             
            pTreeNode = pLeftMax;  
        }  
    }  

    free(pTreeNode);  
    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;  
                (*ppTreeNode)->parent = NULL;  
            }else{  
                pTreeNode->data = pLeftMax->data;  
                pLeftMax->parent->right_child = pLeftMax->left_child;  
                pLeftMax->left_child->parent = pLeftMax->parent;  
                pTreeNode = pLeftMax;  
            }  
        }  

        free(pTreeNode);  
        return TRUE;  
    }  

    return _delete_node_from_tree(pTreeNode);  
}