洛谷P1305 新二叉树(c嘎嘎)

题目链接:P1305 新二叉树 - 洛谷 | 计算机科学教育新生态

题目难度普及

刷题心得:做了几道这种类型的题都不用建树就可以解决,基本上还是利用好树的结构,例如这道题求前序序列(根左右)是可以用递归来求的。无非就是先从根出发,递归遍历左子树,递归遍历右子树,遇到  * 直接返回就行了。

下面奉上代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//const int N = 1e6 + 10;
char h,h1; //定义两个是为了将根节点做完参数直接传入函数 
int n;struct node
{char leftNode,rightNode;//存左右子树的节点 
}lt[130];// ASCII 范围是足够的void dfs(char x)//递归求前序遍历 
{if(x == '*' ) return; 如果是空节点,返回cout<<x;//输出 dfs(lt[x].leftNode);//递归遍历左子树 dfs(lt[x].rightNode);//递归遍历右子树 
}
int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n;cin >> h1;cin >> lt[h1].leftNode >> lt[h1].rightNode;for(int i=2; i<=n; i++){cin >> h;cin >> lt[h].leftNode;cin >> lt[h].rightNode;}dfs(h1);return 0;
}

  下面讲讲递归是如何执行的(个人理解)  

1. 初始调用:dfs(a)
  • 当前节点 a
  • 输出 a
  • 递归访问左子树:dfs(b)
2. 递归调用:dfs(b)
  • 当前节点 b
  • 输出 b
  • 递归访问左子树:dfs(d)
3. 递归调用:dfs(d)
  • 当前节点 d
  • 输出 d
  • d 没有左右子树,所以返回。
4. 回到 b,继续递归访问右子树:dfs(i)
  • 当前节点 i
  • 输出 i
  • i 没有左右子树,所以返回。
5. 回到 a,继续递归访问右子树:dfs(c)
  • 当前节点 c
  • 输出 c
  • 递归访问左子树:dfs(j)
6. 递归调用:dfs(j)
  • 当前节点 j
  • 输出 j
  • j 没有左右子树,所以返回。
7. 返回到 c,继续递归访问右子树:dfs(*)
  • 右子树是空的,所以直接返回。
8. 完成所有递归,结束遍历。

输出:

最终的输出是前序遍历的结果:

abdcij

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

(18)时间序列预测之FiLM

没错&#xff0c;就是看电影 文章目录 前言1. 问题描述2. 创新之处3. 贡献 一、时间序列在legende - fourier域的表示1. 勒让德投影2. 傅里叶变换 二、 模型结构1. LPU: Legendre Projection Unit2. FEL: Frequency Enhanced Layer3. 多尺度专家机制的混合 二、实验结果长时预测…

Linux | Linux的开机启动流程

对于linux系统的初学者来说&#xff0c;理解并掌握linux系统启动流程能够使你够深入的理解linux系统&#xff0c;还可以通过系统的启动过程来分析问题解决问题。 Linux开机启动的流程如下图 power on 开机 post自检&#xff08;检查一部分大的硬件&#xff09; BIOS&#xf…

单端和差分信号的接线法

内容来源&#xff1a;【单端信号 差分信号与数据采集卡的【RSE】【 NRES】【 DIFF】 模式的连接】 此篇文章仅作笔记分享。 单端输入 单端信号指的是输入信号由一个参考端和一个信号端构成&#xff0c;参考端一般是地端&#xff0c;信号就是通过计算信号端口和地端的差值所得…

使用 Apache Commons IO 实现文件读写

在 Java 编程中&#xff0c;文件读写是常见的操作。虽然 Java 标准库提供了基本的文件 I/O 功能&#xff0c;但使用 Apache Commons IO 库可以进一步简化这些操作&#xff0c;提高开发效率。Apache Commons IO 是一个强大的工具库&#xff0c;提供了许多实用的类和方法&#xf…

高级架构二 Git基础到高级

一 Git仓库的基本概念和流程 什么是版本库&#xff1f;版本库又名仓库&#xff0c;英文名repository,你可以简单的理解一个目录&#xff0c;这个目录里面的所有文件都可以被Git管理起来&#xff0c;每个文件的修改&#xff0c;删除&#xff0c;Git都能跟踪&#xff0c;以便任何…

智已汽车x-signature 登录算法 签到

智已汽车x-signature 登录算法 签到 python代码成品

Web3的技术栈详解:解读区块链、智能合约与分布式存储

随着数字时代的不断发展&#xff0c;Web3作为下一代互联网的核心理念逐渐走进了大众视野。它承载着去中心化、用户主权以及更高效、更安全的网络环境的期望。Web3不再是由少数中心化机构主导的网络&#xff0c;而是通过一系列核心技术的支撑&#xff0c;给每个用户赋予了更多的…

速通SpringBoot+vue全栈开发教程

本人的环境配置&#xff1a; idea 2019 java&#xff08;jdk8&#xff09; apache-maven 3.6.1 tomcat 8.5.5 mysql 8.0.12 navicat 16 一、SpringBoot快速上手——创建一个springboot项目 进去之后报红 在设置里面修改maven的配置&#xff0c;改成自己下载的maven的地址 还因…

108.【C语言】数据结构之二叉树查找值为x的节点

目录 1.题目 代码模板 2.分析 分类讨论各种情况 大概的框架 关键部分(继续递归)的详解 递归调用展开图 3.测试结果 其他写法 4.结论 5.注意事项 不推荐的写法 1.题目 查找值为x的节点并返回节点的地址 代码模板 typedef int BTDataType; typedef struct BinaryT…

AI与BI的火花:大语言模型如何重塑商业智能的未来

大家好&#xff0c;我是独孤风。 在当今这个数据驱动的时代&#xff0c;企业对于信息的需求如同对于氧气的需求一般至关重要。商业智能&#xff08;BI&#xff09;作为企业获取、分析和呈现数据的关键工具&#xff0c;正在经历一场深刻的变革&#xff0c;而这一变革的催化剂正是…

网站维护记录

服务器重启&#xff0c;网站打不开&#xff1a;chown -R manager:manager /run/php-fpm/www.sock wordpress升级需设置ftp&#xff1a; // 设置权限0777 //define("FS_METHOD", "direct"); //define("FS_CHMOD_DIR", 0777); //define("…

STL算法之其它算法_下

random_shuffle 这个算法将[first,last)的元素次序随机排列。也就说&#xff0c;在N!中可能的元素排列中随机选出一种&#xff0c;此处N为last-first。 N个元素的序列&#xff0c;其排列方式为N!中&#xff0c;random_shuffle会产生一个均匀分布&#xff0c;因此任何一个排列被…

Mysql面试专题-事务

前言 开始Mysql数据库面试知识的复习和资料的收集&#xff0c;本篇文章会不断更新&#xff0c;本系列文章主要分为两部分&#xff0c;一部分是该专题所涉及的相关基础知识&#xff0c;另一部分是面试题与思考题&#xff0c;大部分重要知识和基础知识的延伸会在面试题和思考题中…

【设计模式系列】工厂方法模式(二十一)

一、什么是工厂方法模式 工厂方法模式&#xff08;Factory Method Pattern&#xff09;是一种创建型设计模式&#xff0c;其核心目的是定义一个创建对象的接口&#xff0c;但让实现这个接口的子类来决定实例化哪一个类。工厂方法模式让类的实例化推迟到子类中进行&#xff0c;…

【Linux】文件描述符fd

1.前置预备 文件 内容 属性访问文件之前&#xff0c;都必须先打开他 #include<stdio.h> int main() { FILE* fpfopen("log.txt","w"); if(fpNULL) { perror("fopen"); return 1; } fclose(fp); return 0…

自由学习记录(29)

FileStream FileStream 是 .NET 中用于文件操作的重要类&#xff0c;位于 System.IO 命名空间中。它提供了对文件的同步和异步读写操作。以下是它的方法签名和重载的详细介绍&#xff1a; 构造函数签名和重载 FileStream 提供多个构造函数&#xff0c;允许在创建实例时指定文…

前缀和(四)除自身以外数组的乘积

238. 除自身以外数组的乘积 给你一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&…

【OpenDRIVE_Python】使用python脚本输出OpenDRIVE数据中含有隧道tunnel的道路ID和隧道信息

示例代码说明&#xff1a; 遍历OpenDRIVE数据中每条道路Road,若Road中存在隧道tunnel属性&#xff0c;则将该道路ID和包含的所有隧道信息输出到xml文件中。 import xml.dom.minidom from xml.dom.minidom import parse from xml.dom import Node import sys import os # 读取…

jmeter如何导出中文版的测试报告?

文章目录 0、初始步骤&#xff1a;把报告模板换成中文形式1、首先添加一份聚合报告2、然后点开【聚合报告】3&#xff0c;生成报告3.1 选择【工具】-【generate HTML report】3.2 【generate HTML report】参数详解3.3 、最后点击 【generate report】直接生成。 声明&#xff…

protobuf实现Hbase数据压缩

目录 前置HBase数据压缩效果获取数据(反序列化) 前置 安装说明 使用说明 HBaseDDL和DML操作 HBase数据压缩 问题 在上文的datain中原文 每次写入数据会写入4个单元格的内容&#xff0c;现在希望能对其进行筛减&#xff0c;合并成1格&#xff0c;减少存储空间&#xff08;序列…