二叉排序树的创建

二叉排序树就是节点经过排序构建起的二叉树,其有以下性质:

1. 若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值。

2. 若它的右子树不为空,则右子树上所有节点的值均大于它的根节点的值。

3. 它的左、右子树也分别为二叉排序树。

画个图方便理解:

        第一张图是一个简单的排序二叉树,5<10<15,所以顺序应该是 10 作为根节点,小于10的在左子树,大于10的在右子树。

        如果现在又要加入一个节点呢?比如说:6,它应该放在哪里?因为 6 比 10 小,所以 6 应该放在 10 的左子树,又因为 6 比 5 大所以放在 5 的右子树。如图:

        那么如果是 16 呢?16 先和 10 进行比较,16>10 进入10的右子树,16 再和 15 比较,16>15,进入 15 的右子树。如图:

现在如果给一个数组:int array[6] = { 6,3,12,5,20,1 },如何构建一个二叉排序树呢?

我们可以回想我们在构建树的时候代码思路:

void CreatTree(TreeNode** T, int data) {if (data == "#") {孩子置空停止递归*T=NULL;}else {*T = (TreeNode*)malloc(sizeof(TreeNode));(*T)->val = data;(*T)->lchild = NULL;(*T)->rchild = NULL;递归左子树,递归右子树Creat_BST(&((*T)->rchild), data);Creat_BST(&((*T)->lchild), data);}}
}

        我这里写的不完整,主要看 else部分,创建节点,然后递归创建左右孩子节点,那么二叉排序树的特殊条件就是小的放在左孩子,大的放在右孩子,只不过加了个判断条件,而不是左右孩子都创建。

所以我们可以这样创建排序二叉树:

void Creat_BST(TreeNode** T, int data) {if (*T == NULL) {*T = (TreeNode*)malloc(sizeof(TreeNode));(*T)->val = data;(*T)->lchild = NULL;(*T)->rchild = NULL;}else {if (data> (*T)->val){Creat_BST(&((*T)->rchild), data);}else {Creat_BST(&((*T)->lchild), data);}}
}

        我的函数是只创建一个二叉排序树的节点,首先传进的 *T 是空,说明树为空,所以创建节点。第二个数据进入时,因为根不为空进入 else,如果小于根节点数据,则进入左孩子遍历(因为左孩子在在创建根节点时置空,所以这时就会创建左孩子存放第二个数据。),如果大于根节点数据,则进入右孩子遍历。

下面是用循环创建二叉排序树的主函数代码:

int main() {TreeNode* T = NULL;int array[6] = { 6,3,12,5,20,1 };for (int i = 0; i < 6; i++) {Creat_BST(&T, array[i]);}return 0;
}

最后写一个寻找树中是否有目标值的函数,逻辑很相似:

TreeNode* BST_search(TreeNode* T, int val) {if (T) {if (T->val == val) {return T;}else{if (val < T->val) {return BST_search(T->lchild, val);}if (val > T->val) {return BST_search(T->rchild, val);}}}else {return NULL;}
}

        如果相等就返回地址,如果小于树节点的值,利用二叉排序树的性质,就一定在左子树,继而进入左子树递归,如果大于树节点的值,就一定在右子树,进入右子树进行递归。如果都没有,最后一定会找到末端节点的左右孩子,末端节点的左右孩子是空,所以进入最后一个 else 返回NULL。

这就是文章的全部内容了,希望对你有所帮助,如有错误欢迎评论。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

python期末作业:批量爬取站长之家的网站排行榜数据并保存,数据分析可视化

爬虫作业,含python爬取数据和保存文件,数据分析使用pyecharts做数据可视化 整体上分析网站的排名,直观看各个网站的热度。 数据分析之后大致的效果: 整个项目分为两个大的部分,第一部分就是抓取网站排名数据,然后保存为Excel、csv等格式,其次就是从文件中…

下一代Docker会让部署更丝滑吗

下一代Docker会让部署更丝滑吗 如何通俗易懂的理解DockerDocker有什么缺点Docker与AI结合&#xff0c;会让部署更加丝滑吗 随着互联网技术的不断发展&#xff0c;单机系统已经无法满足日益正常的用户量以及正常处理用户请求&#xff0c;这个时候就需要进行多机部署&#xff0c;…

设计新境界:大数据赋能UI的创新美学

设计新境界&#xff1a;大数据赋能UI的创新美学 引言 随着大数据技术的蓬勃发展&#xff0c;它已成为推动UI设计创新的重要力量。大数据不仅为界面设计提供了丰富的数据资源&#xff0c;还赋予了设计师以全新的视角和工具来探索美学的新境界。本文将探讨大数据如何赋能UI设计…

使用Datav,echarts开发各种地图

一、功能描述 在实际中&#xff0c;有时候需要针对不同的地图进行开发&#xff0c;而能在网上找到现成&#xff0c;与需要匹配度高的&#xff0c;几乎很难&#xff0c;而且找起对应的资源也相对麻烦。所以结合DataV提供的地图数据&#xff0c;就能开发出各种地图&#xff0c;然…

英语学习笔记25——Mrs. Smith‘s kitchen

Mrs. Smith’s kitchen 史密斯太太的厨房 词汇 Vocabulary Mrs. 夫人【已婚】 复习&#xff1a;Mr. 先生 全名 / 姓    Mrs. 夫人 全名 / 丈夫的姓    Miss 小姐&#xff08;未婚&#xff09; 全名 / 姓    Ms. 女士 全名 / 姓 查看婚姻状况&#xff0c;可以观察…

神经网络的工程基础(零)——PyTorch基础

相关说明 这篇文章的大部分内容参考自我的新书《解构大语言模型&#xff1a;从线性回归到通用人工智能》&#xff0c;欢迎有兴趣的读者多多支持。 本文涉及到的代码链接如下&#xff1a;regression2chatgpt/ch06_optimizer/gradient_descent.ipynb 本文将介绍PyTorch的基础。…

速看!!!24上软考-信息系统项目管理师真题回忆,考点已更新

整理了24上半年软考高级信息系统项目管理师的考试真题&#xff0c;软考一个批次一套题&#xff0c;现在都是机考&#xff0c;收集题目比较困难&#xff0c;希望能给个小小的赞支持一下。 注意&#xff1a;当天考试的宝子们可以对答案预估分数&#xff01;后面场次的宝子可以提…

WordPress搭建流程

1. 简介 WordPress 是一个 PHP 编写的网站制作平台。WordPress 本身免费,并且拥有众多的主题可以使用,适合用于搭建个人博客、公司官网、独立站等。 2. 环境准备 2.1 WordPress 下载 WordPress 可以在 Worpress中文官网 下载(如果后续要将后台调成中文的话,一定要从中文…

idea中显示git的Local Changes

1. 第一打开idea中的Settings文件 2. 找到Version Contro中的commint 3. 取消勾选应用即可 4. 本地提交就会显示出来

堆和堆排序

目录 1.二叉树的顺序存储2.堆的性质3.堆的实现3.1 堆的插入&#xff08;向上调整算法&#xff09;3.2 堆向下调整算法3.3 堆的创建3.4 堆的删除3.5 全套代码 4.堆排序5.Top-K问题 1.二叉树的顺序存储 顺序存储就是数组存储&#xff0c;一般使用数组只适合完全二叉树&#xff0…

AI革命:生活无处不智能

AI革命&#xff1a;生活无处不智能 &#x1f604;生命不息&#xff0c;写作不止 &#x1f525; 继续踏上学习之路&#xff0c;学之分享笔记 &#x1f44a; 总有一天我也能像各位大佬一样 &#x1f3c6; 博客首页 怒放吧德德 To记录领地 &#x1f31d;分享学习心得&#xff0…

回见,那果园

记不得何时开始骑行&#xff0c;何时开始爬山&#xff0c;何时偶遇洛师傅&#xff0c;何时进了那半山腰的果园。 似乎很远&#xff0c;又很近。 昨天打电话给果园的师傅&#xff0c;本意问问杏是否熟了&#xff0c;周末骑行过去、进山聊天顺道吃个新鲜。 洛师傅呵呵的笑…

电脑版网易云音乐听歌识曲

文章目录 流程 流程 电脑网易云音乐的搜索框旁边就是听歌识曲功能

NDIS小端口驱动开发(一)

在四种NDIS相关的驱动中&#xff0c;微型端口驱动(也经常翻译为为小端口驱动)位于驱动栈的底部&#xff0c;一般将它理解为NIC设备的驱动程序&#xff1a; 有几种类型的微型端口驱动程序类型&#xff1a; 无连接微型端口驱动程序用于控制无连接网络媒体 &#xff0c;如以太网的…

JMeter 常见易错问题

1、配置错误&#xff1a; 问题&#xff1a;线程组配置错误&#xff0c;例如设置了错误的线程数或循环次数。 解决方法&#xff1a;检查线程组的配置。确保线程数&#xff08;即并发用户数量&#xff09;设置正确&#xff0c;以及循环次数符合预期。如果要模拟不同类型的用户行…

arc-eager算法XJTU-NLP自然语言处理技术期末考知识点

arc-eager算法&#xff1a;以我/做了/一个/梦为例来描述arc-eager算法的四个操作&#xff1a;shift&#xff0c;left-arc&#xff0c;right-arc&#xff0c;reduce XJTU-NLP期末考点2024版 题型&#xff1a;5*6简答题4*15计算题 简答题考点&#xff1a; &#xff08;1&#…

【30天精通Prometheus:一站式监控实战指南】第8天:redis_exporter从入门到实战:安装、配置详解与生产环境搭建指南,超详细

亲爱的读者们&#x1f44b;   欢迎加入【30天精通Prometheus】专栏&#xff01;&#x1f4da; 在这里&#xff0c;我们将探索Prometheus的强大功能&#xff0c;并将其应用于实际监控中。这个专栏都将为你提供宝贵的实战经验。&#x1f680;   Prometheus是云原生和DevOps的…

1301-习题1-1高等数学

1. 求下列函数的自然定义域 自然定义域就是使函数有意义的定义域。 常见自然定义域&#xff1a; 开根号 x \sqrt x x ​&#xff1a; x ≥ 0 x \ge 0 x≥0自变量为分式的分母 1 x \frac{1}{x} x1​&#xff1a; x ≠ 0 x \ne 0 x0三角函数 tan ⁡ x cot ⁡ x \tan x \cot x …

生产物流智能优化系统

对生产调度、物流调度【车辆路径问题、配送中心拣选问题】智能优化算法研究形成系统性程序&#xff0c;逐步开发设计一个智能优化系统【包括&#xff1a;问题说明、实验界面、算法结构和算法程序应用说明】&#xff0c; 当前完成TSP和集送车辆路径的算法程序&#xff0c;程序效…

Pandas高效数据清洗与转换技巧指南【数据预处理】

三、数据处理 1.合并数据&#xff08;join、merge、concat函数&#xff0c;append函数&#xff09; Concat()函数使用 1.concat操作可以将两个pandas表在垂直方向上进行粘合或者堆叠。 join属性为outer&#xff0c;或默认时&#xff0c;返回列名并集&#xff0c;如&#xff…