【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
二叉樹的節點插入比較簡單。一般來說，二叉樹的插入主要分為以下兩個步驟：
1） 對當前的參數進行判斷，因為需要考慮到頭結點，所以我們使用了指針的指針作為函數的輸入參數
2） 分情況討論：
如果原來二叉樹連根節點都沒有，那麼這個新插入的數據就是根節點；
如果原來的二叉樹有根節點，那我們判斷這個數據是否存在過，如果存在，那麼返回；如果不存在，那麼繼續插入數據。
那繼續插入的數據怎麼保存呢？又要分三種情況：
1）如果插入的數據小於當前節點的數據，那麼往當前節點的左子樹方向繼續尋找插入位置
2）如果插入的數據大於當前插入的位置，那麼往當前節點的右子樹方向繼續尋找插入位置
3）如果方向當前的節點為空，那麼表示插入的位置找到了，插入數據即可
算法說了這麼多，下面即開始練習我們的代碼：
a）判斷輸入數據的合法性
STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
if(NULL == ppTreeNode)
return FALSE;
return TRUE;
}
STATUS insert_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
if(NULL == ppTreeNode)
return FALSE;
return TRUE;
} 此時，可以用一個測試用例驗證一下
static void test1()
{
assert(FALSE == insert_node_into_tree(NULL, 10));
}
static void test1()
{
assert(FALSE == insert_node_into_tree(NULL, 10));
}
b）判斷當前根節點是否存在，修改代碼
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;
}
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;
} 修改了代碼，少不了測試用例的添加。
static void test2()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(10 == pTreeNode->data);
free(pTreeNode);
}
static void test2()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(10 == pTreeNode->data);
free(pTreeNode);
}
c）上面考慮了沒有根節點的情況，那麼如果根節點存在呢？
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);
}
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);
}
上面的代碼已經考慮了不是根節點的情況。我們可以據此添加一個測試用例。
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);
}
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);
} 由於上面的代碼是遞歸代碼，為了實現代碼的健壯性和完畢性，其實我們設計測試用例的時候應該至少包括9個測試用例：
（1） 參數非法
（2） 根節點不存在
（3）根節點存在，但是插入的數據已經存在
（4）根節點存在，插入數據為9，8
（5）根節點存在， 插入數據為9，10
（6）根節點存在，插入數據為9，8，7
（7）根節點存在，插入數據為9，7，8
（8）根節點存在，插入數據為7，8，9
（9）根節點存在，插入數據為7，9，8
【預告： 下面一篇博客主要介紹二叉樹的節點刪除】
