二叉樹的節(jié)點(diǎn)插入比較簡(jiǎn)單。一般來說，二叉樹的插入主要分為以下兩個(gè)步驟：

1） 對(duì)當(dāng)前的參數(shù)進(jìn)行判斷，因?yàn)樾枰紤]到頭結(jié)點(diǎn)，所以我們使用了指針的指針作為函數(shù)的輸入?yún)?shù)

2） 分情況討論：

如果原來二叉樹連根節(jié)點(diǎn)都沒有，那么這個(gè)新插入的數(shù)據(jù)就是根節(jié)點(diǎn)；

如果原來的二叉樹有根節(jié)點(diǎn)，那我們判斷這個(gè)數(shù)據(jù)是否存在過，如果存在，那么返回；如果不存在，那么繼續(xù)插入數(shù)據(jù)。

那繼續(xù)插入的數(shù)據(jù)怎么保存呢？又要分三種情況：

1）如果插入的數(shù)據(jù)小于當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)，那么往當(dāng)前節(jié)點(diǎn)的左子樹方向繼續(xù)尋找插入位置

2）如果插入的數(shù)據(jù)大于當(dāng)前插入的位置，那么往當(dāng)前節(jié)點(diǎn)的右子樹方向繼續(xù)尋找插入位置

3）如果方向當(dāng)前的節(jié)點(diǎn)為空，那么表示插入的位置找到了，插入數(shù)據(jù)即可

算法說了這么多，下面即開始練習(xí)我們的代碼：

a）判斷輸入數(shù)據(jù)的合法性

STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
    if(NULL == ppTreeNode)
        return FALSE;

    return TRUE;
}

此時(shí)，可以用一個(gè)測(cè)試用例驗(yàn)證一下

static void test1()
{
    assert(FALSE == insert_node_into_tree(NULL, 10));
}

b）判斷當(dāng)前根節(jié)點(diǎn)是否存在，修改代碼

STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
    if(NULL == ppTreeNode)
        return FALSE;

    if(NULL == *ppTreeNode){
        *ppTreeNode = (TREE_NODE*)create_tree_node(data);
        assert(NULL != *ppTreeNode);
        return TRUE;
    }

    return TRUE;
}

修改了代碼，少不了測(cè)試用例的添加。

static void test2()
{
    TREE_NODE* pTreeNode = NULL;
    assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
    assert(10 == pTreeNode->data);
    free(pTreeNode);
}

c）上面考慮了沒有根節(jié)點(diǎn)的情況，那么如果根節(jié)點(diǎn)存在呢？

STATUS _insert_node_into_tree(TREE_NODE** ppTreeNode, int data, TREE_NODE* pParent)
{
    if(NULL == *ppTreeNode){
        *ppTreeNode = create_tree_node(data);
        assert(NULL != *ppTreeNode);
        (*ppTreeNode)->parent = pParent;
        return TRUE;
    }

    if(data < (*ppTreeNode)->data)
        return _insert_node_into_tree(&(*ppTreeNode)->left_child, data, *ppTreeNode);
    else
        return _insert_node_into_tree(&(*ppTreeNode)->right_child, data, *ppTreeNode);
}

STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
    if(NULL == ppTreeNode)
        return FALSE;

    if(NULL == *ppTreeNode){
        *ppTreeNode = (TREE_NODE*)create_tree_node(data);
        assert(NULL != *ppTreeNode);
        return TRUE;
    }

    return _insert_node_into_tree(ppTreeNode, data, NULL);
}

上面的代碼已經(jīng)考慮了不是根節(jié)點(diǎn)的情況。我們可以據(jù)此添加一個(gè)測(cè)試用例。

static void test3()
{
    TREE_NODE* pTreeNode = NULL;
    assert(TRUE == insert_node_into_tree(&pTreeNode, 9));
    assert(TRUE == insert_node_into_tree(&pTreeNode, 8));
    assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
    assert(9 == pTreeNode->data);
    assert(8 == pTreeNode->left_child->data);
    assert(10 == pTreeNode->right_child->data);
    free(pTreeNode->left_child);
    free(pTreeNode->right_child);
    free(pTreeNode);
}

由于上面的代碼是遞歸代碼，為了實(shí)現(xiàn)代碼的健壯性和完畢性，其實(shí)我們?cè)O(shè)計(jì)測(cè)試用例的時(shí)候應(yīng)該至少包括9個(gè)測(cè)試用例：

（1） 參數(shù)非法

（2） 根節(jié)點(diǎn)不存在

（3）根節(jié)點(diǎn)存在，但是插入的數(shù)據(jù)已經(jīng)存在

（4）根節(jié)點(diǎn)存在，插入數(shù)據(jù)為 9， 8

（5）根節(jié)點(diǎn)存在， 插入數(shù)據(jù)為9， 10

（6）根節(jié)點(diǎn)存在，插入數(shù)據(jù)為9，8， 7

（7）根節(jié)點(diǎn)存在，插入數(shù)據(jù)為9，7，8

（8）根節(jié)點(diǎn)存在，插入數(shù)據(jù)為7，8， 9

（9）根節(jié)點(diǎn)存在，插入數(shù)據(jù)為7，9，8