# 一步一步写算法（之排序二叉树删除-3）

2011-10-26

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】 3 普通节点的删除 3.1 删除的节点没有左子树，也没有右子树 测试用例1： 删除节点6/*** 10 ======> 10* / \ ...

【 声明：版权所有，欢迎转载，请勿用于商业用途。 联系信箱：feixiaoxing @163.com】

3 普通节点的删除

3.1 删除的节点没有左子树，也没有右子树

/*

*

* 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 删除的节点有左子树，没有右子树

/*

*

* 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 删除的节点左子树为空，右子树节点不为空

/*

*

* 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);

}