一步一步写算法(之排序二叉树删除-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 = 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、 普通节点的删除


    (待续)

上一篇:脱掉360奇虎的“加固保”壳后的发现与你的微信安全


下一篇:一处折腾笔记:Android内嵌html5加入原生微信分享的解决的方法