【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
相比較節點的添加，平衡二叉樹的刪除要復雜一些。因為在刪除的過程中，你要考慮到不同的情況，針對每一種不同的情況，你要有針對性的反應和調整。所以在代碼編寫的過程中，我們可以一邊寫代碼，一邊寫測試用例。編寫測試用例不光可以驗證我們編寫的代碼是否正確，還能不斷提高我們開發代碼的自信心。這樣，即使我們在開發過程對代碼進行修改或者優化也不會擔心害怕。然而看起來編寫測試用例是一個繁雜的過程，但是從長期的收益來看，編寫測試用例的成本是非常低廉的。
在排序二叉樹的刪除過程當中，我們應該怎麼做呢？大家不用擔心，只要按照我們下面的介紹一步一步往下做就可以了，大體上分為下面三個步驟：
1）判斷參數的合法性，判斷參數是否在當前的二叉樹當中
2）刪除的節點是根節點，此時應該怎麼調整
3）刪除的節點是普通節點，此時又應該怎麼調整
閒話不多說，下面看看我們的代碼是怎麼設計的？
1、判斷參數的合法性，同時判斷當前的二叉樹是否含有相關數據
1.1 判斷輸入參數是否合法
STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data)
{
if(NULL == ppTreeNode || NULL == *ppTreeNode)
return FALSE;
return TRUE；
}
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));
}
static void test1()
{
TREE_NODE* pTreeNode = NULL;
assert(FALSE == delete_node_from_tree(NULL, 10));
assert(FALSE == delete_node_from_tree(&pTreeNode, 10));
} 注： 上面的測試用例說明當指針為空或者指針的指針為空，函數返回FALSE。
1.2 判斷輸入數據是否存在
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;
}
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;
} 此時，我們設計一種當前指針合法，但是刪除數據不存在的測試用例。
static void test2()
{
TREE_NODE* pTreeNode = NULL;
pTreeNode = create_tree_node(10);
assert(FALSE == delete_node_from_tree(&pTreeNode, 11));
free(pTreeNode);
}
static void test2()
{
TREE_NODE* pTreeNode = NULL;
pTreeNode = create_tree_node(10);
assert(FALSE == delete_node_from_tree(&pTreeNode, 11));
free(pTreeNode);
} 注： 上面的測試用例根節點為10，但是刪除的數據為11，單步跟蹤，驗證我們編寫的代碼是否正確。
2、刪除的數據是根節點數據
2.1 刪除根數據時，根節點沒有左子樹，沒有右子樹情形
/*
*
* 10 ======> NULL
* / \
* NULL NULL
*/
/*
*
* 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;
}
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);
}
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 刪除根數據時，只有左子樹節點，沒有右子樹節點
/*
*
* 10 ======> 5
* / \ / \
* 5 NULL 3 NULL
* /
* 3
*/
/*
*
* 10 ======> 5
* / \ / \
* 5 NULL 3 NULL
* /
* 3
*/ 很明顯，我們只需要把用左子樹節點代替原來的根節點即可。
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;
}
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);
}
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 刪除根數據時，沒有左子樹節點，只有右子樹節點
/*
*
* 10 ======> 15
* / \ / \
* NULL 15 NULL 20
* \
* 20
*/
/*
*
* 10 ======> 15
* / \ / \
* NULL 15 NULL 20
* \
* 20
*/ 上面的代碼表示了節點的刪除過程。我們可以按照這個流程編寫代碼。
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;
}
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，然後刪除數據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);
}
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);
}
2.4刪除數據的左右節點都存在
