当前位置: 首页 > news >正文

非递归创建二叉查找树

        非递归创建二叉查找树代码。

#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;//王道书上的递归写法&#xff0c;代码简单&#xff0c;但是理解有难度 //int …...

摄影师危!AI绘画即将降维打击摄影行业

你还以为AI绘画影响的只是插画师行业吗&#xff1f;错了&#xff0c;摄影行业也即将面临技术洗牌 话不多说&#xff0c;先看一下这几张图 你能一眼看出这是AI画的迪丽热巴吗&#xff1f; 你是不是还以为AI绘画只能画点动漫艺术风格&#xff1f;那你就低估了AI的发展速度&…...

ts 中class

class obj{name:stringage:numberconstructor(name:string,age:number){this.name namethis.age age}setname(){this.name 111 } } //新建实例 //构造方法中的this指向调用者&#xff0c;谁new就指向谁 //这个this 指向 o&#xff0c;打印this&#xff0c;可以获取到o身上的…...

深度解析RocketMq源码-高可用存储组件(四)Dledger框架日志同步流程

1.绪论 在深度解析RocketMq源码-高可用存储组件&#xff08;一&#xff09; raft协议详解-CSDN博客 中讲过&#xff0c;raft协议中&#xff0c;日志同步主要有两个地方&#xff0c;一个是leader会跟follower同步数据&#xff0c;另一个是在新leader诞生的时候&#xff0c;会与…...

ONLYOFFICE 文档开发者版 8.1:API 更新

随着版本 8.1 新功能的发布&#xff0c;我们更新了编辑器、文档生成器和插件的 API&#xff0c;并添加了 Office API 板块。阅读下文了解详情。 ​ ONLYOFFICE 文档是什么 ONLYOFFICE 文档是一个功能强大的文档编辑器&#xff0c;支持处理文本文档、电子表格、演示文稿、可填写…...

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的配置文件是可以有很多个的&#xff0c;我们在web.xml中如下配置就可以引入它们&#xff1a; SprongBoot默认已经给我们配置好了Spring&#xff0c;它的内部相当于已经有一个配置文件&#xff0c;那么我们想要添加新的配置文件怎么办&am…...

GitLab配置免密登录之后仍然需要Git登录的解决办法

GitLab配置免密登录之后仍然需要Git登录的解决办法 因为实习工作需要&#xff0c;要在本地拉取gitlab上的代码&#xff0c;设置了密钥之后连接的时候还需要登录的token&#xff0c;摸索之后有了下面的解决办法。 方法一&#xff1a; 根据报错的提示&#xff0c;去网站上设置个人…...

探索小众爱好:打造个人韧性与特色之路

在这个信息爆炸的时代&#xff0c;我们很容易陷入“千篇一律”的漩涡中&#xff0c;无论是生活方式还是兴趣爱好&#xff0c;似乎都趋向于某种“流行”或“热门”。然而&#xff0c;真正的个性与魅力&#xff0c;往往来源于那些不为大众所知的小众爱好。今天&#xff0c;我想和…...

GitHub使用教程(小白版)

看一百篇文章不如自己写一篇 第一步&#xff1a;注册和安装 注册GitHub账号 访问 GitHub官网。点击右上角的 "Sign up" 按钮。按照提示输入你的邮箱、创建用户名和密码&#xff0c;完成注册。 安装Git 访问 Git官网。下载并安装适用于你操作系统的Git。安装…...

深度解析SD-WAN在企业组网中的应用场景

在现代企业快速发展的网络环境中&#xff0c;SD-WAN技术不仅是实现企业各站点间高效连接的关键&#xff0c;也是满足不同站点对互联网、SaaS云应用和公有云等多种业务需求的理想选择。本文将从企业的WAN业务需求出发&#xff0c;对SD-WAN的组网场景进行全面解析&#xff0c;涵盖…...

【INTEL(ALTERA)】Eclipse Nios II SBT 无法从模板创建新应用程序和 BSP

目录 说明 解决方法 说明 您应该能够创建新的应用程序和 BSP 模板包含以下步骤&#xff1a; 选择 Nios II应用程序和 BSP 来自模板。选择您的.sopcinfo 文件并选择模板。从您的工作区单击 选择现有的 BSP 项目。单击 创建。选择所需的 BSP 选项。单击 完成。 但是&#xf…...

Vue_cli搭建过程项目创建

概述 vue-cli 官方提供的一个脚手架&#xff0c;用于快速生成一个 vue 的项目模板&#xff1b;预先定义 好的目录结构及基础代码&#xff0c;就好比咱们在创建 Maven 项目时可以选择创建一个 骨架项目&#xff0c;这个骨架项目就是脚手架&#xff0c;我们的开发更加的快速&am…...

面试题4:POST 比 GET 安全?

不是。HTTP就没有加密功能。 我们知道 GET一般将参数放到URL的查询字符串中&#xff0c;如果是实现登录页面&#xff0c;我们的用户名和密码就直接显示到浏览器的地址栏中了&#xff0c;此时就会轻易的被他人获取账号密码&#xff0c;很不安全。而POST会把参数放到 body 里&am…...

Github生成Personal access tokens及在git中使用

目录 生成Token 使用Token-手工修改 使用Token-自动 生成Token 登录GitHub&#xff0c;在GitHub右上角点击个人资料头像&#xff0c;点击Settings → Developer Settings → Personal access tokens (classic)。 在界面上选择点击【Generate new token】&#xff0c;填写如…...

【BUG记录】条件查询没有查询结果 || MybatisPlus打印查询语句

结论 先说结论&#xff0c;查询没有结果&#xff0c;可能是数据库连接&#xff0c;数据问题之类&#xff0c;最有可能的根本原因是查询语句问题&#xff0c;需要想办法检查查询语句&#xff0c;使用mybatisPlus等自动生成查询语句的框架不能直接看语句&#xff0c;可以依靠日志…...

【C#】找不到属性集方法。get只读属性用了反射设置setValue肯定报错

欢迎来到《小5讲堂》 这是《C#》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解。 温馨提示&#xff1a;博主能力有限&#xff0c;理解水平有限&#xff0c;若有不对之处望指正&#xff01; 背景 找不到属性集方法。get只读属性用了反射设置setValue肯定报错 报错…...

探索ChatGPT在程序员日常工作的多种应用

引言 在现代科技迅猛发展的今天&#xff0c;人工智能的应用已经深入到我们生活和工作的各个方面。作为程序员&#xff0c;我们时常面临大量繁杂的任务&#xff0c;从代码编写、错误调试到项目管理和团队协作&#xff0c;每一项都需要花费大量的时间和精力。近年来&#xff0c;…...

算法与数据结构——时间复杂度详解与示例(C#,C++)

文章目录 1. 算法与数据结构概述2. 时间复杂度基本概念3. 时间复杂度分析方法4. 不同数据结构的时间复杂度示例5. 如何通过算法优化来提高时间复杂度6. C#中的时间复杂度示例7. 总结 算法与数据结构是计算机科学的核心&#xff0c;它们共同决定了程序的性能和效率。在实际开发中…...

面试题3:GET 和 POST 有什么区别?

[!]高频面试题。 GET 和 POST 没有本质区别&#xff0c;可以进行相互代替。 1、GET语义&#xff1a;“从服务器获取数据”&#xff1b;POST语义&#xff1a;“往服务器上提交数据”。[设计初衷&#xff0c;不一定要遵守] 2、发请求时&#xff0c;给服务器传递的数据&#xff…...

基于大模型的 UI 自动化系统

基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...

相关类相关的可视化图像总结

目录 一、散点图 二、气泡图 三、相关图 四、热力图 五、二维密度图 六、多模态二维密度图 七、雷达图 八、桑基图 九、总结 一、散点图 特点 通过点的位置展示两个连续变量之间的关系&#xff0c;可直观判断线性相关、非线性相关或无相关关系&#xff0c;点的分布密…...

网页端 js 读取发票里的二维码信息(图片和PDF格式)

起因 为了实现在报销流程中&#xff0c;发票不能重用的限制&#xff0c;发票上传后&#xff0c;希望能读出发票号&#xff0c;并记录发票号已用&#xff0c;下次不再可用于报销。 基于上面的需求&#xff0c;研究了OCR 的方式和读PDF的方式&#xff0c;实际是可行的&#xff…...

宠物车载安全座椅市场报告:解读行业趋势与投资前景

一、什么是宠物车载安全座椅&#xff1f; 宠物车载安全座椅是一种专为宠物设计的车内固定装置&#xff0c;旨在保障宠物在乘车过程中的安全性与舒适性。它通常由高强度材料制成&#xff0c;具备良好的缓冲性能&#xff0c;并可通过安全带或ISOFIX接口固定于车内。 近年来&…...

信息系统分析与设计复习

2024试卷 单选题&#xff08;20&#xff09; 1、在一个聊天系统(类似ChatGPT)中&#xff0c;属于控制类的是&#xff08;&#xff09;。 A. 话语者类 B.聊天文字输入界面类 C. 聊天主题辨别类 D. 聊天历史类 ​解析 B-C-E备选架构中分析类分为边界类、控制类和实体类。 边界…...