相比較節(jié)點(diǎn)的添加，平衡二叉樹(shù)的刪除要復(fù)雜一些。因?yàn)樵趧h除的過(guò)程中，你要考慮到不同的情況，針對(duì)每一種不同的情況，你要有針對(duì)性的反應(yīng)和調(diào)整。所以在代碼編寫(xiě)的過(guò)程中，我們可以一邊寫(xiě)代碼，一邊寫(xiě)測(cè)試用例。編寫(xiě)測(cè)試用例不光可以驗(yàn)證我們編寫(xiě)的代碼是否正確，還能不斷提高我們開(kāi)發(fā)代碼的自信心。這樣，即使我們?cè)陂_(kāi)發(fā)過(guò)程對(duì)代碼進(jìn)行修改或者優(yōu)化也不會(huì)擔(dān)心害怕。然而看起來(lái)編寫(xiě)測(cè)試用例是一個(gè)繁雜的過(guò)程，但是從長(zhǎng)期的收益來(lái)看，編寫(xiě)測(cè)試用例的成本是非常低廉的。

在排序二叉樹(shù)的刪除過(guò)程當(dāng)中，我們應(yīng)該怎么做呢？大家不用擔(dān)心，只要按照我們下面的介紹一步一步往下做就可以了，大體上分為下面三個(gè)步驟：

1）判斷參數(shù)的合法性，判斷參數(shù)是否在當(dāng)前的二叉樹(shù)當(dāng)中

2）刪除的節(jié)點(diǎn)是根節(jié)點(diǎn)，此時(shí)應(yīng)該怎么調(diào)整

3）刪除的節(jié)點(diǎn)是普通節(jié)點(diǎn)，此時(shí)又應(yīng)該怎么調(diào)整

閑話不多說(shuō)，下面看看我們的代碼是怎么設(shè)計(jì)的？

1、判斷參數(shù)的合法性，同時(shí)判斷當(dāng)前的二叉樹(shù)是否含有相關(guān)數(shù)據(jù)

1.1 判斷輸入?yún)?shù)是否合法

STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data)
{
    if(NULL == ppTreeNode || NULL == *ppTreeNode)
        return FALSE;
    return TRUE；
}

那么此時(shí)測(cè)試用例怎么寫(xiě)呢？

static void test1()
{
    TREE_NODE* pTreeNode = NULL;
    assert(FALSE == delete_node_from_tree(NULL, 10));
    assert(FALSE == delete_node_from_tree(&pTreeNode, 10));
}

注：上面的測(cè)試用例說(shuō)明當(dāng)指針為空或者指針的指針為空，函數(shù)返回FALSE。

1.2 判斷輸入數(shù)據(jù)是否存在

STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data)
{
    TREE_NODE* pTreeNode;

    if(NULL == ppTreeNode || NULL == *ppTreeNode)
        return FALSE;

    pTreeNode = find_data_in_tree_node(*ppTreeNode, data);
    if(NULL == pTreeNode)
        return FALSE;

    return TRUE;
}

此時(shí)，我們?cè)O(shè)計(jì)一種當(dāng)前指針合法，但是刪除數(shù)據(jù)不存在的測(cè)試用例。

static void test2()
{
    TREE_NODE* pTreeNode = NULL;
    pTreeNode = create_tree_node(10);
    assert(FALSE == delete_node_from_tree(&pTreeNode, 11));
    free(pTreeNode);
}

注：上面的測(cè)試用例根節(jié)點(diǎn)為10，但是刪除的數(shù)據(jù)為11，單步跟蹤，驗(yàn)證我們編寫(xiě)的代碼是否正確。

2、刪除的數(shù)據(jù)是根節(jié)點(diǎn)數(shù)據(jù)

2.1 刪除根數(shù)據(jù)時(shí)，根節(jié)點(diǎn)沒(méi)有左子樹(shù)，沒(méi)有右子樹(shù)情形

/*
*
*         10          ======>    NULL
*        /
*      NULL  NULL
*/

那么此時(shí)代碼應(yīng)該怎么寫(xiě)呢？我們可以試一試。

STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data)
{
    TREE_NODE* pTreeNode;

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

        free(pTreeNode);
        return TRUE;
    }

    return TRUE;
}

我們的代碼明顯越來(lái)越長(zhǎng)，我們要保持耐心。此時(shí)，該是我們添加新測(cè)試用例的時(shí)候了。

static void test3()
{
    TREE_NODE* pTreeNode = NULL;
    pTreeNode = create_tree_node(10);
    assert(TRUE == delete_node_from_tree(&pTreeNode, 10));
    assert(NULL == pTreeNode);
}

2.2 刪除根數(shù)據(jù)時(shí)，只有左子樹(shù)節(jié)點(diǎn)，沒(méi)有右子樹(shù)節(jié)點(diǎn)

/*
*
*         10          ======>    5
*        /                    /
*      5  NULL                3    NULL
*     /
*    3
*/

很明顯，我們只需要把用左子樹(shù)節(jié)點(diǎn)代替原來(lái)的根節(jié)點(diǎn)即可。

STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data)
{
    TREE_NODE* pTreeNode;

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

        free(pTreeNode);
        return TRUE;
    }

    return TRUE;
}

這個(gè)時(shí)候，我們可以添加新的測(cè)試用例，分別添加10、5、3，然后刪除10。

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

2.3 刪除根數(shù)據(jù)時(shí)，沒(méi)有左子樹(shù)節(jié)點(diǎn)，只有右子樹(shù)節(jié)點(diǎn)

/*
*
*         10          ======>    15
*        /                     /
*     NULL  15               NULL    20
*
*             20
*/

上面的代碼表示了節(jié)點(diǎn)的刪除過(guò)程。我們可以按照這個(gè)流程編寫(xiě)代碼。

STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data)
{
    TREE_NODE* pTreeNode;

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

        free(pTreeNode);
        return TRUE;
    }

    return TRUE;
}

添加測(cè)試用例，依次添加10、15、20，然后刪除數(shù)據(jù)10。

static void test5()
{
    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, 10));
    assert(15 == pTreeNode->data);
    assert(NULL == pTreeNode->parent);
    free(pTreeNode->right_child);
    free(pTreeNode);
}

上一篇：A*算法下一篇：圖結(jié)構(gòu)

在线观看不卡亚洲电影_亚洲妓女99综合网_91青青青亚洲娱乐在线观看_日韩无码高清综合久久

排序二叉樹(shù)刪除-1