备案控制台
开发者社区 人工智能 文章 正文

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

2014-12-11 601
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 原文: 一步一步写算法（之排序二叉树删除-3） 【 声明：版权所有，欢迎转载，请勿用于商业用途。  联系信箱：feixiaoxing @163.com】     3 普通节点的删除     3.
原文: 一步一步写算法（之排序二叉树删除-3）

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

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


文章标签：
测试技术
算法
关键词：
算法排序
算法二叉树
算法删除
算法排序二叉树
杰克.陈
目录
相关文章
闻缺陷则喜何志丹
|
1月前
|
人工智能 算法 测试技术
【数学】【排序】【C++算法】3027人员站位的方案数
【数学】【排序】【C++算法】3027人员站位的方案数
闻缺陷则喜何志丹
27 0
阿森要自信
|
1月前
|
算法
【算法与数据结构】二叉树（前中后）序遍历1
【算法与数据结构】二叉树（前中后）序遍历
阿森要自信
15 0
阿森要自信
|
1月前
|
算法
【算法与数据结构】二叉树（前中后）序遍历2
【算法与数据结构】二叉树（前中后）序遍历
阿森要自信
18 0
小小unicorn
|
1月前
|
人工智能 算法 BI
【优选算法专栏】专题十八：BFS解决拓扑排序（一）
【优选算法专栏】专题十八：BFS解决拓扑排序（一）
小小unicorn
20 0
小小unicorn
|
1月前
|
算法
【优选算法专栏】专题十八：BFS解决拓扑排序--前言
【优选算法专栏】专题十八：BFS解决拓扑排序--前言
小小unicorn
22 1
Mylvzi
|
1月前
|
算法
算法系列--递归(2)--二叉树专题（上）
算法系列--递归(2)--二叉树专题
Mylvzi
24 0
toKeep
|
3天前
|
算法
常见的算法排序（2）
常见的算法排序（2）
toKeep
11 3
Bigcrab__
|
3天前
|
算法 搜索推荐 索引
数据结构与算法 排序（下）
数据结构与算法 排序（下）
Bigcrab__
9 1
Bigcrab__
|
3天前
|
缓存 算法 搜索推荐
数据结构与算法 排序（上）
数据结构与算法 排序（上）
Bigcrab__
9 0
电力程序小学童
|
4天前
|
算法 调度
【问题探讨】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研究
【问题探讨】基于非支配排序的蜣螂优化算法NSDBO求解微电网多目标优化调度研究
电力程序小学童
9 0

热门文章

最新文章

  • 1
    【MATLAB】GA_ELM神经网络时序预测算法
  • 2
    使用Python实现DBSCAN聚类算法
  • 3
    R语言聚类算法的应用实例
  • 4
    Machine Learning机器学习之决策树算法 Decision Tree（附Python代码）
  • 5
    普林斯顿算法讲义（二）（4）
  • 6
    52个AIGC视频生成算法模型介绍（上）
  • 7
    【算法与数据结构】队列的实现详解
  • 8
    深度解析JVM世界：垃圾判断和垃圾回收算法
  • 9
    普林斯顿算法讲义（一）（4）
  • 10
    R语言贝叶斯MCMC：GLM逻辑回归、Rstan线性回归、Metropolis Hastings与Gibbs采样算法实例
  • 1
    Python基础算法解析：K最近邻算法
    25
  • 2
    【数据结构与算法】—— 手撕红黑树
    42
  • 3
    【优选算法】—— 字符串匹配算法
    49
  • 4
    【优选算法】—— 滑动窗口类问题
    44
  • 5
    【算法】——全排列算法讲解
    37
  • 6
    【排序算法】数据结构排序详解
    48
  • 7
    数据结构——排序算法之快速排序
    34
  • 8
    ArrayList集合的两个实例应用，有趣的洗牌算法与杨辉三角
    28
  • 9
    数据结构--算法的时间复杂度和空间复杂度
    22
  • 10
    KNN和SVM实现对LFW人像图像数据集的分类应用
    44

    • 相关课程

    更多
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • TLS1.3的后量子算法集成
  • RSA非对称加密算法
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）