数据结构-----二叉排序树

目录

前言

1.什么是二叉排序树

2.如何构建二叉排序树

3.二叉排序树的操作

3.1定义节点储存方式

3.2插入节点操作

3.2创建二叉排序树

3.4遍历输出（中序遍历）

3.5数据查找操作

3.6获取最大值和最小值

3.7删除节点操作

3.8销毁二叉排序树

4.完整代码

前言

        今天我们继续学习新的知识点----排序二叉树，在此之前我们学习了相关的排序算法，给你一个数组，然后对这个数组进行排序。那么同样的我们也可以去构建一个二叉排序树，在创建树的过程中进行排序，也能实现排序的效果，下面就一起来看看吧！

1.什么是二叉排序树

        二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。 

给定一个二叉树，如果满足以下条件，那就是二叉排序树

  • 若它的左子树不空，则左子树上所有结点的值均小于它根结点的值。
  • 若它的右子树不空，则右子树上所有结点的值均大于它根结点的值。
  • 它的左、右子树都满足为⼆叉排序树

二叉排序树最大的好处就是查找效率高，相较于链表一个一个去查找，二叉排序树可以去根据数据的排序规律来进行查找

二叉排序树图示：

2.如何构建二叉排序树

比如给定一个数组 [62,88,58,47,35,73,51,99,37,93] ，首先拿到第一个数字，以这个数字为根结点（标准），进行构建，如果比这个数字要大的就放到右子树，比这个要小的就放到左子树去，如下图所示：

 这里我们可以看出，这些节点是一个一个去进行插入的，那我们就可以去通过递归插入的方式来创建，依次往下遍历，找到合适的位置再进行插入操作。

3.二叉排序树的操作

3.1定义节点储存方式

#include<stdio.h>
#include<stdlib.h>//二叉排序树节点存储方式
typedef int DataType;
typedef struct binarytreenode {DataType data;	//数据域struct binarytreenode* left;	//左指针 struct binarytreenode* right;	//右指针
}BTnode;

3.2插入节点操作

插入一个节点首先就要找到这个节点应该插入的位置，从跟节点开始，如果比跟节点小就往左，大就往右，直到叶子节点的位置进行插入操作。

代码实现： 

//插入数据
void Insert_node(BTnode** root, DataType data) {if (*root == NULL) {*root = (BTnode*)malloc(sizeof(BTnode));if (!*root) {printf("ERROR\n");exit(-1);}(*root)->data = data;(*root)->left = NULL;(*root)->right = NULL;}else if ((*root)->data <= data)Insert_node(&(*root)->right, data);else if ((*root)->data > data)Insert_node(&(*root)->left, data);
}

3.2创建二叉排序树

创建二叉排序树，只需要一一插入节点，最后返回根节点即可。代码如下：

//创建排序二叉树
BTnode* Create_sortBtree(DataType* arr, int size) {if (!arr)return NULL;else {BTnode* T = NULL;for (int i = 0; i < size; i++) {Insert_node(&T, arr[i]);}return T;}
}

3.4遍历输出（中序遍历）

//中序遍历排序二叉树
void mid_travel(BTnode* T)
{if (!T)return;mid_travel(T->left);printf("%d ", T->data);mid_travel(T->right);
}

3.5数据查找操作

在二叉排序树上查找某一个值节点，然后返回这个节点的操作。这里可以通过递归和非递归两种方法去实现，代码如下：

递归实现： 

BTnode* Btree_search(BTnode* root, DataType target) {if (!root)return NULL;if (target == root->data) {return root;}return target > root->data ? Btree_search(root->right, target) : Btree_search(root->left, target);
}

 非递归实现（迭代实现）：

//非递归查找
BTnode* Btree_search_fa(BTnode* T, DataType target) {BTnode* p = T;while (p) {if (p->data == target){return p;}p = target > p->data ? p->right : p->left;}return NULL;
}

3.6获取最大值和最小值

在一个排序二叉树里面获取最大值或者是最小值，说白了也就是找到最右边和最左边节点就行了，二叉排序树的两个最值就在最两边。代码如下：

获取最大值

//获取最大值
int Btree_max(BTnode* T) {BTnode* cur = T;while (cur->right) {cur = cur->right;}return cur->data;
}

 获取最小值

//获取最小值
int Btree_min(BTnode* T) {BTnode* cur = T;while (cur->left) {cur = cur->left;}return cur->data;
}

3.7删除节点操作

删除节点操作，这就有可能会破坏到排序二叉树的结构，所以要分几种情况去处理。一、如果删除的是叶子节点的话，那么就可以直接去删除，因为叶子节点左右节点都为空，不会影响到二叉排序树的结构；二、如果要删除的节点只有一个左子树或者是有一个右子树的话，我们只需要找到这个节点的左节点或者是右节点，然后顶替掉这个要删除的节点即可；三、如果要删除的节点都有左右子树的话，这里我们就需要去遍历找到比这个节点大一位或者是小一位的节点来顶替这个节点。如下图所示：

1.删除叶子节点 

 

 2.删除只有一个左（右）子树的节点

3.删除有左右子树的节点 

代码实现：

//删除节点
void Btree_del(BTnode* T, DataType l) {if (!T) {printf("fuck no\n");return;}//找到这个要删除节点的父节点BTnode* p = T, * f = NULL;while (p) {if (p->data == l){break;}f = p;p = l > p->data ? p->right : p->left;}if (!p){printf("没有这个节点\n");return;}BTnode* target = p;//此时的要删除目标节点BTnode* par = f; //此时要删除节点的父节点//第一种情况 此节点只有一个子树的时候if (!target->left && target->right != NULL){if (target->data > par->data) {par->right = target->right;}else {par->left = target->right;}free(target);//释放空间target = NULL;}else if (target->left != NULL && !target->right) {if (target->data > par->data) {par->right = target->left;}else {par->left = target->left;}free(target);target = NULL;}//第二种情况，如果删除的是叶节点，直接删除即可else if (!target->left && !target->right) {if (target->data > par->data) {par->right = NULL;}else {par->left = NULL;}free(target);target = NULL;}//第三种情况,如果左右子树都存在的话//可以用右子树的最小元素//或者左子树的最大元素来替代被删除的节点//我这里就直接去用左树的最大代替这个节点else{BTnode* Lchild = target->left;while (Lchild->right != NULL) {Lchild = Lchild->right;}if (target->data > par->data) {par->right = Lchild;}else {par->left = Lchild;}free(target);target = NULL;}printf("Deleting successfully\n");
}

3.8销毁二叉排序树

//销毁
void Destory_btree(BTnode* T) {if (!T)return;BTnode* cur = T;if (cur->left)Destory_btree(cur->left);if (cur->right)Destory_btree(cur->right);free(T);
}

4.完整代码

#include<stdio.h>
#include<stdlib.h>//二叉排序树节点存储方式
typedef int DataType;
typedef struct binarytreenode {DataType data;	//数据域struct binarytreenode* left;	//左指针 struct binarytreenode* right;	//右指针
}BTnode;//插入数据
void Insert_node(BTnode** root, DataType data) {if (*root == NULL) {*root = (BTnode*)malloc(sizeof(BTnode));if (!*root) {printf("ERROR\n");exit(-1);}(*root)->data = data;(*root)->left = NULL;(*root)->right = NULL;}else if ((*root)->data <= data)Insert_node(&(*root)->right, data);else if ((*root)->data > data)Insert_node(&(*root)->left, data);
}//创建排序二叉树
BTnode* Create_sortBtree(DataType* arr, int size) {if (!arr)return NULL;else {BTnode* T = NULL;for (int i = 0; i < size; i++) {Insert_node(&T, arr[i]);}return T;}
}//中序遍历排序二叉树
void mid_travel(BTnode* T)
{if (!T)return;mid_travel(T->left);printf("%d ", T->data);mid_travel(T->right);
}//递归查找数据
BTnode* Btree_search(BTnode* root, DataType target) {if (!root)return NULL;if (target == root->data) {return root;}return target > root->data ? Btree_search(root->right, target) : Btree_search(root->left, target);
}
//非递归查找
BTnode* Btree_search_fa(BTnode* T, DataType target) {BTnode* p = T, * f = NULL;while (p) {if (p->data == target){return f;}f = p;p = target > p->data ? p->right : p->left;}return NULL;
}//获取最大值
int Btree_max(BTnode* T) {BTnode* cur = T;while (cur->right) {cur = cur->right;}return cur->data;
}
//获取最小值
int Btree_min(BTnode* T) {BTnode* cur = T;while (cur->left) {cur = cur->left;}return cur->data;
}//删除节点
void Btree_del(BTnode* T, DataType l) {if (!T) {printf("fuck no\n");return;}//找到这个要删除节点的父节点BTnode* p = T, * f = NULL;while (p) {if (p->data == l){break;}f = p;p = l > p->data ? p->right : p->left;}if (!p){printf("没有这个节点\n");return;}BTnode* target = p;//此时的要删除目标节点BTnode* par = f; //此时要删除节点的父节点//第一种情况 此节点只有一个子树的时候if (!target->left && target->right != NULL){if (target->data > par->data) {par->right = target->right;}else {par->left = target->right;}free(target);//释放空间target = NULL;}else if (target->left != NULL && !target->right) {if (target->data > par->data) {par->right = target->left;}else {par->left = target->left;}free(target);target = NULL;}//第二种情况，如果删除的是叶节点，直接删除即可else if (!target->left && !target->right) {if (target->data > par->data) {par->right = NULL;}else {par->left = NULL;}free(target);target = NULL;}//第三种情况,如果左右子树都存在的话//可以用右子树的最小元素//或者左子树的最大元素来替代被删除的节点//我这里就直接去用左树的最大代替这个节点else{BTnode* Lchild = target->left;while (Lchild->right != NULL) {Lchild = Lchild->right;}if (target->data > par->data) {par->right = Lchild;}else {par->left = Lchild;}free(target);target = NULL;}printf("Deleting successfully\n");
}//销毁
void Destory_btree(BTnode* T) {if (!T)return;BTnode* cur = T;if (cur->left)Destory_btree(cur->left);if (cur->right)Destory_btree(cur->right);free(T);
}int main()
{int a[] = { 53,17,78,9,45,65,87,23 };//创建二叉排序树BTnode* T = Create_sortBtree(a, sizeof(a) / sizeof(int));mid_travel(T);//遍历输出puts("");//删除最大最小值printf("max:%d  min:%d\n", Btree_max(T), Btree_min(T));//查找BTnode* find = Btree_search(T, 23);printf("查找结果%d\n", find->data);//删除节点Btree_del(T, 45);mid_travel(T);puts("");//销毁操作Destory_btree(T);
}
//输出结果：
//9 17 23 45 53 65 78 87
//max:87  min : 9
//查找结果23
//Deleting successfully
//9 17 23 53 65 78 87

以上就是二叉排序树的全部内容了，我们下次见咯！祝各位国庆节快乐！

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/146040.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

【文献】TOF标定 Time-of-Flight Sensor Calibration for a Color and Depth Camera Pair

【文献】TOF标定 Time-of-Flight Sensor Calibration for a Color and Depth Camera Pair

文章目录 Article info.Introduction处理TOF误差Take home messagesResourcesIDEAS Article info. Time-of-Flight Sensor Calibration for a Color and Depth Camera Pair IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 37, NO. 7, JULY 2015 Intr…
阅读更多...
高级词汇和句子（二）-day15

高级词汇和句子（二）-day15

阅读更多...
nextTick源码解读

nextTick源码解读

&#x1f4dd;个人主页&#xff1a;爱吃炫迈 &#x1f48c;系列专栏&#xff1a;Vue &#x1f9d1;‍&#x1f4bb;座右铭&#xff1a;道阻且长&#xff0c;行则将至&#x1f497; 文章目录 nextTick原理nextTicktimerFuncflushCallbacks 异步更新流程updatequeueWatcherflushS…
阅读更多...
ROS2 库包设置和使用 Catch2 进行单元测试

ROS2 库包设置和使用 Catch2 进行单元测试

说明 本文的目的是了解如何在 ROS2 中创建库&#xff0c;以供其他 ROS2 包使用。除此之外&#xff0c;本文还介绍了如何使用 catch2 框架编写单元测试。本文的第 1 部分将详细介绍如何创建库包。第 2 部分将介绍 ROS2 软件包如何利用创建的库 上篇 ROS2 库包设置和使用 Catch2…
阅读更多...
GEO生信数据挖掘（一）数据集下载和初步观察

GEO生信数据挖掘（一）数据集下载和初步观察

检索到目标数据集后&#xff0c;开始数据挖掘&#xff0c;本文以阿尔兹海默症数据集GSE1297为例 目录 GEOquery 简介 安装并加载GEOquery包 getGEO函数获取数据&#xff08;联网下载&#xff09; 更换下载数据源 对数据集进行初步观察处理 GEOquery 简介 GEOquery是一个…
阅读更多...
【AntDesign】封装全局异常处理-全局拦截器

【AntDesign】封装全局异常处理-全局拦截器

[toc] 场景 本文前端用的是阿里的Ant-Design框架&#xff0c;其他框架也有全局拦截器&#xff0c;思路是相同&#xff0c;具体实现自行百度下吧 因为每次都需要调接口&#xff0c;都需要单独处理异常情况&#xff08;code !0&#xff09;&#xff0c;因此前端需要对后端返回的…
阅读更多...
联邦学习-Tensorflow实现联邦模型AlexNet on CIFAR-10

联邦学习-Tensorflow实现联邦模型AlexNet on CIFAR-10

目录 Client端 Server端 扩展 Client.py Server.py Dataset.py Model.py 分享一种实现联邦学习的方法&#xff0c;它具有以下优点&#xff1a; 不需要读写文件来保存、切换Client模型 不需要在每次epoch重新初始化Client变量 内存占用尽可能小&#xff08;参数量仅翻一…
阅读更多...
1.4.C++项目：仿muduo库实现并发服务器之buffer模块的设计

1.4.C++项目：仿muduo库实现并发服务器之buffer模块的设计

项目完整版在&#xff1a; 一、buffer模块&#xff1a; 缓冲区模块 Buffer模块是一个缓冲区模块&#xff0c;用于实现通信中用户态的接收缓冲区和发送缓冲区功能。 二、提供的功能 存储数据&#xff0c;取出数据 三、实现思想 1.实现换出去得有一块内存空间&#xff0c;采…
阅读更多...
Learning Invariant Representation for Unsupervised Image Restoration

Learning Invariant Representation for Unsupervised Image Restoration

Learning Invariant Representation for Unsupervised Image Restoration (Paper reading) Wenchao Du, Sichuan University, CVPR20, Cited:63, Code, Paper 1. 前言 近年来&#xff0c;跨域传输被应用于无监督图像恢复任务中。但是&#xff0c;直接应用已有的框架&#xf…
阅读更多...
【python海洋专题三】图像修饰之画布和坐标轴

【python海洋专题三】图像修饰之画布和坐标轴

【python海洋专题三】图像修饰之画布和坐标轴 海洋与大气科学 上期读取nc水深文件&#xff0c;并出图 但是存在一些不完美&#xff0c;本期修饰 本期内容目录 1&#xff1a;改变画布大小 2&#xff1a;改变画布背景色 3&#xff1a;改变画布在显示屏中的显示位置 4&#xf…
阅读更多...
【项目管理】--敏捷开发管理之Scrum

【项目管理】--敏捷开发管理之Scrum

目录 一、前言二、what---敏捷开发是什么2.1、敏捷开发宣言2.2、敏捷开发原则2.3、一句话概述敏捷开发三、why---为什么会有敏捷开发3.1、传统开发模式和敏捷开发模式对比四、how---敏捷开发怎么实践到项目团队4.1、what---Scrum是什么4.2、what---Scrum有哪些内容(1)、Scrum之…
阅读更多...
NLP 01(介绍)

NLP 01(介绍)

一、NLP 自然语言处理 (Natural Language rrocessing,简称NLP) 是计算机科学与语言学中关注于计算机与人类语言间转换的领域。 1.1 发展 规则&#xff1a;基于语法 自然语言处理的应用场景: 语音助手 机器翻译 搜索引擎 智能问答
阅读更多...
【单片机】12-串口通信和RS485

【单片机】12-串口通信和RS485

1.通信有关的常见概念 区分&#xff1a;串口&#xff0c;COM口&#xff0c;UART&#xff0c;USART_usart和串口区别-CSDN博客 串口、COM口、UART口, TTL、RS-232、RS-485区别详解-CSDN博客 1.什么是通信 &#xff08;1&#xff09;人和人之间的通信&#xff1a;说话&#xff…
阅读更多...
抓包习讯云院校数据通过PHP解析导入数据库

抓包习讯云院校数据通过PHP解析导入数据库

前言 最近&#xff0c;打卡APP需要这个数据&#xff0c;通过抓包后发现这个数据是固定的&#xff0c;获取很简单&#xff0c;但是数据太多&#xff0c;手动导入不显示&#xff0c;于是分析了json格式后果断通过脚本完成 【推荐】 《【MQTT】Esp32数据上传采集&#xff1a;最…
阅读更多...
栈和队列的概念和实现

栈和队列的概念和实现

栈和队列的概念和实现 一.栈二.队列一些题目 一.栈 栈&#xff1a;一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作&#xff0c;进行数据插入和删除操作的一端称为栈顶&#xff0c;另一端称为栈底&#xff0c;栈中的数据元素遵守后进先出LIFO&#x…
阅读更多...
UG\NX二次开发 用程序修改“用户默认设置”

UG\NX二次开发 用程序修改“用户默认设置”

文章作者：里海 来源网站：《里海NX二次开发3000例专栏》 简介 可以用程序修改“用户默认设置”吗？下面是用代码修改“用户默认设置->基本环境->用户界面->操作记录->操作记录语言”的例子。 效果 代码 #include <uf_defs.h> #include <NXOpen/NXExcept…
阅读更多...
angular 在vscode 下的hello world

angular 在vscode 下的hello world

Angulai 是google 公司开发的前端开发框架。Angular 使用 typescript 作为编程语言。typescript 是Javascript 的一个超集&#xff0c;提升了某些功能。本文介绍运行我的第一个angular 程序。 前面部分参考&#xff1a; Angular TypeScript Tutorial in Visual Studio Code 一…
阅读更多...
Kafka-Kerberos票据刷新问题

Kafka-Kerberos票据刷新问题

线上kafka使用了 kerberos 认证&#xff0c;每隔24小时&#xff0c;票据过期&#xff0c;无法自动续期&#xff0c;出现消息发送失败问题。 从日志可以发现会有如下报错&#xff1a; 2023-09-14 17:48:47,144 [kafka-kerberos-refresh-thread-kafka/hdp-1HADOOP.COM] [] WARN …
阅读更多...
gitee 远程仓库操作基础(二)

gitee 远程仓库操作基础(二)

(1&#xff09;clone远端仓库,本地建立分支推送 (基于远程仓库版本库 本地建立分支开发新功能) git clone gitgitee.com:xxxxx/alsa_test.git git remote add origin gitgitee.com:xxxxx/alsa_test.git进入clone过后路径代码,查看本地分支,发现该项目远程仓库有很多分支 基于…
阅读更多...
Spring Framework 学习笔记5：事务

Spring Framework 学习笔记5：事务

Spring Framework 学习笔记5&#xff1a;事务 1.快速入门 1.1.准备工作 这里提供一个示例项目 transaction-demo&#xff0c;这个项目包含 Spring 框架、MyBatis 以及 JUnit。 对应的表结构见 bank.sql。 服务层有一个方法可以用于在不同的账户间进行转账&#xff1a; Se…
阅读更多...
最新文章

Copyright @ 2022~2023