1. 首页
  2. CSS
  3. c++，排序二叉树删除

c++，排序二叉树删除

•css•阅读 1365

相比较节点的添加，平衡二叉树的删除要复杂一些。因为在删除的过程中，你要考虑到不同的情况，针对每一种不同的情况，你要有针对性的反应和调整。所以在代码编写的过程中，我们可以一边写代码，一边写测试用例。编写测试用例不光可以验证我们编写的代码是否正确，还能不断提高我们开发代码的自信心。这样，即使我们在开发过程对代码进行修改或者优化也不会担心害怕。然而看起来编写测试用例是一个繁杂的过程，但是从长期的收益来看，编写测试用例的成本是非常低廉的。

在排序二叉树的删除过程当中，我们应该怎么做呢？大家不用担心，只要按照我们下面的介绍一步一步往下做就可以了，大体上分为下面三个步骤：

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；
}
那么此时测试用例怎么写呢？ 
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;
}
此时，我们设计一种当前指针合法，但是删除数据不存在的测试用例。 
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
*/
那么此时代码应该怎么写呢？我们可以试一试。 
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);
}
2.2 删除根数据时，只有左子树节点，没有右子树节点
/*
*               
*         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;
}
这个时候，我们可以添加新的测试用例，分别添加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);
}
2.3 删除根数据时，没有左子树节点，只有右子树节点
/*
*               
*         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;
}
添加测试用例，依次添加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);
}

2.4删除数据的左右节点都存在

2.4 删除节点的左右子树都存在，此时又会分成两种情形

1）左节点是当前左子树的最大节点，此时只需要用左节点代替根节点即可

/*
*               
*         10          ======>     6
*        /  \                   /   \
*      6     15               5     15
*     /                      
*    5                         
*/

代码该怎么编写呢？

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;
                        }
                }
                
                free(pTreeNode);
                return TRUE;
        }
        
        return TRUE;
}

上面的代码中添加的内容表示了我们介绍的这一情形。为此，我们可以设计一种测试用例。依次插入10、6、5、15，然后删除10即可。

static void test6()
{
        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, 15));
        assert(TRUE == delete_node_from_tree(&pTreeNode, 10));
        assert(6 == pTreeNode->data);
        assert(NULL == pTreeNode->parent);
        assert(15 == pTreeNode->right_child->data);
        assert(pTreeNode = pTreeNode->right_child->parent);
        assert(NULL == pTreeNode->parent);
        free(pTreeNode->left_child);
        free(pTreeNode->right_child);
        free(pTreeNode);
}

如果上面的测试用例通过，表示我们添加的代码没有问题。

2）左节点不是当前左子树的最大节点，情形如下所示

/*
*               
*         10          ======>     8
*        /  \                   /   \
*      6     15               5     15
*       \                      
*        8                     
*/

此时，我们应该用10左侧的最大节点8代替删除的节点10即可。

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 TRUE;
}

那么，这个场景下面测试用例又该怎么设计呢？其实只需要按照上面给出的示意图进行即可。依次插入数据10、6、8、15，然后删除数据10。

static void test7()
{
        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 == insert_node_into_tree(&pTreeNode, 15));
        assert(TRUE == delete_node_from_tree(&pTreeNode, 10));
        assert(8 == pTreeNode->data);
        assert(NULL == pTreeNode->parent);
        assert(NULL == pTreeNode->left_child->right_child);
        assert(NULL == pTreeNode->parent);
        free(pTreeNode->left_child);
        free(pTreeNode->right_child);
        free(pTreeNode);
}

至此，删除节点为根节点的情形全部讨论完毕，那么如果删除的节点是普通节点呢，那应该怎么解决呢？

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 = pLeftMax->left_child;
                                pLeftMax->left_child->parent = pLeftMax->parent;
                                pTreeNode = pLeftMax;
                        }
                }
                
                free(pTreeNode);
                return TRUE;
        }
        
        return _delete_node_from_tree(pTreeNode);
}

我们在当前函数的最后一行添加_delete_node_from_tree，这个函数用来处理普通节点的删除情况，我们会在下面一篇博客中继续介绍。

3、 普通节点的删除

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

测试用例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);
}

那么代码应该怎么编写呢？

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

测试用例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);
}

添加左子树不为空，右子树为空的处理代码，如下所示：

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

测试用例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);
}

添加左子树为空，右子树不为空的处理情形。代码如下：

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

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

那么针对这两种类型，我们的代码究竟应该怎么处理呢？

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 = pLeftMax->left_child;
                        pLeftMax->left_child->parent = pLeftMax->parent;
                        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 = pLeftMax->left_child;
                        pLeftMax->left_child->parent = pLeftMax->parent;                       
                        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 = pLeftMax->left_child;
                                pLeftMax->left_child->parent = pLeftMax->parent;
                                pTreeNode = pLeftMax;
                        }
                }
                
                free(pTreeNode);
                return TRUE;
        }
        
        return _delete_node_from_tree(pTreeNode);
}

相关推荐

Copyright © 2008-2024渝ICP备2022006305号-5.

本站所有数据收集于网络如有侵犯到您的权益请联系，进行下架处理。