非递归创建二叉查找树
非递归创建二叉查找树代码。
#include <stdio.h>
#include <stdlib.h>typedef int KeyType;
typedef struct BSTNode{KeyType key;struct BSTNode *lchild,*rchild;
}BSTNode,*BiTree;//王道书上的递归写法,代码简单,但是理解有难度
//int BST_Insert1(BiTree &T,KeyType k)
//{
// if(NULL==T)
// { //为新结点申请空间,第一个结点作为树根,后面递归再进入的不是树根,是为叶子结点
// T=(BiTree)malloc(sizeof(BSTNode));
// T->key=k;
// T->lchild=T->rchild=NULL;
// return 1;//代表插入成功
// }
// else if(k==T->key)
// return 0;//发现相同元素,就不插入
// else if(k<T->key)//如果要插入的结点,小于当前结点
// //函数调用结束后,左孩子和原来的父亲会关联起来,巧妙利用了引用机制
// return BST_Insert1(T->lchild,k);
// else
// return BST_Insert1(T->rchild,k);
//}//54,20,66,40,28,79,58
//非递归的创建二叉查找树
int BST_Insert(BiTree &T,KeyType k)
{BiTree TreeNew=(BiTree)calloc(1,sizeof(BSTNode));//新结点申请空间TreeNew->key=k;//把值放入if(NULL==T)//树为空,新结点作为树的根{T=TreeNew;return 1;}BiTree p=T,parent;//p用来查找树while(p){parent=p;//parent用来存p的父亲if(k>p->key){p=p->rchild;}else if(k<p->key){p=p->lchild;}else{return 0;//相等的元素不可以放入查找树,考研不会考相等元素放入问题}}//接下来要判断放到父亲的左边还是右边if(k>parent->key)//放到父亲右边{parent->rchild=TreeNew;}else{//放到父亲左边parent->lchild=TreeNew;}return 1;
}//这里二叉排序树中不放相等元素
void Creat_BST(BiTree &T,KeyType *str,int len)
{int i;for(i=0;i<len;i++){BST_Insert(T,str[i]);//把某一个结点放入二叉查找树}
}void InOrder(BiTree T)
{if(T!=NULL){InOrder(T->lchild);printf("%3d",T->key);InOrder(T->rchild);}
}BiTree BST_Search(BiTree T,KeyType k,BiTree &parent)
{while(T!=NULL&&k!=T->key){parent=T;if(k>T->key){T=T->rchild;}else{T=T->lchild;}}return T;
}//王道书上没有二叉排序树删除代码--考大题的概率没有那么高
//root加引用是因为有可能会删除根结点,从而改变根结点
void DeleteNode(BiTree &root,KeyType x)
{if(NULL==root){return;}if(root->key>x)//当前结点大于要删除的结点,往左子树找{DeleteNode(root->lchild,x);}else if(root->key<x)//当前结点小于要删除的结点,往右子树找{DeleteNode(root->rchild,x);}else{//找到了要删除的结点if(root->lchild==NULL)//左子树为空,右子树直接顶上去{BiTree tempNode=root;root=root->rchild;free(tempNode);}else if(root->rchild==NULL)//右子树为空,左子树直接顶上去{BiTree tempNode=root;root=root->lchild;free(tempNode);}else{//两边都不为空//一般的删除策略是左子树的最大数据或右子树的最小数据代替要删除的结点(这里采用查找左子树最大数据来代替)BiTree tempNode=root->lchild;BiTree parent=root->lchild;while(tempNode->rchild!=NULL){parent=tempNode;//每次tempNode往右走的时候,先保存一下当前位置tempNode=tempNode->rchild;}root->key=tempNode->key;//把tempNode对应的值替换到要删除的值的位置上if(parent!=tempNode){//把tempNode左子树,作为parent的右子树parent->rchild=tempNode->lchild;}else{//当左子树没有右侧结点时//把tempNode左子树,作为root的左子树即可root->lchild=tempNode->lchild;}free(tempNode);}}
}//二叉排序树新建,中序遍历,查找
int main() {BiTree T=NULL;//树根KeyType str[7]={54,20,66,40,28,79,58};//将要进入二叉排序树的元素值Creat_BST(T,str,7);InOrder(T);//中序遍历二叉查找树是由小到大的printf("\n");BiTree search,parent;search=BST_Search(T,40,parent);if(search){printf("find key %d\n",search->key);}else{printf("not find\n");}DeleteNode(T,40);//删除某个结点InOrder(T);printf("\n");return 0;
}
相关文章:
非递归创建二叉查找树
非递归创建二叉查找树代码。 #include <stdio.h> #include <stdlib.h>typedef int KeyType; typedef struct BSTNode{KeyType key;struct BSTNode *lchild,*rchild; }BSTNode,*BiTree;//王道书上的递归写法,代码简单,但是理解有难度 //int …...
摄影师危!AI绘画即将降维打击摄影行业
你还以为AI绘画影响的只是插画师行业吗?错了,摄影行业也即将面临技术洗牌 话不多说,先看一下这几张图 你能一眼看出这是AI画的迪丽热巴吗? 你是不是还以为AI绘画只能画点动漫艺术风格?那你就低估了AI的发展速度&…...
ts 中class
class obj{name:stringage:numberconstructor(name:string,age:number){this.name namethis.age age}setname(){this.name 111 } } //新建实例 //构造方法中的this指向调用者,谁new就指向谁 //这个this 指向 o,打印this,可以获取到o身上的…...
深度解析RocketMq源码-高可用存储组件(四)Dledger框架日志同步流程
1.绪论 在深度解析RocketMq源码-高可用存储组件(一) raft协议详解-CSDN博客 中讲过,raft协议中,日志同步主要有两个地方,一个是leader会跟follower同步数据,另一个是在新leader诞生的时候,会与…...
ONLYOFFICE 文档开发者版 8.1:API 更新
随着版本 8.1 新功能的发布,我们更新了编辑器、文档生成器和插件的 API,并添加了 Office API 板块。阅读下文了解详情。 ONLYOFFICE 文档是什么 ONLYOFFICE 文档是一个功能强大的文档编辑器,支持处理文本文档、电子表格、演示文稿、可填写…...
Activemq单节点在Windows下的配置部署
1.环境信息 服务器信息jdk版本activemq版本备注Windows Server 2008R2 Enterprisejdk-17_windows-x64_bin.exeapache-activemq-5.18.42.jdk配置 1.下载jdk 地址: Java Downloads | Oracle 中国 2.上传至Windows服务器,点击安装,在选择安装目录页面,选择合适的安装目录即…...
SpringBoot-注解@ImportResource引入自定义spring的配置xml文件和配置类
1、注解ImportResource 我们知道Spring的配置文件是可以有很多个的,我们在web.xml中如下配置就可以引入它们: SprongBoot默认已经给我们配置好了Spring,它的内部相当于已经有一个配置文件,那么我们想要添加新的配置文件怎么办&am…...
GitLab配置免密登录之后仍然需要Git登录的解决办法
GitLab配置免密登录之后仍然需要Git登录的解决办法 因为实习工作需要,要在本地拉取gitlab上的代码,设置了密钥之后连接的时候还需要登录的token,摸索之后有了下面的解决办法。 方法一: 根据报错的提示,去网站上设置个人…...
探索小众爱好:打造个人韧性与特色之路
在这个信息爆炸的时代,我们很容易陷入“千篇一律”的漩涡中,无论是生活方式还是兴趣爱好,似乎都趋向于某种“流行”或“热门”。然而,真正的个性与魅力,往往来源于那些不为大众所知的小众爱好。今天,我想和…...
GitHub使用教程(小白版)
看一百篇文章不如自己写一篇 第一步:注册和安装 注册GitHub账号 访问 GitHub官网。点击右上角的 "Sign up" 按钮。按照提示输入你的邮箱、创建用户名和密码,完成注册。 安装Git 访问 Git官网。下载并安装适用于你操作系统的Git。安装…...
深度解析SD-WAN在企业组网中的应用场景
在现代企业快速发展的网络环境中,SD-WAN技术不仅是实现企业各站点间高效连接的关键,也是满足不同站点对互联网、SaaS云应用和公有云等多种业务需求的理想选择。本文将从企业的WAN业务需求出发,对SD-WAN的组网场景进行全面解析,涵盖…...
【INTEL(ALTERA)】Eclipse Nios II SBT 无法从模板创建新应用程序和 BSP
目录 说明 解决方法 说明 您应该能够创建新的应用程序和 BSP 模板包含以下步骤: 选择 Nios II应用程序和 BSP 来自模板。选择您的.sopcinfo 文件并选择模板。从您的工作区单击 选择现有的 BSP 项目。单击 创建。选择所需的 BSP 选项。单击 完成。 但是…...
Vue_cli搭建过程项目创建
概述 vue-cli 官方提供的一个脚手架,用于快速生成一个 vue 的项目模板;预先定义 好的目录结构及基础代码,就好比咱们在创建 Maven 项目时可以选择创建一个 骨架项目,这个骨架项目就是脚手架,我们的开发更加的快速&am…...
面试题4:POST 比 GET 安全?
不是。HTTP就没有加密功能。 我们知道 GET一般将参数放到URL的查询字符串中,如果是实现登录页面,我们的用户名和密码就直接显示到浏览器的地址栏中了,此时就会轻易的被他人获取账号密码,很不安全。而POST会把参数放到 body 里&am…...
Github生成Personal access tokens及在git中使用
目录 生成Token 使用Token-手工修改 使用Token-自动 生成Token 登录GitHub,在GitHub右上角点击个人资料头像,点击Settings → Developer Settings → Personal access tokens (classic)。 在界面上选择点击【Generate new token】,填写如…...
【BUG记录】条件查询没有查询结果 || MybatisPlus打印查询语句
结论 先说结论,查询没有结果,可能是数据库连接,数据问题之类,最有可能的根本原因是查询语句问题,需要想办法检查查询语句,使用mybatisPlus等自动生成查询语句的框架不能直接看语句,可以依靠日志…...
【C#】找不到属性集方法。get只读属性用了反射设置setValue肯定报错
欢迎来到《小5讲堂》 这是《C#》系列文章,每篇文章将以博主理解的角度展开讲解。 温馨提示:博主能力有限,理解水平有限,若有不对之处望指正! 背景 找不到属性集方法。get只读属性用了反射设置setValue肯定报错 报错…...
探索ChatGPT在程序员日常工作的多种应用
引言 在现代科技迅猛发展的今天,人工智能的应用已经深入到我们生活和工作的各个方面。作为程序员,我们时常面临大量繁杂的任务,从代码编写、错误调试到项目管理和团队协作,每一项都需要花费大量的时间和精力。近年来,…...
算法与数据结构——时间复杂度详解与示例(C#,C++)
文章目录 1. 算法与数据结构概述2. 时间复杂度基本概念3. 时间复杂度分析方法4. 不同数据结构的时间复杂度示例5. 如何通过算法优化来提高时间复杂度6. C#中的时间复杂度示例7. 总结 算法与数据结构是计算机科学的核心,它们共同决定了程序的性能和效率。在实际开发中…...
面试题3:GET 和 POST 有什么区别?
[!]高频面试题。 GET 和 POST 没有本质区别,可以进行相互代替。 1、GET语义:“从服务器获取数据”;POST语义:“往服务器上提交数据”。[设计初衷,不一定要遵守] 2、发请求时,给服务器传递的数据ÿ…...
Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)
引言 工欲善其事,必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后,我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集,就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...
