相比較節(jié)點的添加，平衡二叉樹的刪除要復雜一些。因為在刪除的過程中，你要考慮到不同的情況，針對每一種不同的情況，你要有針對性的反應和調整。所以在代碼編寫的過程中，我們可以一邊寫代碼，一邊寫測試用例。編寫測試用例不光可以驗證我們編寫的代碼是否正確，還能不斷提高我們開發(fā)代碼的自信心。這樣，即使我們在開發(fā)過程對代碼進行修改或者優(yōu)化也不會擔心害怕。然而看起來編寫測試用例是一個繁雜的過程，但是從長期的收益來看，編寫測試用例的成本是非常低廉的。

在排序二叉樹的刪除過程當中，我們應該怎么做呢？大家不用擔心，只要按照我們下面的介紹一步一步往下做就可以了，大體上分為下面三個步驟：

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

2）刪除的節(jié)點是根節(jié)點，此時應該怎么調整

3）刪除的節(jié)點是普通節(jié)點，此時又應該怎么調整

閑話不多說，下面看看我們的代碼是怎么設計的？

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

1.1 判斷輸入參數(shù)是否合法

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

那么此時測試用例怎么寫呢？

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

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

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

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ù)據不存在的測試用例。

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

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

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

2.1 刪除根數(shù)據時，根節(jié)點沒有左子樹，沒有右子樹情形

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

那么此時代碼應該怎么寫呢？我們可以試一試。

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

我們的代碼明顯越來越長，我們要保持耐心。此時，該是我們添加新測試用例的時候了。

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ù)據時，只有左子樹節(jié)點，沒有右子樹節(jié)點

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

很明顯，我們只需要把用左子樹節(jié)點代替原來的根節(jié)點即可。

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

這個時候，我們可以添加新的測試用例，分別添加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ù)據時，沒有左子樹節(jié)點，只有右子樹節(jié)點

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

上面的代碼表示了節(jié)點的刪除過程。我們可以按照這個流程編寫代碼。

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

添加測試用例，依次添加10、15、20，然后刪除數(shù)據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);
}

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

排序二叉樹刪除-1