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

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

2014-12-11 622
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 原文: 一步一步写算法（之排序二叉树删除-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天前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代，文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用，并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构，每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树，能高效地管理和检索文件。相较于顺序查找，二叉树查找每次比较可排除一半子树，极大提升了查找效率，尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数，展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
小山那边
33 5
睡觉待开机
|
4月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
睡觉待开机
69 0
光明顶阳顶天
|
1月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码，实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
光明顶阳顶天
60 8
ephemerals__
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序（上）（c语言实现）（附源码）
本文介绍了四种常见的排序算法：冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据，详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序，选择排序通过选择最小元素进行交换，插入排序通过逐步插入元素到已排序部分，而希尔排序则是插入排序的改进版，通过预排序使数据更接近有序，从而提高效率。文章最后总结了这四种算法的空间和时间复杂度，以及它们的稳定性。
ephemerals__
104 8
ephemerals__
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序（下）（c语言实现）（附源码）
本文继续学习并实现了八大排序算法中的后四种：堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现，并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序，快速排序通过递归和多种划分方法实现高效排序，归并排序通过分治法将问题分解后再合并，计数排序则通过统计每个元素的出现次数实现非比较排序。最后，文章还对比了这些排序算法在处理一百万个整形数据时的运行时间，帮助读者了解不同算法的优劣。
ephemerals__
124 7
dufadayang
|
1月前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率？
选择合适的遍历算法，如按层次遍历树时使用广度优先搜索（BFS），中序遍历二叉搜索树以获得有序序列。优化数据结构，如使用线索二叉树减少空指针判断，自定义节点类增加辅助信息。利用递归与非递归的特点，避免栈溢出问题。多线程并行遍历提高速度，注意线程安全。缓存中间结果，避免重复计算。预先计算并存储信息，提高遍历效率。综合运用这些方法，提高二叉树遍历算法的效率。
dufadayang
60 5
mao29955
|
1月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些？
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法，在许多领域都有着不可或缺的应用，它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展，二叉树遍历算法也在不断地被优化和扩展，以适应新的应用场景和需求。
mao29955
47 0
糜终
|
2月前
|
搜索推荐 Shell
解析排序算法：十大排序方法的工作原理与性能比较
解析排序算法：十大排序方法的工作原理与性能比较
糜终
79 9
java冯坚持
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
32 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
37 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树

热门文章

最新文章

  • 1
    深入解析PID控制算法：从理论到实践的完整指南
  • 2
    猫狗宠物识别系统Python+TensorFlow+人工智能+深度学习+卷积网络算法
  • 3
    利用Python内置函数实现的冒泡排序算法
  • 4
    用 Python 实现快速排序算法。
  • 5
    深入解析图神经网络：Graph Transformer的算法基础与工程实践
  • 6
    【宠物识别系统】Python+卷积神经网络算法+深度学习+人工智能+TensorFlow+图像识别
  • 7
    马特赛特旋转算法：Python的随机模块背后的力量
  • 8
    基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
  • 9
    K-means聚类算法是机器学习中常用的一种聚类方法，通过将数据集划分为K个簇来简化数据结构
  • 10
    基于GA遗传算法的PID控制器参数优化matlab建模与仿真
  • 1
    【算法】——快排，分治算法合集
    32
  • 2
    【算法】栈
    29
  • 3
    【算法】位运算合集
    19
  • 4
    【算法】——前缀和（矩阵区域和详解，文末附）
    18
  • 5
    【算法】——二分查找合集
    25
  • 6
    【算法】——滑动窗口专题
    23
  • 7
    基于EO平衡优化器算法的目标函数最优值求解matlab仿真
    12
  • 8
    【算法】——双指针算法合集（力扣）
    11
  • 9
    理解CAS算法原理
    18
  • 10
    探索企业文件管理软件：Python中的哈希表算法应用
    22

    • 相关课程

    更多
  • 智能运维赛（复赛）：利用数据和算法，快速定位系统异常并进行根因分析
  • 智能创作赛（复赛）：相册应用中的视频故事生成算法介绍
  • 智能创作赛（初赛）：相册应用中的故事生成算法介绍
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

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

    • 相关实验场景

    更多
  • 使用Swing算法实现商品推荐
  • RSA密码算法设计与实现
  • RSA非对称加密算法
  • 欧拉图的构造性证明与算法实现
  • 推荐系统入门之使用ALS算法实现打分预测
    • 下一篇
    DataWorks售前咨询