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

数据结构---二叉线索树

数据结构—二叉线索树

原理:参考趣学数据结构

代码:

#include<stdio.h>
#include<stdlib.h>
typedef struct bmTree {int data;struct bmTree* lchild, *rchild;int ltag, rtag;
}bmTree;
bmTree * pre=NULL;//中序遍历的前驱指针
void createBTree(bmTree* & BMTree) {//创建二叉树int data;scanf_s("%d", &data);if (data == -1) {BMTree = NULL;}else {BMTree= (bmTree*)malloc(sizeof(bmTree));BMTree->data = data;createBTree(BMTree->lchild);createBTree(BMTree->rchild);}}
void midTraverseBMTree(bmTree* & BMTree) {//中序构造二叉线索树bmTree* T = BMTree;if (T) {midTraverseBMTree(T->lchild);if (!T->lchild) {T->ltag = 1;//指向直接前驱T->lchild = pre;}else {T->ltag = 0;//有左孩子}if (pre) {if (!pre->rchild) {pre->rtag = 1;//直接后继pre->rchild = T;}else {pre->rtag = 0;//有右孩子}}pre = T;midTraverseBMTree(T->rchild);}
}
void printMideBMT(bmTree * T) {//遍历二叉线索树bmTree *p = T;while (p) {while (p->ltag==0) {p = p->lchild;}printf("%d ", p->data);//左结点while (p->rtag == 1&&p->rchild) {p = p->rchild;printf("%d ", p->data);//根|右结点}p = p->rchild;//右子树}
}
int main() {bmTree* T;createBTree(T);midTraverseBMTree(T);pre->rchild = NULL;//中序遍历的最后一个元素,没有后继pre->rtag = 1;printf("二叉线索树进行中序遍历:");printMideBMT(T);printf("\n");system("pause");return 0;
}

测试截图:

请添加图片描述

时间复杂度O(nlogn),空间复杂度O(1)

如果存在什么问题,欢迎批评指正!谢谢!

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈,一经查实,立即删除!

真·杂项:资本论阅读笔记(随缘更新)

Chap1 商品与货币 商品的两个属性&#xff1a;使用价值和价值 商品是使用价值和价值的综合体。 使用价值&#xff1a;物品对人有用&#xff0c;价值分为质&#xff08;属性&#xff09;和量&#xff08;多少&#xff09; 交换价值&#xff1a;一种使用价值和另一种使用价值…...

HMS Core助力同程旅行,打造更贴心的用户出行体验

作为中国在线旅行行业的创新者&#xff0c;同程旅行聚焦年轻、时尚、个性的消费群体&#xff0c;致力于为用户提供更便捷、聪明、安全的出行服务。近年来&#xff0c;同程旅行通过人工智能等创新科技的应用将平台原本的交易撮合角色转变为“管家”和“助手”的角色&#xff0c;…...

C++STL算法 mismatch 中string.c_str()无法直接放到容器中

vs下的输出结果如下 .天地玄黄 日月盈昃 辰宿列张 寒来暑往 秋收冬藏 闰余成岁 闰余成岁 8 0 8 8 8 8 8 8 天地玄黄 日月盈昃 辰宿列张 寒来暑往 秋收冬藏 闰余成岁 律吕调阳 8 0 8 8 8 8 8 8 闰余成岁 7 律吕调阳 7 #include<iostream> #include<cstdlib> #includ…...

vue简单基础

引入vue 新建vue对象 绑定作用范围 {{}} 取值 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><meta http…...

Flutter 自定义单选按钮

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pMekK9tV-1629764513963)(https://ducafecat.tech/2021/08/24/translation/exploring-custom-radio-button-in-flutter/2021-08-24-07-49-36.png)] 原文 https://medium.com/flutterdevs/exploring-cu…...

1688API、获得商品快递费用

本帖只展示部分代码及接口 需了解更多或开发系统请移步注册测试 http://console.open.onebound.cn/console/?iRookie 测试请求地址: http://open.onebound.cn/test/? { “item”: { “num_iid”: “591734471276”, “location”: null, “area_id”: “2274”, “shipping_…...

搜索: DFS + 剪枝:木棒

题目链接&#xff1a;https://www.acwing.com/problem/content/169/ 题目&#xff1a; 乔治拿来一组等长的木棒&#xff0c;将它们随机地砍断&#xff0c;使得每一节木棍的长度都不超过 50 个长度单位。 然后他又想把这些木棍恢复到为裁截前的状态&#xff0c;但忘记了初始时有…...

160. 相交链表

给你两个单链表的头节点 headA 和 headB &#xff0c;请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点&#xff0c;返回 null 。 图示两个链表在节点 c1 开始相交&#xff1a; 题目数据 保证 整个链式结构中不存在环。 注意&#xff0c;函数返回结果后&#…...

Prometheus rate和irate查询实现

rate 该函数用来计算某个指标在最近一个区间时间内的变化率。 比如说&#xff0c;Prometheus每15秒采集一次数据&#xff0c;当某个指标metric1的数据采集如下&#xff1a; timestampvalue15:00:001000015:00:151003015:00:301004515:00:4510090 假设当前时间为15:00:50&…...

OpenGl 基本函数 glDrawArrays 详解

本文章是转载&#xff1a;下面的几张图一目了然&#xff0c;很不多。 https://www.cnblogs.com/lxb0478/p/6381677.html glDrawArrays的功能&#xff1a;提供绘制功能&#xff0c;从数组数据中提取数据渲染基本图元。 定义 void glDrawArrays( GLenum mode, GLint first…...

清新简约教育培训汇报总结PPT-朴尔PPT

清新简约教育培训汇报总结PPT模板。一套,总结报告,工作汇报,幻灯片模板&#xff0c;内含黄色,红色多种配色&#xff0c;简约,小清新,卡通风风格设计&#xff0c;动态播放效果&#xff0c;精美实用。 希望下面这份精美的PPT模板能帮助到你 基本信息 用途&#xff1a;,总结报告…...

【AI视野·今日CV 计算机视觉论文速览 第220期】Wed, 16 Jun 2021

AI视野今日CS.CV 计算机视觉论文速览 Wed, 16 Jun 2021 Totally 76 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computer Vision Papers Is this Harmful? Learning to Predict Harmfulness Ratings from Video Authors Johan Edstedt, Johan Karlsson, Franci…...

centos7 yum安装使用时提示 cannot find a valid baseurl for repo:base/7/x86_64 的解决方法(亲测有效!)

一、报错原因 机子解析不了yum源,原因有三种情况&#xff1a; &#xff08;1&#xff09;电脑不能上网。请检查好网络配置&#xff0c;确认是可以上网了再看第二种情况。简单点就是ping一个公网的IP&#xff0c;如ping 114.114.114.114 如果ping不通&#xff0c;就是上不了网。…...

Linux线程总结

Linux 线程总结简述常用的线程相关API函数原型(3、4、5)线程创建、等待、退出API使用创建线程、等待线程线程退出、传参线程间共享数据(全局变量)互斥锁相关API使用简述互斥锁的作用互斥锁与全局变量配合使用死锁条件变量相关API的使用简述条件变量的使用条件变量的使用测试---…...

【RTT】SPI Flash 与文件系统(2):FAL

参考文档&#xff08;国内&#xff09;&#xff1a;FAL 参考文档 一、概述 FAL (Flash Abstraction Layer) &#xff0c;即 Flash 抽象层&#xff0c;是对 Flash 及基于 Flash 的分区进行管理、操作的抽象层&#xff0c;对上层统一了 Flash 及 分区操作的 API。 对于 FAL 的依赖…...

数据库索引高频面试题:java类的继承关系

前言 今天我们来说说Redis为什么高性能&#xff1f;如何做高可用&#xff1f; Redis为什么这么快&#xff1f; Redis是单线程的&#xff0c;避免了多线程的上下文切换和并发控制开销&#xff1b;Redis大部分操作时基于内存&#xff0c;读写数据不需要磁盘I/O&#xff0c;所以速…...

数据库事物隔离级别

数据库事务的隔离级别有4种&#xff0c;由低到高分别为Read uncommitted 、Read committed 、Repeatable read 、Serializable 。而且&#xff0c;在事务的并发操作中可能会出现脏读&#xff0c;不可重复读&#xff0c;幻读。下面通过事例一一阐述它们的概念与联系。 Read unc…...

推荐学习!超全Android中高级面试复习大纲,大厂面经合集

前言 这些题目是网友去美团等一线互联网公司面试被问到的题目。笔者从自身面试经历、各大网络社交技术平台搜集整理而成&#xff0c;熟悉本文中列出的知识点会大大增加通过前两轮技术面试的几率。 主要分为以下几部分&#xff1a; &#xff08;1&#xff09;Android面试题 …...

用户增长——Cohort Analysis 留存分析(三)

转载于:Cohort Analysis&#xff1a;用户在哪一步离开了我们的产品&#xff1f; 数据是会骗人的&#xff0c;尤其是平均数据&#xff08;真实世界会有用户每个月下单2.5次吗&#xff1f;很可能是两个分别下单1次和4次的客户而已&#xff09;&#xff0c;一个中等的平均的用户画…...

网站服务01-网站服务原理--(linux运维14)

网站服务原理1. 网站页面访问流程2.HTTP协议资源信息3. 评测网站好坏的指标1. 网站页面访问流程 客户端 浏览器输入要访问的地址 回车客户端完成域名的解析过程&#xff08;DNS&#xff09;客户端直接访问相应的网站服务器 建立tcp三次握手客户端 访问网站服务器 发送http请求…...

使用RAK7268网关与RAK3172节点连接至TTN最新的服务器TTS上

一、背景 当需要连接网关到TTN的时候我们突然发现&#xff1a;在TTN V2版本上已经无法创建新的网关了。另外&#xff0c;V2版本对于当前已创建的网关支持在今年年底也要失效了。所以&#xff0c;我们需要了解如何将网关连接到TTN最新的服务器TTS上。 二、目的 本文将会使用到RA…...

Xshell无法连接,centos7 network.service 网络服务无法启动或启动自动关闭

在虚拟中下载安装mysql之后&#xff0c;对NetworkManager进行操作&#xff0c;导致与Network服务可能起了冲突&#xff0c;使得导致network.service启动自动关闭&#xff0c;Xshell对虚拟机无法进行链接。 需要对NetworkManager进行调整 # 停止 NetworkManager 系统服务 syste…...

求一款能够批量采集新浪微博相册图片的软件,适合电脑小白使用

新浪微博是我们生活中非常常见的一款社交软件&#xff0c;我们常常会在这上面获取到很多当下热门的信息&#xff0c;大家还会在上面分享自己的日常&#xff0c;很多明星都会使用的一个平台&#xff0c;那如果我们想要下载保存某一个喜欢的博主、明星的相册图片&#xff0c;要怎…...

【JS011】ES6的学习笔记之原始数据类型Symbol

日期&#xff1a;2021年8月23日 作者&#xff1a;Commas 注释&#xff1a;如果您觉得有所帮助&#xff0c;帮忙点个赞&#xff0c;也可以关注我&#xff0c;我们一起成长&#xff1b;如果有不对的地方&#xff0c;还望各位大佬不吝赐教&#xff0c;谢谢^ - ^ (ง •_•)ง 积跬…...

VMware 仅主机模式虚拟机无法 ping 通物理机的问题

前言 最近做了另外一个项目&#xff0c;用的数据库软件版本比较新&#xff0c;我本机装的旧的&#xff0c;因版本原因无法还原数据库&#xff0c;考虑到以最快速度部署开发环境&#xff0c;决定在虚拟机里安装新版数据库软件&#xff0c;使用 VMware 网络类型的仅主机模式&…...

Seurat学习:如何将自定义的聚类标签添加到Seurat对象当中

假如要添加k-means聚类标签&#xff1a; objectmeta.data$k.means.clusters <- k.means.result 绘制自定义标签的UMAP图&#xff1a; DimPlot(object , reduction‘umap’,group.by “k.means.clusters”) 同时显示自定义标签和UMAP图和Seurat中louvain聚类的UMAP图 plot…...

Spring框架的入门知识点

一、概念 1.一款轻量级的JAVAEE解决方案&#xff0c;众多优秀设计模式的组合&#xff1b; 2.作用&#xff08;目的&#xff09;&#xff1a;解耦合&#xff0c;目的是为了解决企业级应用开发的业务逻辑层和其他各层的耦合问题。 3. Spring 的核心思想是&#xff1a; IOC:控制…...

【数据库系统概论(王珊)】第4章——数据库安全性

1、安全性级别 TCSEC将系统划分为四组&#xff08;ABCD&#xff09;七个等级&#xff0c;依次是D、C1、C2、B1、B2、B3、A1。 D级&#xff1a;是最低级别。将一切不符合更高标准的系统均归于D组。如DOS实操作系统中安全标准为D级的典型例子。 C1级&#xff1a;非…...

一句话让spring-boot帮我开启浏览器参数内容协商策略

一句话&#xff1a; 背后的原理&#xff1a; 当我们开启参数协商以后在RequestResponseBodyMethodProcessor里 有个方法 有个writeWithMessageConverter 这里包含消息的读和写操作 进入查看发现&#xff1a; 里面有个获取request的可以接受的类型 继续进入 调用了一个内容协…...

html标签字符,在thymeleaf中非转义显示

html标签字符&#xff0c;在thymeleaf中非转义显示 对于“非转义文本”使用 th:utext th:utext"${lastAnnouncement.content}"th:text和 th:utext效果对比&#xff1a; <p><strong>This is my textarea to be replaced with CKEditor 4.</strong&g…...

小白怎么入门大数据行业 自学课程内容有哪些

大数据行业人才的巨缺&#xff0c;企业对技术人才的渴求&#xff0c;激发了一批对大数据技术感兴趣的人的的学习欲望。小白怎么入门大数据行业&#xff1f;自学课程的内容有哪些&#xff1f;对于大数据的学习&#xff0c;千万不能盲目学习&#xff0c;先要找准方向&#xff0c;…...

通话蓝牙耳机什么牌子好?通话工作蓝牙耳机推荐

在一般人的印象中&#xff0c;蓝牙耳机主要是用于听听歌、打打游戏还有煲剧&#xff0c;&#xff0c;而对经常经常外出的商务差旅人士和音乐发烧友来说&#xff0c;蓝牙耳机的通话和续航也是重点关注的&#xff0c;因此&#xff0c;笔者专门整理了一些通话效果好的蓝牙耳机&…...

软件代码格式规范

正好国庆&#xff0c;整理并且编写下这篇文章来说说编程代码格式规范&#xff0c;使代码更加精简、整洁和清晰。开发人员编写出简洁、可维护、可靠、可测试、高效、可移植的代码。从长远来看&#xff0c;不仅利于别人看懂&#xff0c;也利于代码管理和使用。 一、注释规范 1&…...

黑客软件编写基础知识锦囊

确定Windows和windows系统目录 有两个SDK函数可以完成该功能。GetWindowsDirectory和GetSystemDirectory&#xff0c;下例说明了如何使用这两个函数&#xff1a; TCHAR szDir [MAX_PATH]; //Get the full path of the windows directory. :: GetWindowsDirectory (szDir, MAX_P…...

[附源码]计算机毕业设计基于springboot的家政服务平台

项目运行 环境配置&#xff1a; Jdk1.8 Tomcat7.0 Mysql HBuilderX&#xff08;Webstorm也行&#xff09; Eclispe&#xff08;IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持&#xff09;。 项目技术&#xff1a; SSM mybatis Maven Vue 等等组成&#xff0c;B/S模式 M…...

Twice-JavaSE01

狂神学习路线&#xff1a; 今天又重头开始复习Java了&#xff0c;不顾一切往前冲吧。 空常量null不能直接输出。其他几种基本数据类型可以直接输出。 定义变量时要给赋值才行&#xff0c;浮点型默认为double,float类型后要加f. 注意&#xff1a;byte和short不能直接跟char做…...

坑1438

能说理由么&#xff0c;以前总是被一多了一个空格符坑&#xff0c;今儿又遇到多了在1438的几行空白&#xff0c;删去多余的空间就没事了 爪尖啊爪贱 转载于:https://www.cnblogs.com/alex-13/archive/2013/05/23/3095049.html...

力扣1438.绝对差不超过限制——python

题目中我们需要不断的进行两两比较&#xff0c;感觉用到itertools包应该是个不错的选择&#xff0c;罗列出所有的两两组合进行比较&#xff0c;但是很可惜&#xff0c;是一个超时的答案 import itertools x[10,1,2,4,7,2] k 5 right 0 left 0 res 0 while right < len(…...

1438oracle,ORA1438 during rollup

Hi,Loading from flat file to info cube successful but rollup to aggregates is giving a sql error ORA1438 which isSQL-ERROR: 1.438 ORA-01438: value larger than specified precision allowed for this column.I managed to rollup several requests only one reques...

leetcode1438

leetcode1438 2021/2/21 绝对差不超过限制的最长连续子数组 给你一个整数数组 nums &#xff0c;和一个表示限制的整数 limit&#xff0c;请你返回最长连续子数组的长度&#xff0c;该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。如果不存在满足条件的子数…...

oracle -1438,IMP-00058, ORA-1438

Subject: Import Fails with IMP-00058, ORA-1438 Errors Doc ID: Note:185229.1 Type: PROBLEM Last Revision Date: 28-JUL-2005 Status: PUBLISHED fact: Oracle Server - Enterprise Edition fact: Export Utility (EXP) fact: Import Utility (IMP) symptom: Running an...

洛谷P1438 无聊的数列

题目背景 无聊的YYB总喜欢搞出一些正常人无法搞出的东西。有一天&#xff0c;无聊的YYB想出了一道无聊的题&#xff1a;无聊的数列。。。&#xff08;K峰&#xff1a;这题不是傻X题吗&#xff09; 题目描述 维护一个数列{a[i]}&#xff0c;支持两种操作&#xff1a; 1、1 L R K…...

codeforces1438C Engineer Artem (#682 Div2)

题目链接&#xff1a; https://codeforces.com/problemset/problem/1438/C 题目大意&#xff1a; 给你一个n*m的矩阵a&#xff0c;每个位置一个数字&#xff0c;现在你可以对每一个位置进行一次操作&#xff0c; 使得这个位置的数字1或者不变&#xff0c;问你在对所有位置进…...

CF1438 C. Engineer Artem

Artem is building a new robot. He has a matrix a consisting of n rows and m columns. The cell located on the i-th row from the top and the j-th column from the left has a value ai,j written in it. If two adjacent cells contain the same value, the robot w...

codeforces 1438C、Engineer Artem

题目 题意&#xff1a;给一个二维数组&#xff0c;对对每个元素可以进行不变和加以的操作&#xff0c;使得相邻的两个元素的不相同 思路&#xff1a;令二维数组的横坐标为i,纵坐标为j&#xff0c;当ij为偶数的时候令a[i][j]为偶数&#xff0c;当ij为奇数的时候令a[i][j]为奇数…...

mysql generator 中文注释_GitHub - orange1438/mybatis-generator-core-chinese-annotation-1.3.5: mybatis-ge

mybatis-generator-core-chinese-annotation(已删除ibatis2内容)介绍该项目是mybatis-generator-core 1.3.5 进行自定义注解生成的修改&#xff0c;mybatis-generator-core 1.3.5官方下载地址&#xff0c;主要添加中文注释信息&#xff0c;详细修改内容如下&#xff1a;1.生成m…...

HDU 1438(钥匙计数之一)

#include <iostream> #include <cmath> using namespace std; const int MAXN 35;int main() {__int64 a[MAXN], b[MAXN];a[2] 0; b[2] 0;a[3] 8; b[3] 4;for (int i 4; i < 32; i){a[i] 4 * a[i - 1];a[i] (__int64)(pow(2.0, i - 1) * 2) - 4;__int6...

[leetcode]1438. 绝对差不超过限制的最长连续子数组

个人博客&#xff1a;https://javaniuniu.com/难度&#xff1a;中等本题涉及算法&#xff1a; 滑动窗口思路&#xff1a;滑动窗口类似题型&#xff1a; 3. 无重复字符的最长子串5393. 可获得的最大点数 题目 1438. 绝对差不超过限制的最长连续子数组 给你一个整数数组 nums &…...

leetcode1438. 绝对差不超过限制的最长连续子数组

给你一个整数数组 nums &#xff0c;和一个表示限制的整数 limit&#xff0c;请你返回最长连续子数组的长度&#xff0c;该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。 如果不存在满足条件的子数组&#xff0c;则返回 0 。 示例 1&#xff1a; 输入&#…...

力扣刷题笔记:1438. 绝对差不超过限制的最长连续子数组(滑窗模板题,选择有序列表SortedList()数据类型就不会超时)

题目&#xff1a; 1438、绝对差不超过限制的最长连续子数组 给你一个整数数组 nums &#xff0c;和一个表示限制的整数 limit&#xff0c;请你返回最长连续子数组的长度&#xff0c;该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。 如果不存在满足条件的子数…...