首页 > 代码库 > 一步一步写算法(之排序二叉树删除-2)
一步一步写算法(之排序二叉树删除-2)
原文: 一步一步写算法(之排序二叉树删除-2)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
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 = http://www.mamicode.com/pLeftMax->data;> 那么,这个场景下面测试用例又该怎么设计呢?其实只需要按照上面给出的示意图进行即可。依次插入数据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 = http://www.mamicode.com/pLeftMax->data;> 我们在当前函数的最后一行添加_delete_node_from_tree,这个函数用来处理普通节点的删除情况,我们会在下面一篇博客中继续介绍。
3、 普通节点的删除
(待续)
一步一步写算法(之排序二叉树删除-2)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。