返回
多御浏览器
广告
多御浏览器
广告

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

发布时间：2023-09-20 03:13:11 269
相关标签：


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



文章来源： https://blog.51cto.com/u_15888909/5880541
特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。
举报
评论区(0)
按点赞数排序
用户头像
0 声望
0 粉丝
1 获赞
TA的文章 更多>
精选文章
thumb 中国研究员首次曝光美国国安局顶级后门—“方程式组织”
thumb 俄乌线上战争，网络攻击弥漫着数字硝烟
thumb 从网络安全角度了解俄罗斯入侵乌克兰的相关事件时间线
下一篇
一步一步写算法（之单词统计） 2023-09-20 00:14:46