当前位置:编程学习 > C/C++ >>

一步一步写算法(之排序二叉树删除-1)

 

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱: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;

     &n

补充:软件开发 , C语言 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,