当前位置: 首页 > 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 数据可视化阶段 三、纯大数据离线计算项…...

浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)

✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义&#xff08;Task Definition&…...

uniapp 对接腾讯云IM群组成员管理(增删改查)

UniApp 实战&#xff1a;腾讯云IM群组成员管理&#xff08;增删改查&#xff09; 一、前言 在社交类App开发中&#xff0c;群组成员管理是核心功能之一。本文将基于UniApp框架&#xff0c;结合腾讯云IM SDK&#xff0c;详细讲解如何实现群组成员的增删改查全流程。 权限校验…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

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

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 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卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...