【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
3 普通節點的刪除
3.1 刪除的節點沒有左子樹，也沒有右子樹
測試用例1： 刪除節點6
/*
*
* 10 ======> 10
* / \ \
* 6 15 15
*
*/
static void test8()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(6 == pTreeNode->left_child->data);
assert(TRUE == insert_node_into_tree(&pTreeNode, 15));
assert(TRUE == delete_node_from_tree(&pTreeNode, 6));
assert(NULL == pTreeNode->left_child);
free(pTreeNode->right_child);
free(pTreeNode);
}
/*
*
* 10 ======> 10
* / \ \
* 6 15 15
*
*/
static void test8()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(6 == pTreeNode->left_child->data);
assert(TRUE == insert_node_into_tree(&pTreeNode, 15));
assert(TRUE == delete_node_from_tree(&pTreeNode, 6));
assert(NULL == pTreeNode->left_child);
free(pTreeNode->right_child);
free(pTreeNode);
} 測試用例2： 刪除節點15
/*
*
* 10 ======> 10
* / \ /
* 6 15 6
*
*/
static void test9()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == insert_node_into_tree(&pTreeNode, 15));
assert(15 == pTreeNode->right_child->data);
assert(TRUE == delete_node_from_tree(&pTreeNode, 15));
assert(NULL == pTreeNode->right_child);
free(pTreeNode->right_child);
free(pTreeNode);
}
/*
*
* 10 ======> 10
* / \ /
* 6 15 6
*
*/
static void test9()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == insert_node_into_tree(&pTreeNode, 15));
assert(15 == pTreeNode->right_child->data);
assert(TRUE == delete_node_from_tree(&pTreeNode, 15));
assert(NULL == pTreeNode->right_child);
free(pTreeNode->right_child);
free(pTreeNode);
} 那麼代碼應該怎麼編寫呢？
STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)
{
TREE_NODE* pLeftMax;
if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = NULL;
else
pTreeNode->parent->right_child = NULL;
}
free(pTreeNode);
return TRUE;
}
STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)
{
TREE_NODE* pLeftMax;
if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = NULL;
else
pTreeNode->parent->right_child = NULL;
}
free(pTreeNode);
return TRUE;
}
3.2 刪除的節點有左子樹，沒有右子樹
測試用例1： 測試節點6
/*
*
* 10 ======> 10
* / /
* 6 3
* /
* 3
*/
static void test10()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == insert_node_into_tree(&pTreeNode, 3));
assert(TRUE == delete_node_from_tree(&pTreeNode, 6));
assert(3 == pTreeNode->left_child->data);
assert(pTreeNode = pTreeNode->left_child->parent);
free(pTreeNode->left_child);
free(pTreeNode);
}
/*
*
* 10 ======> 10
* / /
* 6 3
* /
* 3
*/
static void test10()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == insert_node_into_tree(&pTreeNode, 3));
assert(TRUE == delete_node_from_tree(&pTreeNode, 6));
assert(3 == pTreeNode->left_child->data);
assert(pTreeNode = pTreeNode->left_child->parent);
free(pTreeNode->left_child);
free(pTreeNode);
} 測試用例2： 刪除節點15
/*
*
* 10 ======> 10
* \ \
* 15 12
* /
* 12
*/
static void test11()
{
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, 12));
assert(TRUE == delete_node_from_tree(&pTreeNode, 15));
assert(12 == pTreeNode->right_child->data);
assert(pTreeNode = pTreeNode->right_child->parent);
free(pTreeNode->right_child);
free(pTreeNode);
}
/*
*
* 10 ======> 10
* \ \
* 15 12
* /
* 12
*/
static void test11()
{
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, 12));
assert(TRUE == delete_node_from_tree(&pTreeNode, 15));
assert(12 == pTreeNode->right_child->data);
assert(pTreeNode = pTreeNode->right_child->parent);
free(pTreeNode->right_child);
free(pTreeNode);
} 添加左子樹不為空，右子樹為空的處理代碼，如下所示：
STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)
{
TREE_NODE* pLeftMax;
if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = NULL;
else
pTreeNode->parent->right_child = NULL;
}else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){
pTreeNode->left_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->left_child;
else
pTreeNode->parent->right_child = pTreeNode->left_child;
}
free(pTreeNode);
return TRUE;
}
STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)
{
TREE_NODE* pLeftMax;
if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = NULL;
else
pTreeNode->parent->right_child = NULL;
}else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){
pTreeNode->left_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->left_child;
else
pTreeNode->parent->right_child = pTreeNode->left_child;
}
free(pTreeNode);
return TRUE;
}
3.3 刪除的節點左子樹為空，右子樹節點不為空
測試用例1： 刪除數據6
/*
*
* 10 ======> 10
* / /
* 6 8
* \
* 8
*/
static void test12()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == insert_node_into_tree(&pTreeNode, 8));
assert(TRUE == delete_node_from_tree(&pTreeNode, 6));
assert(8 == pTreeNode->left_child->data);
assert(pTreeNode = pTreeNode->left_child->parent);
free(pTreeNode->left_child);
free(pTreeNode);
}
/*
*
* 10 ======> 10
* / /
* 6 8
* \
* 8
*/
static void test12()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == insert_node_into_tree(&pTreeNode, 8));
assert(TRUE == delete_node_from_tree(&pTreeNode, 6));
assert(8 == pTreeNode->left_child->data);
assert(pTreeNode = pTreeNode->left_child->parent);
free(pTreeNode->left_child);
free(pTreeNode);
} 測試用例2： 刪除數據15
/*
*
* 10 ======> 10
* \ \
* 15 20
* \
* 20
*/
static void test13()
{
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, 15));
assert(20 == pTreeNode->right_child->data);
assert(pTreeNode = pTreeNode->right_child->parent);
free(pTreeNode->right_child);
free(pTreeNode);
}
/*
*
* 10 ======> 10
* \ \
* 15 20
* \
* 20
*/
static void test13()
{
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, 15));
assert(20 == pTreeNode->right_child->data);
assert(pTreeNode = pTreeNode->right_child->parent);
free(pTreeNode->right_child);
free(pTreeNode);
} 添加左子樹為空，右子樹不為空的處理情形。代碼如下：
STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)
{
TREE_NODE* pLeftMax;
if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = NULL;
else
pTreeNode->parent->right_child = NULL;
}else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){
pTreeNode->left_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->left_child;
else
pTreeNode->parent->right_child = pTreeNode->left_child;
}else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){
pTreeNode->right_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->right_child;
else
pTreeNode->parent->right_child = pTreeNode->right_child;
}
free(pTreeNode);
return TRUE;
}
STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)
{
TREE_NODE* pLeftMax;
if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = NULL;
else
pTreeNode->parent->right_child = NULL;
}else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){
pTreeNode->left_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->left_child;
else
pTreeNode->parent->right_child = pTreeNode->left_child;
}else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){
pTreeNode->right_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->right_child;
else
pTreeNode->parent->right_child = pTreeNode->right_child;
}
free(pTreeNode);
return TRUE;
}
3.4 刪除的節點左右子樹均不為空，不過又要分為兩種情形：
1） 左節點是刪除節點左側的最大節點 （刪除節點6）
/*
*
* 10 ======> 10
* / /
* 6 5
* / \ \
* 5 8 8
*/
static void test14()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == insert_node_into_tree(&pTreeNode, 5));
assert(TRUE == insert_node_into_tree(&pTreeNode, 8));
assert(TRUE == delete_node_from_tree(&pTreeNode, 6));
assert(5 == pTreeNode->left_child->data);
assert(pTreeNode = pTreeNode->left_child->parent);
assert( 8 == pTreeNode->left_child->right_child->data);
assert(pTreeNode->left_child = pTreeNode->left_child->right_child->parent);
free(pTreeNode->left_child->right_child);
free(pTreeNode->left_child);
free(pTreeNode);
}
/*
*
* 10 ======> 10
* / /
* 6 5
* / \ \
* 5 8 8
*/
static void test14()
{
TREE_NODE* pTreeNode = NULL;
assert(TRUE == insert_node_into_tree(&pTreeNode, 10));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == insert_node_into_tree(&pTreeNode, 5));
assert(TRUE == insert_node_into_tree(&pTreeNode, 8));
assert(TRUE == delete_node_from_tree(&pTreeNode, 6));
assert(5 == pTreeNode->left_child->data);
assert(pTreeNode = pTreeNode->left_child->parent);
assert( 8 == pTreeNode->left_child->right_child->data);
assert(pTreeNode->left_child = pTreeNode->left_child->right_child->parent);
free(pTreeNode->left_child->right_child);
free(pTreeNode->left_child);
free(pTreeNode);
} 2） 左節點不是刪除節點左側的最大節點（刪除節點5）
/*
*
* 10 ======> 10
* / /
* 5 4
* / \ / \
* 2 6 2 6
* \
* 4
*/
static void test15()
{
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, 2));
assert(TRUE == insert_node_into_tree(&pTreeNode, 4));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == delete_node_from_tree(&pTreeNode, 5));
assert(4 == pTreeNode->left_child->data);
assert(NULL == pTreeNode->left_child->left_child->right_child);
free(pTreeNode->left_child->left_child);
free(pTreeNode->left_child->right_child);
free(pTreeNode->left_child);
free(pTreeNode);
}
/*
*
* 10 ======> 10
* / /
* 5 4
* / \ / \
* 2 6 2 6
* \
* 4
*/
static void test15()
{
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, 2));
assert(TRUE == insert_node_into_tree(&pTreeNode, 4));
assert(TRUE == insert_node_into_tree(&pTreeNode, 6));
assert(TRUE == delete_node_from_tree(&pTreeNode, 5));
assert(4 == pTreeNode->left_child->data);
assert(NULL == pTreeNode->left_child->left_child->right_child);
free(pTreeNode->left_child->left_child);
free(pTreeNode->left_child->right_child);
free(pTreeNode->left_child);
free(pTreeNode);
} 那麼針對這兩種類型，我們的代碼究竟應該怎麼處理呢？
STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)
{
TREE_NODE* pLeftMax;
if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = NULL;
else
pTreeNode->parent->right_child = NULL;
}else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){
pTreeNode->left_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->left_child;
else
pTreeNode->parent->right_child = pTreeNode->left_child;
}else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){
pTreeNode->right_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->right_child;
else
pTreeNode->parent->right_child = pTreeNode->right_child;
}else{
pLeftMax = find_max_node(pTreeNode->left_child);
if(pLeftMax == pTreeNode->left_child){
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->left_child;
else
pTreeNode->parent->right_child = pTreeNode->left_child;
pTreeNode->left_child->parent = pTreeNode->parent;
pTreeNode->left_child->right_child = pTreeNode->right_child;
pTreeNode->right_child->parent = pTreeNode-> left_child;
}else{
pTreeNode->data = pLeftMax->data;
pLeftMax->parent->right_child = NULL;
pTreeNode = pLeftMax;
}
}
free(pTreeNode);
return TRUE;
}
STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)
{
TREE_NODE* pLeftMax;
if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = NULL;
else
pTreeNode->parent->right_child = NULL;
}else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){
pTreeNode->left_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->left_child;
else
pTreeNode->parent->right_child = pTreeNode->left_child;
}else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){
pTreeNode->right_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->right_child;
else
pTreeNode->parent->right_child = pTreeNode->right_child;
}else{
pLeftMax = find_max_node(pTreeNode->left_child);
if(pLeftMax == pTreeNode->left_child){
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->left_child;
else
pTreeNode->parent->right_child = pTreeNode->left_child;
pTreeNode->left_child->parent = pTreeNode->parent;
pTreeNode->left_child->right_child = pTreeNode->right_child;
pTreeNode->right_child->parent = pTreeNode-> left_child;
}else{
pTreeNode->data = pLeftMax->data;
pLeftMax->parent->right_child = NULL;
pTreeNode = pLeftMax;
}
}
free(pTreeNode);
return TRUE;
}
結束總結：
上面的過程記錄了我們的代碼是怎麼一步一步走過來的。最後我們給出一份完整的節點刪除代碼：
STATUS _delete_node_from_tree(TREE_NODE* pTreeNode)
{
TREE_NODE* pLeftMax;
if(NULL == pTreeNode-> left_child && NULL == pTreeNode->right_child){
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = NULL;
else
pTreeNode->parent->right_child = NULL;
}else if(NULL != pTreeNode->left_child && NULL == pTreeNode->right_child){
pTreeNode->left_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->left_child;
else
pTreeNode->parent->right_child = pTreeNode->left_child;
}else if(NULL == pTreeNode->left_child && NULL != pTreeNode->right_child){
pTreeNode->right_child->parent = pTreeNode->parent;
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->right_child;
else
pTreeNode->parent->right_child = pTreeNode->right_child;
}else{
pLeftMax = find_max_node(pTreeNode->left_child);
if(pLeftMax == pTreeNode->left_child){
if(pTreeNode == pTreeNode->parent->left_child)
pTreeNode->parent->left_child = pTreeNode->left_child;
else
pTreeNode->parent->right_child = pTreeNode->left_child;
pTreeNode->left_child->parent = pTreeNode->parent;
pTreeNode->left_child->right_child = pTreeNode->right_child;
pTreeNode->right_child->parent = pTreeNode-> left_child;
}else{
pTreeNode->data = pLeftMax->data;
pLeftMax->parent->right_child = NULL;
pTreeNode = pLeftMax;
}
}
free(pTreeNode);
return TRUE;
}
STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data)
{
TREE_NODE* pTreeNode;
TREE_NODE* pLeftMax;
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;
}else{
pLeftMax = find_max_node(pTreeNode->left_child);
if(pLeftMax == pTreeNode->left_child){
*ppTreeNode = pTreeNode->left_child;
(*ppTreeNode)->right_child = pTreeNode->right_child;
(*ppTreeNode)->right_child->parent = *ppTreeNode;
(*ppTreeNode)->parent = NULL;
}else{
pTreeNode->data = pLeftMax->data;
pLeftMax->parent->right_child = NULL;
pTreeNode = pLeftMax;
}
}
free(pTreeNode);
return TRUE;
}
return _delete_node_from_tree(pTreeNode);
}
