2024王道408数据结构P144 T18
2024王道408数据结构P144 T18
思考过程
- 首先还是先看题目的意思,让我们在中序线索二叉树里查找指定结点在后序的前驱结点,这题有一点难至少对我来说…我讲的不清楚理解一下我做的也有点糊涂。
- 在创建结构体时多两个变量ltag和rtag,当ltag=0时就说明该结点有左孩子,当ltag=1时说明该结点的lchild指向它的前驱结点。
- 那么我们需要把一个二叉树给中序线索化,线索化后假设有这么一颗二叉树
之后要查找指定结点在后序的前驱结点有这么五种情况,假设指定结点为指针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;
了
- 如果p有右孩子,那么在后序的前驱结点也就是该结点的右孩子,
完整代码
//
// 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:…...

关于大模型参数微调的不同方法
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文档,直接上教程。 第一步:引入依赖 <!--swagger 依赖--><dependency><groupId>com.github.xiaoymin</groupId><artifactId>knife4j-spring-boot-starter</artifactId><version>3.0.3</version></d…...
C++ 中的 Pimpl 惯用法
C 中的 Pimpl 惯用法 介绍 Pimpl(Pointer to Implementation)是一种常见的 C 设计模式,用于隐藏类的实现细节,从而减少编译依赖和提高编译速度。本文将通过一个较为复杂的例子,展示如何使用智能指针(如 s…...

【个人博客系统网站】统一处理 · 拦截器
【JavaEE】进阶 个人博客系统(2) 文章目录 【JavaEE】进阶 个人博客系统(2)1. 统一返回格式处理1.1 统一返回类common.CommonResult1.2 统一返回处理器component.ResponseAdvice 2. 统一异常处理3. 拦截器实现3.1 全局变量SESSI…...
深入探索PHP编程:文件操作与输入/输出(I/O)
深入探索PHP编程:文件操作与输入/输出(I/O) 在PHP编程中,文件操作和输入/输出(I/O)是不可或缺的关键部分。无论是读取、写入文件,还是处理上传的文件,这些操作都是Web开发的重要组成…...
基于jeecg-boot的flowable流程自定义业务驳回到发起人的一种处理方式
有些粉丝,希望对自定义业务中,驳回到发起人进行处理,比如可以重新进行发起流程,下面就给出一种方式,当然不一定是最好的方式,只是提供一种参考而已,以后可以考虑动态根据流程状态或节点信息进行…...

【大数据知识】大数据平台和数据中台的定义、区别以及联系
数据行业有太多数据名词,例如大数据、大数据平台、数据中台、数据仓库等等。但大家很容易混淆,也很容易产生疑问,今天我们就来简单聊聊大数据平台和数据中台的定义、区别以及联系。 大数据平台和数据中台的定义 大数据平台:一个…...
华为OD:IPv4地址转换成整数
题目描述: 存在一种虚拟IPv4地址,由4小节组成,每节的范围为0-255,以#号间隔,虚拟IPv4地址可以转换为一个32位的整数,例如: 128#0#255#255,转换为32位整数的结果为2147549183&#…...

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

STM32f103入门(10)ADC模数转换器
ADC模数转换器 ADC简介AD单通道初始化代码编写第一步开启时钟第二步 RCCCLK分频 6分频 72M/612M第三步 配置GPIO 配置为AIN状态第四步,选择规则组的输入通道第五步 用结构体 初始化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 数据可视化阶段 三、纯大数据离线计算项…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
uniapp 对接腾讯云IM群组成员管理(增删改查)
UniApp 实战:腾讯云IM群组成员管理(增删改查) 一、前言 在社交类App开发中,群组成员管理是核心功能之一。本文将基于UniApp框架,结合腾讯云IM SDK,详细讲解如何实现群组成员的增删改查全流程。 权限校验…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

基于TurtleBot3在Gazebo地图实现机器人远程控制
1. TurtleBot3环境配置 # 下载TurtleBot3核心包 mkdir -p ~/catkin_ws/src cd ~/catkin_ws/src git clone -b noetic-devel https://github.com/ROBOTIS-GIT/turtlebot3.git git clone -b noetic https://github.com/ROBOTIS-GIT/turtlebot3_msgs.git git clone -b noetic-dev…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合
在汽车智能化的汹涌浪潮中,车辆不再仅仅是传统的交通工具,而是逐步演变为高度智能的移动终端。这一转变的核心支撑,来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒(T-Box)方案:NXP S32K146 与…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...