返回顶部

收藏

C++算法之排序二叉树删除

更多

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; 删除节点的左右子树都存在,此时又会分成两种情形
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.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);  
}  

标签:二叉树,删除,C++

收藏

0人收藏

支持

0

反对

0

发表评论