首页 > 代码库 > 一步一步写算法（之排序二叉树删除-2）

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

2024-08-07 08:46:44   210人阅读

原文: 一步一步写算法（之排序二叉树删除-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）


联系
我们