一步一步写算法(之排序二叉树线索化)

简介: 原文: 一步一步写算法(之排序二叉树线索化) 【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】     前面我们谈到了排序二叉树,还没有熟悉的同学可以看一下这个,二叉树基本操作、二叉树插入、二叉树删除1、删除2、删除3。
原文: 一步一步写算法(之排序二叉树线索化)

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


    前面我们谈到了排序二叉树,还没有熟悉的同学可以看一下这个,二叉树基本操作二叉树插入二叉树删除1删除2删除3。但是排序二叉树也不是没有缺点,比如说,如果我们想在排序二叉树中删除一段数据的节点怎么办呢?按照现在的结构,我们只能一个一个数据查找验证,首先看看在不在排序二叉树中,如果在那么删除;如果没有这个数据,那么继续查找。那么有没有方法,可以保存当前节点的下一个节点是什么呢?这样就不再需要进行无谓的查找了。其实这样的方法是存在的,那就是在排序二叉树中添加向前向后双向节点。
    现在数据结构定义如下:

typedef struct _TREE_NODE
{
	int data;
	struct _TREE_NODE* prev;
	struct _TREE_NODE* next;
	struct _TREE_NODE* left;
	struct _TREE_NODE* right;
}TREE_NODE;
    拿节点的添加来说,我们可能需要添加prev、next的处理步骤。

void set_link_for_insert(TREE_NODE* pParent, TREE_NODE* pNode)
{
	if(NULL == pParent || NULL == pNode)
		return;

	if(pNode = pParent->left){
		pNode->prev = pParent->prev;
		if(pParent->prev)
			pParent->prev->next = pNode;
		pNode->next = pParent;
		pParent->prev = pNode;
	}else{
		pNode->next = pParent->next;
		if(pParent->next)
			pParent->next->prev = pNode;
		pNode->prev = pParent;
		pParent->next = pNode;
	}

	return;
}

STATUS add_node_into_tree(TREE_NODE** ppTreeNode, int data)
{
	TREE_NODE* pHead;
	TREE_NODE* pNode;

	if(NULL == ppTreeNode)
		return FALSE;

	if(NULL == *ppTreeNode){
		*ppTreeNode = create_new_node(data);
		return TRUE;
	}

	if(NULL != find_data_in_tree(*ppTreeNode, data))
		return FALSE;

	pHead = *ppTreeNode;
	while(1){
		if(data < pHead->data){
			if(pHead->left){
				pHead = pHead->left;
			}else{
				pNode = create_new_node(data);
				pHead->left = pNode;
				break;
			}
		}else{
			if(pHead->right){
				pHead = pHead->right;
			}else{
				pNode = create_new_node(data);
				pHead->right = pNode;
				break;
			}
		}
	}

	set_link_for_insert(pHead, pNode);
	return TRUE;
}
    添加节点如此,删除节点的工作也不能马虎。

void set_link_for_delete(TREE_NODE* pNode)
{
	if(pNode->prev){
		if(pNode->next){
			pNode->prev->next = pNode->next;
			pNode->next->prev = pNode->prev;
		}else
			pNode->prev->next = NULL;
	}else{
		if(pNode->next)
			pNode->next->prev = NULL;
	}
}

TREE_NODE* _delete_node_from_tree(TREE_NODE* root, TREE_NODE* pNode)
{
	TREE_NODE* pLeftMax;
	TREE_NODE* pLeftMaxParent;
	TREE_NODE* pParent = get_parent_of_one(root, pNode);

	if(NULL == pNode->left && NULL == pNode->right){
		if(pNode == pParent->left)
			pParent->left = NULL;
		else
			pParent->right = NULL;
	}else if(NULL != pNode->left && NULL == pNode->right){
		if (pNode == pParent->left)
			pParent->left = pNode->left;
		else
			pParent->right = pNode->left;
	}else if(NULL == pNode->left && NULL != pNode->right){
		if(pNode == pParent->left)
			pParent->left = pNode->right;
		else
			pParent->right = pNode->right;
	}else{
		pLeftMax = get_max_node_of_one(pNode->left);
		if(pLeftMax == pNode->left){
			pNode->left->right = pNode->right;
			if(pNode == pParent->left)
				pParent->left = pNode->left;
			else
				pParent->right = pNode->left;
		}else{
			pLeftMaxParent = get_parent_of_one(root, pLeftMax);
			pNode->data = pLeftMax->data;
			pLeftMaxParent->right = NULL;
			pNode = pLeftMax;
		}
	}

	return pNode;
}

STATUS delete_node_from_tree(TREE_NODE** ppTreeNode, int data)
{
	TREE_NODE* pNode;
	TREE_NODE* pLeftMax;
	TREE_NODE* pLeftMaxParent;

	if(NULL == ppTreeNode || NULL == *ppTreeNode)
		return FALSE;

	if(NULL == (pNode = find_data_in_tree(*ppTreeNode, data)))
		return FALSE;

	if(pNode == *ppTreeNode){
		if(NULL == pNode->left && NULL == pNode->right)
			*ppTreeNode = NULL;
		else if(NULL != pNode->left && NULL == pNode->right)
			*ppTreeNode = pNode->left;
		else if(NULL == pNode->left && NULL != pNode->right)
			*ppTreeNode = pNode->right;
		else {
			pLeftMax =  get_max_node_of_one(pNode->left);
			if(pNode->left == pLeftMax){
				pNode->left->right = pNode->right;
				*ppTreeNode = pNode->left;
			}else{
				pLeftMaxParent = get_parent_of_one(*ppTreeNode, pLeftMax);
				pNode->data = pLeftMax->data;
				pLeftMaxParent->right = NULL;
				pNode = pLeftMax;
			}
		}

		goto final;
	}

	pNode = _delete_node_from_tree(*ppTreeNode, pNode);

final:
	set_link_for_delete(pNode);

	free(pNode);
	return TRUE;
}

    其中,寻找最大值节点和寻找父节点的代码如下所示:

TREE_NODE* get_max_node_of_one(TREE_NODE* pNode)
{
	if(NULL == pNode)
		return NULL;

	while(pNode->right)
		pNode = pNode->right;

	return pNode;
}

TREE_NODE* get_parent_of_one(TREE_NODE* root, TREE_NODE* pNode)
{
	if(NULL == root || NULL == pNode)
		return NULL;

	while(root){
		if(pNode == root->left || pNode == root->right)
			return root;
		else if(pNode->data < root->data)
			root = root->left;
		else
			root = root->right;
	}

	return NULL;
}

总结:
    (1)排序二叉树的序列化关键就是在二叉树节点添加前向指针和后继指针
    (2)排序二叉树是空间换时间的典型案例
    (3)排序二叉树是很多结构的基础,写多少遍都不为多,有机会朋友们应该多加练习
    (4)测试用例的编写是代码编写的关键,编写程序的目的就是为了消除bug,特别是低级bug


目录
相关文章
|
7天前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
39 9
 算法系列之数据结构-二叉树
|
2月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
60 2
|
3月前
|
存储 算法 Python
文件管理系统中基于 Python 语言的二叉树查找算法探秘
在数字化时代,文件管理系统至关重要。本文探讨了二叉树查找算法在文件管理中的应用,并通过Python代码展示了其实现过程。二叉树是一种非线性数据结构,每个节点最多有两个子节点。通过文件名的字典序构建和查找二叉树,能高效地管理和检索文件。相较于顺序查找,二叉树查找每次比较可排除一半子树,极大提升了查找效率,尤其适用于海量文件管理。Python代码示例包括定义节点类、插入和查找函数,展示了如何快速定位目标文件。二叉树查找算法为文件管理系统的优化提供了有效途径。
75 5
|
4月前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
4月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
214 7
|
4月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
168 8
|
4月前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
110 5
|
4月前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
138 0
|
5月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
53 0
|
5月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
48 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)