2.4 刪除節(jié)點(diǎn)的左右子樹都存在，此時(shí)又會(huì)分成兩種情形

1）左節(jié)點(diǎn)是當(dāng)前左子樹的最大節(jié)點(diǎn)，此時(shí)只需要用左節(jié)點(diǎn)代替根節(jié)點(diǎn)即可

/*
*
*         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;
}

上面的代碼中添加的內(nèi)容表示了我們介紹的這一情形。為此，我們可以設(shè)計(jì)一種測(cè)試用例。依次插入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);
}

如果上面的測(cè)試用例通過，表示我們添加的代碼沒有問題。

2）左節(jié)點(diǎn)不是當(dāng)前左子樹的最大節(jié)點(diǎn)，情形如下所示

/*
*
*         10          ======>     8
*        /                     /
*      6     15               5     15
*
*        8
*/

此時(shí)，我們應(yīng)該用10左側(cè)的最大節(jié)點(diǎn)8代替刪除的節(jié)點(diǎn)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)->right_child = pTreeNode->right_child;
                (*ppTreeNode)->right_child->parent = *ppTreeNode;
                (*ppTreeNode)->parent = NULL;
            }else{
                pTreeNode->data = pLeftMax->data;
                pLeftMax->parent->right_child = NULL;
                pTreeNode = pLeftMax;
            }
        }

        free(pTreeNode);
        return TRUE;
    }

    return TRUE;
}

那么，這個(gè)場景下面測(cè)試用例又該怎么設(shè)計(jì)呢？其實(shí)只需要按照上面給出的示意圖進(jìn)行即可。依次插入數(shù)據(jù)10、6、8、15，然后刪除數(shù)據(jù)10。

static void test7()
{
    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 == insert_node_into_tree(&pTreeNode, 15));
    assert(TRUE == delete_node_from_tree(&pTreeNode, 10));
    assert(8 == pTreeNode->data);
    assert(NULL == pTreeNode->parent);
    assert(NULL == pTreeNode->left_child->right_child);
    assert(NULL == pTreeNode->parent);
    free(pTreeNode->left_child);
    free(pTreeNode->right_child);
    free(pTreeNode);
}

至此，刪除節(jié)點(diǎn)為根節(jié)點(diǎn)的情形全部討論完畢，那么如果刪除的節(jié)點(diǎn)是普通節(jié)點(diǎn)呢，那應(yīng)該怎么解決呢？

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);
}

我們?cè)诋?dāng)前函數(shù)的最后一行添加_delete_node_from_tree，這個(gè)函數(shù)用來處理普通節(jié)點(diǎn)的刪除情況，我們會(huì)在下面一篇博客中繼續(xù)介紹。

3、 普通節(jié)點(diǎn)的刪除