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

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

 

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

 

 

 

 

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

 

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

 

 

 

/*

*               

*         10          ======>     6

*        /  \                   /   \

*      6     15               5     15

*     /                      

*    5                         

*/ 

/*

*              

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

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;

          &nb

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