西风的数据结构教程(3)——二叉树

2024-02-23 13:18

本文主要是介绍西风的数据结构教程(3)——二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

今天我们终于要说到计算机界的经典数据结构——树,树是非常良好的一种组织数据的形式,在现实生活中也经常用到。

树的结构,大概就是这个样子:

这里写图片描述

一群树就会组成一个森林

不过,这样并不好管理,所以我们一般会还是使用一个根节点来管理它们。

树结构最大的特点就是,一个节点的情况分析只和父节点和子节点相关,这样管理数据时往往不需要考虑很多。

例如文件系统中,每个文件夹可以视为一个节点,而每个文件夹只显示自己的子节点,结构就非常清晰了。

而二叉树是树结构中的非常常用的一种,往往被用作排序树使用,可以自动排序和判重,可以作为索引使用。

下面我们就来实际写一个二叉排序树,然后增加其平衡性,将其改写为一棵红黑树,不过红黑树的部分十分复杂,可以循序渐进的来学习和理解,不必一下就学习完。

二叉排序树

二叉排序树是简单的排序数据结构,可以支持动态的插入删除数据,对数据快速查找,复杂度只有log(n)

它的实现方法是这样的:

这里写图片描述

原理很简单,对于每一棵子树,左孩子都比自己小,右孩子都比自己大,那么就利用二分的思想,不断寻找这个数所在的位置。

插入时,则需要先考虑好要插入的位置:

这里写图片描述

我们发现,插入操作和查找操作是几乎一样的,只要找到对应的位置,插入很好办。

删除时,确实要复杂一点,因为我们直接将节点从树上拿走,如果叶子节点还好办,但我们考虑非叶子节点的删除,就较为复杂了。那么,如何才能正确的删除一个节点呢?我们来观察一下:

这里写图片描述

通过这张图,我们能看出来,每一个元素的上一个相邻元素是左子树的最右边孩子,下一个元素是右子树的最左孩子,这两个相邻元素都是叶子节点,而且如果左子树没有右孩子节点,那么就用最大的根节点替换。同理,用右子树删除也可以。

这里写图片描述

那好,我们既然知道了树的基本操作,就来简要的模拟一下,二叉排序树是如何运作的。

二叉排序树的实现

让我们来定义一棵树吧

typedef int TreeElementType;typedef struct _bst_node
{TreeElementType data;struct _bst_node *left, *right;
} bst_node;typedef struct _tree
{bst_node* root;
} bstree;

还是类似的方法,bstree存抽象的树对象,bst_node则是树的每个节点,其中存放的元素单独定义出来

为其编写构造函数:


bst_node* TreeNodeCreate() {bst_node* n = (bst_node*) malloc(sizeof(bst_node));n->left = n->right = NULL;
}bstree* BSTreeCreate() {return (bstree*)malloc(sizeof(bstree));
}

下面我们要开始实现这个二叉树了,二叉树的插入十分简单,只需要递归的判断,当前节点是比中值大还是小,如果小就往左走,大就往右走,相同时就直接返回无法插入即可。
但这样实现考虑到函数的调用效率问题,我们采用while循环来实现,只需要用指针模拟两个节点即可:

void TreeInsert(bstree* t, TreeElementType data) {if (t->root == NULL) { t->root = TreeNodeCreate();t->root->data = data; return;}bst_node* p = t->root;bst_node* q = NULL;while(p != NULL) {if (data < p->data) { q = p; p = p->left; continue; }if (data > p->data) { q = p; p = p->right; continue; }if (data ==p->data) return;}bst_node* node = TreeNodeCreate();node->data = data;if (data < q->data)q->left = node;elseq->right = node;
}

而查找方法也将是使用循环实现的:

bst_node* TreeSearch(bstree* t, TreeElementType data) {if (t->root == NULL) return NULL;bst_node* p = t->root;while(p != NULL) {if (data ==p->data) return p;if (data < p->data) { p = p->left; continue; }if (data > p->data) { p = p->right; continue; }}return NULL;
}

二叉树的删除是最复杂的部分,核心思路就是找一个可以和当前节点互换的元素,将那个元素替换上去,当前节点拿下来:

void TreeDelete(bstree* t, TreeElementType data) {if (t->root == NULL) return;bst_node* p = t->root;bst_node* q = NULL;while(p != NULL) {if (data ==p->data) break;if (data < p->data) { q = p; p = p->left; continue; }if (data > p->data) { q = p; p = p->right; continue; }}if (p == NULL) return;if (p->left == NULL) { // 若p没有左孩子,直接用它的右孩子取代q->right = p->right;Free(p);} else { // 否则先找到做子树中最大的元素ptemp, 用它交换p, 然后ptemp由ptemp的左孩子代替(因为它一定没有右孩子)bst_node* ptemp = p->left;bst_node* qtemp = NULL;while(ptemp->right != NULL) {qtemp = ptemp;ptemp = ptemp->right;}q->right = ptemp;qtemp->right = ptemp->left;ptemp->left = p->left;ptemp->right = p->right;Free(p);}
}

本系列教程由 西风逍遥游 原创,转载请注明出处:http://blog.csdn.net/xfxyy_sxfancy

这篇关于西风的数据结构教程(3)——二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/738764

相关文章

使用Docker构建Python Flask程序的详细教程

《使用Docker构建PythonFlask程序的详细教程》在当今的软件开发领域,容器化技术正变得越来越流行,而Docker无疑是其中的佼佼者,本文我们就来聊聊如何使用Docker构建一个简单的Py... 目录引言一、准备工作二、创建 Flask 应用程序三、创建 dockerfile四、构建 Docker

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

Java Web实现类似Excel表格锁定功能实战教程

《JavaWeb实现类似Excel表格锁定功能实战教程》本文将详细介绍通过创建特定div元素并利用CSS布局和JavaScript事件监听来实现类似Excel的锁定行和列效果的方法,感兴趣的朋友跟随... 目录1. 模拟Excel表格锁定功能2. 创建3个div元素实现表格锁定2.1 div元素布局设计2.

SpringBoot连接Redis集群教程

《SpringBoot连接Redis集群教程》:本文主要介绍SpringBoot连接Redis集群教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 依赖2. 修改配置文件3. 创建RedisClusterConfig4. 测试总结1. 依赖 <de

Nexus安装和启动的实现教程

《Nexus安装和启动的实现教程》:本文主要介绍Nexus安装和启动的实现教程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、Nexus下载二、Nexus安装和启动三、关闭Nexus总结一、Nexus下载官方下载链接:DownloadWindows系统根

CnPlugin是PL/SQL Developer工具插件使用教程

《CnPlugin是PL/SQLDeveloper工具插件使用教程》:本文主要介绍CnPlugin是PL/SQLDeveloper工具插件使用教程,具有很好的参考价值,希望对大家有所帮助,如有错... 目录PL/SQL Developer工具插件使用安装拷贝文件配置总结PL/SQL Developer工具插

Java中的登录技术保姆级详细教程

《Java中的登录技术保姆级详细教程》:本文主要介绍Java中登录技术保姆级详细教程的相关资料,在Java中我们可以使用各种技术和框架来实现这些功能,文中通过代码介绍的非常详细,需要的朋友可以参考... 目录1.登录思路2.登录标记1.会话技术2.会话跟踪1.Cookie技术2.Session技术3.令牌技

Python使用Code2flow将代码转化为流程图的操作教程

《Python使用Code2flow将代码转化为流程图的操作教程》Code2flow是一款开源工具,能够将代码自动转换为流程图,该工具对于代码审查、调试和理解大型代码库非常有用,在这篇博客中,我们将深... 目录引言1nVflRA、为什么选择 Code2flow?2、安装 Code2flow3、基本功能演示

Java Spring 中的监听器Listener详解与实战教程

《JavaSpring中的监听器Listener详解与实战教程》Spring提供了多种监听器机制,可以用于监听应用生命周期、会话生命周期和请求处理过程中的事件,:本文主要介绍JavaSprin... 目录一、监听器的作用1.1 应用生命周期管理1.2 会话管理1.3 请求处理监控二、创建监听器2.1 Ser

MySQL 安装配置超完整教程

《MySQL安装配置超完整教程》MySQL是一款广泛使用的开源关系型数据库管理系统(RDBMS),由瑞典MySQLAB公司开发,目前属于Oracle公司旗下产品,:本文主要介绍MySQL安装配置... 目录一、mysql 简介二、下载 MySQL三、安装 MySQL四、配置环境变量五、配置 MySQL5.1