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

2024王道408数据结构P144 T18

2024王道408数据结构P144 T18

思考过程

  1. 首先还是先看题目的意思,让我们在中序线索二叉树里查找指定结点在后序的前驱结点,这题有一点难至少对我来说…我讲的不清楚理解一下我做的也有点糊涂。
  2. 在创建结构体时多两个变量ltag和rtag,当ltag=0时就说明该结点有左孩子,当ltag=1时说明该结点的lchild指向它的前驱结点
  3. 那么我们需要把一个二叉树给中序线索化,线索化后假设有这么一颗二叉树请添加图片描述之后要查找指定结点在后序的前驱结点有这么五种情况,假设指定结点为指针p:
    • 如果p有右孩子,那么在后序的前驱结点也就是该结点的右孩子if(p->rtag==0)从上面那个二叉树来看很明显。
    • 如果p没有右孩子但是有左孩子,那么在后序的前驱结点也就是改结点的左孩子if(p->ltag==0)比如上图的结点B,当B没有右孩子但是有左孩子时,在后序序列中的前驱结点也就是它的左孩子D。
    • 如果p是中序遍历中的第一个结点的话,那么在后序遍历中也必定是第一个结点if (p->lchild==NULL)这时候也就说明该结点没有前驱结点,我们直接q=NULL就好了。
    • 第四种情况就是该结点没有左右孩子,比如下图这种情况请添加图片描述这棵树中的C结点就是没有左右孩子的,此时它在后序序列中的前驱结点就是先要找到该结点的祖先, while (p->ltag == 1 && p->lchild != NULL) p = p->lchild;找到祖先后那也就是该祖先结点的左孩子。if (p->ltag == 0) q = p->lchild;
    • 那最后一种情况就是一棵树中既没有左孩子也没有右孩子,只有一个孤零零的结点,此时也就是q=NULL;

完整代码

//
// Created by 黎圣  on 2023/8/29.
//
//在中序线索二叉树里查找指定结点在后序的前驱结点
#include "iostream"
using namespace std;
typedef struct TreeNode
{char data;struct TreeNode *lchild, *rchild;int ltag, rtag;
}*tree;
void CreateTree(tree &t)
{char ch = getchar();if (ch == '#')t = NULL;else{t = (struct TreeNode *)malloc(sizeof(struct TreeNode));t->data = ch;t->lchild = NULL;t->rchild = NULL;t->ltag = t->rtag = 0;CreateTree(t->lchild);CreateTree(t->rchild);}
}
struct TreeNode *pre;
void zx(tree &t)
{if (t){zx(t->lchild);if (t->lchild == NULL){t->ltag = 1;//无左孩子t->lchild = pre;}elset->ltag = 0;//有左孩子if (pre != NULL && pre->rchild == NULL){pre->rtag = 1;pre->rchild = t;}pre = t;zx(t->rchild);}
}
tree Inpostpre(tree &t, struct TreeNode *p)
{struct TreeNode *q;//结果指针if (p->rtag == 0)//有右孩子就是右孩子q = p->rchild;else if (p->ltag == 0)//没有右孩子有左孩子就是左孩子q = p->lchild;else if (p->lchild == NULL)q = NULL;else{while (p->ltag == 1 && p->lchild != NULL)p = p->lchild;//若找到祖先结点 且有左孩子 结果就是左孩子if (p->ltag == 0)q = p->lchild;elseq = NULL;}return q;
}
int main()
{tree t;CreateTree(t);//ABD##E##CF##G##zx(t);printf("%c ", Inpostpre(t, t->rchild)->data);return 0;
}

相关文章:

2024王道408数据结构P144 T18

2024王道408数据结构P144 T18 思考过程 首先还是先看题目的意思,让我们在中序线索二叉树里查找指定结点在后序的前驱结点,这题有一点难至少对我来说…我讲的不清楚理解一下我做的也有点糊涂。在创建结构体时多两个变量ltag和rtag,当ltag0时…...

在windows下安装配置skywalking

1.下载地址 Downloads | Apache SkyWalkinghttp://skywalking.apache.org/downloads/ 2.文件目录说明 将文件解压后,可看到agent和bin目录: Agent:作为探针,安装在服务器端,进行数据采集和上报。 Config&#xff1a…...

关于大模型参数微调的不同方法

Adapter Tuning 适配器模块(Adapter Moudle)可以生成一个紧凑且可扩展的模型;每个任务只需要添加少量可训练参数,并且可以在不重新访问之前任务的情况下添加新任务。原始网络的参数保持不变,实现了高度的参数共享 Pa…...

方法的引用第一版(method reference)

1、体验方法引用 在使用Lambda表达式的时候,我们实际上传递进去的代码就是一种解决方案:拿参数做操作那么考虑一种情况:如果我们在Lanbda中所指定的操作方案,已经有地方存在相同方案,那是否还有必要再重复逻辑呢&#…...

Android DataBinding 基础入门(学习记录)

目录 一、DataBinding简介二、findViewById 和 DataBinding 原理及优缺点1. findViewById的优缺点2. DataBinding的优缺点 三、Android mvvm 之 databinding 原理1. 简介和三个主要的实体DataViewViewDataBinding 2.三个功能2.1. rebind 行为2.2 observe data 行为2.3 observe …...

spring 错误百科

一、使用Spring出错根源 1、隐式规则的存在 你可能忽略了 Sping Boot 中 SpringBootApplication 是有一个默认的扫描包范围的。这就是一个隐私规则。如果你原本不知道,那么犯错概率还是很高的。类似的案例这里不再赘述。 2、默认配置不合理 3、追求奇技淫巧 4、…...

OpenCV基本操(IO操作,读取、显示、保存)

图像的IO操作,读取和保存方法 1.1 API cv.imread()参数: 要读取的图像 读取图像的方式: cv.IMREAD*COLOR:以彩色模式加载图像,任何图像的图像的透明度都将被忽略。这是默认参数 标志: 1 cv.IMREAD*GRAYSCALE :以…...

1.快速搭建Flask项目

一.Pear Admin Flask 官网文档:http://www.pearadmin.com/doc/index.html 1.1下载安装 # 下 载 git clone https://gitee.com/pear-admin/pear-admin-flask# 安 装 pip install -r requirements.txt1.2修改配置 applications下的config.py docker运行的修改dockerdata/conf…...

编程题四大算法思想(三)——贪心法:找零问题、背包问题、任务调度问题、活动选择问题、Prim算法

文章目录 贪心法找零问题(change-making problem)贪心算法要求基本思想适合求解问题的特征 背包问题0/1背包问题0/1背包问题——贪心法 分数背包问题 任务调度问题活动选择问题活动选择——贪心法最早结束时间优先——最优性证明 Prim算法 贪心法 我在当…...

core dump管理在linux中的前世今生

目录 一、什么是core dump? 二、coredump是怎么来的? 三、怎么限制coredump文件的产生? ulimit 半永久限制 永久限制 四、从源码分析如何对coredump文件的名字和路径管理 命名 管理 一些问题的答案 1、为什么新的ubuntu不能产生c…...

Springboot整合knife4j配置swagger教程-干货

开启swagger文档&#xff0c;直接上教程。 第一步:引入依赖 <!--swagger 依赖--><dependency><groupId>com.github.xiaoymin</groupId><artifactId>knife4j-spring-boot-starter</artifactId><version>3.0.3</version></d…...

C++ 中的 Pimpl 惯用法

C 中的 Pimpl 惯用法 介绍 Pimpl&#xff08;Pointer to Implementation&#xff09;是一种常见的 C 设计模式&#xff0c;用于隐藏类的实现细节&#xff0c;从而减少编译依赖和提高编译速度。本文将通过一个较为复杂的例子&#xff0c;展示如何使用智能指针&#xff08;如 s…...

【个人博客系统网站】统一处理 · 拦截器

【JavaEE】进阶 个人博客系统&#xff08;2&#xff09; 文章目录 【JavaEE】进阶 个人博客系统&#xff08;2&#xff09;1. 统一返回格式处理1.1 统一返回类common.CommonResult1.2 统一返回处理器component.ResponseAdvice 2. 统一异常处理3. 拦截器实现3.1 全局变量SESSI…...

深入探索PHP编程:文件操作与输入/输出(I/O)

深入探索PHP编程&#xff1a;文件操作与输入/输出&#xff08;I/O&#xff09; 在PHP编程中&#xff0c;文件操作和输入/输出&#xff08;I/O&#xff09;是不可或缺的关键部分。无论是读取、写入文件&#xff0c;还是处理上传的文件&#xff0c;这些操作都是Web开发的重要组成…...

基于jeecg-boot的flowable流程自定义业务驳回到发起人的一种处理方式

有些粉丝&#xff0c;希望对自定义业务中&#xff0c;驳回到发起人进行处理&#xff0c;比如可以重新进行发起流程&#xff0c;下面就给出一种方式&#xff0c;当然不一定是最好的方式&#xff0c;只是提供一种参考而已&#xff0c;以后可以考虑动态根据流程状态或节点信息进行…...

【大数据知识】大数据平台和数据中台的定义、区别以及联系

数据行业有太多数据名词&#xff0c;例如大数据、大数据平台、数据中台、数据仓库等等。但大家很容易混淆&#xff0c;也很容易产生疑问&#xff0c;今天我们就来简单聊聊大数据平台和数据中台的定义、区别以及联系。 大数据平台和数据中台的定义 大数据平台&#xff1a;一个…...

华为OD:IPv4地址转换成整数

题目描述&#xff1a; 存在一种虚拟IPv4地址&#xff0c;由4小节组成&#xff0c;每节的范围为0-255&#xff0c;以#号间隔&#xff0c;虚拟IPv4地址可以转换为一个32位的整数&#xff0c;例如&#xff1a; 128#0#255#255&#xff0c;转换为32位整数的结果为2147549183&#…...

2023.9 - java - 浅拷贝

与 js的浅拷贝不同&#xff1a; 在 JavaScript 中&#xff0c; Object.assign() 或 spread 运算符等方法可以实现浅拷贝&#xff0c;但只针对对象的第一层属性进行复制。如果一个对象只包含基本数据类型的属性&#xff0c;那么对浅拷贝出来的对象进行修改不会影响原始对象&…...

STM32f103入门(10)ADC模数转换器

ADC模数转换器 ADC简介AD单通道初始化代码编写第一步开启时钟第二步 RCCCLK分频 6分频 72M/612M第三步 配置GPIO 配置为AIN状态第四步&#xff0c;选择规则组的输入通道第五步 用结构体 初始化ADC第六步 对ADC进行校准编写获取电压函数初始化代码如下 Main函数编写 ADC简介 ADC…...

实训笔记8.28

实训笔记8.28 8.28笔记一、大数据计算场景主要分为两种1.1 离线计算场景1.2 实时计算场景 二、一般情况下大数据项目的开发流程2.1 数据采集存储阶段2.2 数据清洗预处理阶段2.3 数据统计分析阶段2.4 数据挖掘预测阶段2.5 数据迁移阶段2.6 数据可视化阶段 三、纯大数据离线计算项…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

从面试角度回答Android中ContentProvider启动原理

Android中ContentProvider原理的面试角度解析&#xff0c;分为​​已启动​​和​​未启动​​两种场景&#xff1a; 一、ContentProvider已启动的情况 1. ​​核心流程​​ ​​触发条件​​&#xff1a;当其他组件&#xff08;如Activity、Service&#xff09;通过ContentR…...

Java并发编程实战 Day 11:并发设计模式

【Java并发编程实战 Day 11】并发设计模式 开篇 这是"Java并发编程实战"系列的第11天&#xff0c;今天我们聚焦于并发设计模式。并发设计模式是解决多线程环境下常见问题的经典解决方案&#xff0c;它们不仅提供了优雅的设计思路&#xff0c;还能显著提升系统的性能…...