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

C++—非递归【循环】遍历二叉树(前序,中序,后序)思路讲解+代码实现

非递归遍历二叉树

  • 前序
  • 中序
  • 后序

接下来我们在研究如何使用循环实现遍历二叉树时,以下面的二叉树为例:
在这里插入图片描述
在下文的讲解中,不对如何构建这颗二叉树做讲解,直接给出代码,如果有不懂的地方欢迎私信我。

文章中的完整源代码链接在结尾处。

前序

先来讲解前序。
前序的遍历顺序为:根-左-右,所以以上面的这棵树为例,前序遍历的结果就应该为:3 1 0 2 4 5
我们要遍历这颗树,不适用递归的话,就只能使用循环的方式来了。

思路讲解:
根据前序的遍历顺序我们不难发现,我们首先要先将根节点和左子树遍历完才能遍历右子树,所以我们可以先循环遍历到这颗树的最左结点,同时将结点的值存放在vector中。如下图所示:
在这里插入图片描述
接下来我们就要考虑的是,如何遍历右子树的问题。
其实也不难,我们只需要使用一个栈,在vector存在结点的值的同时,将结点也存放在栈结构中即可,即在上图的遍历完成后我们还能得到一个下图所示的栈:
在这里插入图片描述
在上图中我们已经完成了0结点和0结点的左子树的遍历,因为0结点的左子树为空所以本次循环结束,接下来我们只需要取栈顶元素,即0结点,让栈顶元素的右子树按照同样的方式进行遍历即可。

因为0的右子树也为空,所以下次循环直接结束,再取栈顶元素的时候,因为0已经被取走了,再取就是1结点了,1结点的右子树不为空,所以2入vector和栈。
上诉过程如下图所示:
在这里插入图片描述
然后就是以同样的方式去遍历整颗树。
代码如下:

//前序遍历
vector<int> preorderTraversal(TreeNode* root) 
{//非递归,借助栈来实现//分为两大的问题,一,左路结点, 二,左路节点的右子树stack<TreeNode*> st;vector<int> arr;TreeNode* cur = root;while (cur || !st.empty()){//1.先访问左路结点while (cur){st.push(cur);arr.push_back(cur->val);cur = cur->left;//向左走,先把左路结点全部放到栈}//2.开始处理最左结点的右子树问题TreeNode* top = st.top();st.pop();//访问每个左路结点的右子树就是上述过程的子问题,把左节点的第一个右结点//看成一个树的根节点。cur = top->right;}return arr;
}

测试结果:
在这里插入图片描述

中序

中序的遍历和前序本质上没有太大的区别,一定要在理解前序之后再来看中序。
这里先直接给出代码,再给代码进行解释:

//中序遍历
vector<int> inorderTraversal(TreeNode* root) {//思路跟前序的非递归相似stack<TreeNode*> st;vector<int> arr;TreeNode* cur = root;while (cur || !st.empty()){while (cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();st.pop();arr.push_back(top->val);cur = top->right;//一个结点从栈中出来就意味着,它和它的左子树访问完了}return arr;
}

因为中序遍历的顺序是:左-根-右。
所以在遍历到最左结点的时候,不应该直接入vector中,而是在取栈顶元素的时候,将其值入到vector中去。

认真观察我们可以发现一点:一个结点如果出栈的话,就代表这个结点的左子树肯定是遍历完了的!!

后序

后序就需要先遍历完左右子树再去处理根节点了。
讲解以注释的形式给出了,按照代码的思路去走一遍才能更好的理解。

//后序遍历
vector<int> postorderTraversal(TreeNode* root) {//思路跟前序的非递归相似stack<TreeNode*> st;vector<int> arr;TreeNode* cur = root;TreeNode* prev = nullptr;while (cur || !st.empty()){while (cur){st.push(cur);cur = cur->left;}TreeNode* top = st.top();if (top->right == nullptr || top->right == prev){//满足第一个条件的时候,处理的就是左结点//满足第二个条件的时候,处理的就是根结点,,在满足第二个条件的时候,就说明左右子树都处理完了arr.push_back(top->val);prev = top;st.pop();}elsecur = top->right;//开始遍历右子树}return arr;
}

测试结果:
在这里插入图片描述

点此处->源代码链接

相关文章:

C++—非递归【循环】遍历二叉树(前序,中序,后序)思路讲解+代码实现

非递归遍历二叉树 前序中序后序 接下来我们在研究如何使用循环实现遍历二叉树时&#xff0c;以下面的二叉树为例&#xff1a; 在下文的讲解中&#xff0c;不对如何构建这颗二叉树做讲解&#xff0c;直接给出代码&#xff0c;如果有不懂的地方欢迎私信我。 文章中的完整源代码链…...

前端002_初始化项目

1、命名和启动项目 将目录名 vue-admin-template-master 重命名为 db-manager-system 将 db-manager-system/package.json 中的 name 值改为 db-manager-system {"name": "db-manager-system","version": "1.0.1","descriptio…...

组合设计模式

组合模式 组合模式定义使用场景1、文件系统的目录结构&#xff1a;2、组织架构图&#xff1a;3、菜单和菜单项&#xff1a;4、使用场景总结&#xff1a; 角色定义Component 抽象构件角色:Leaf 叶子构件:Composite 树枝构件: 需求背景代码实现Component&#xff08;抽象构件角色…...

【MySQL】多表查询

上一篇介绍了外键约束,外键约束是用于连接两张数据表的,所以在此基础上就有了多表查询 之前的查询都是单表查询,这里我们会将多个数据表的数据结果返回在一张表上 文章目录 1.多表关系2.多表查询2.1 多表查询分类2.2 内连接2.3 外连接2.4 自连接2.5 联合查询2.6子查询 1.多表关…...

关于在线帮助中心你需要思考以下几个问题

搭建帮助中心是大多数企业都在尝试做的事情&#xff0c;它的重要性对于企业来说不言而喻。现在对于企业来说&#xff0c;搭建帮助中心或许不是什么难事&#xff0c;但是关于帮助中心&#xff0c;有几个问题需要思考清楚&#xff0c;才能让其发挥最大的价值。 一、如何让用户养成…...

基于FPGA+JESD204B 时钟双通道 6.4GSPS 高速数据采集模块设计(一)总体方案

本章将根据高速数据采集指标要求&#xff0c;分析并确定高速数据采集模块的设计方 案&#xff0c;由此分析数据存储需求及存储速度需求给出高速大容量数据存储方案&#xff0c;完成 双通道高速数据采集模块总体设计方案&#xff0c;并综合采集、存储方案及 AXIe 接口需求 …...

二、Spring Cloud Alibaba环境搭建

一、依赖环境 SpringCloud Alibaba 依赖 Java 环境来运行。还需要为此配置 Maven环境&#xff0c;请确保是在以下版本环境中安装使用。 64 bit JDK 1.8;Maven 3.2.x。 spring-cloud-alibaba相关网址&#xff1a; 地址&#xff1a;https://github.com/alibaba/spring-cloud-…...

瑞萨e2studio(24)----电容触摸配置(1)

瑞萨e2studio.24--电容触摸配置1 概述硬件准备新建工程工程模板保存工程路径芯片配置工程模板选择时钟配置添加TOUCH驱动配置CapTouch开启调优界面启动 CapTouch 调优通过电容触摸点亮LED 概述 这篇文档将创建一个使用 e2 studio 集成 QE 的电容式触摸应用示例&#xff0c;通…...

数据开发常见问题

目录 环境变量过多或者参数值过长时&#xff0c;为什么提交作业失败&#xff1f; 为什么Shell作业状态和相关的YARN Application状态不一致&#xff1f; 创建作业和执行计划的区别是什么&#xff1f; 如何查看作业运行记录&#xff1f; 如何在OSS上查看日志&#xff1f; 读…...

Ae:橡皮擦工具

橡皮擦工具 Eraser Tool 快捷键&#xff1a;Ctrl B 橡皮擦工具 Eraser Tool在工作原理上同 Ae 中的其它绘画工具&#xff08;画笔、仿制图章&#xff09;工具基本一致&#xff0c;都是通过绘制路径&#xff0c;然后基于此路径进行描边&#xff08;可统称为“绘画描边”&…...

干货 | 正确引用参考文献的6大技巧

Hello&#xff0c;大家好&#xff01; 这里是壹脑云科研圈&#xff0c;我是喵君姐姐&#xff5e; 对于学术研究而言&#xff0c;正确引用参考文献非常重要。参考文献不仅展现了自己的学术水平&#xff0c;同时也给研究定位&#xff0c;突显研究在前人研究基础上作出的贡献。 …...

区块链系统探索之路:基于椭圆曲线的私钥与公钥生成

前两节我们探讨了抽象代数的重要概念&#xff1a;有限域&#xff0c;然后研究了基于椭圆曲线上点的怪异”“操作&#xff0c;两者表面看起来牛马不相及&#xff0c;实际上两者在逻辑上有着紧密的联系&#xff0c;简单来说如果我们在椭圆曲线上取一点G,然后让它跟自己做”“操作…...

Linux命令集(Linux常用命令--echo指令篇)

Linux命令集&#xff08;Linux常用命令--echo指令篇&#xff09; Linux常用命令集&#xff08;echo指令篇&#xff09;2.echo(echo)1. 输出自定义内容2. 禁止输出末尾换行符3. 转义功能4. 与特殊字符配合使用实现其余功能 Linux常用命令集&#xff08;echo指令篇&#xff09; 如…...

【电子学会】2023年03月图形化一级 -- 甲壳虫走迷宫

甲壳虫走迷宫 1. 准备工作 &#xff08;1&#xff09;绘制如图所示迷宫背景图&#xff0c;入口在左下角&#xff0c;出口在右上角&#xff0c;线段的颜色为黑色&#xff1b; &#xff08;2&#xff09;删除默认小猫角色&#xff0c;添加角色&#xff1a;Beetle&#xff1b; …...

老外从神话原型中提取的12个品牌个性

老外从神话原型中提取的12个品牌个性 也是西方视角&#xff0c;需要本土化 参照心理学大师荣格的理论&#xff1a;心理学潜意识派 趣讲大白话&#xff1a;品牌的调调是啥 【趣讲信息科技151期】 **************************** 12种原型又归属于4种人性动机。 1、稳定&#xff0…...

unity中的Quaternion.AngleAxis

介绍 unity中的Quaternion.AngleAxis 方法 Quaternion.AngleAxis() 函数是 Unity 引擎中的一个数学函数&#xff0c;用于创建一个绕着某个轴旋转一定角度的旋转四元数。在游戏开发中&#xff0c;经常会用到该函数来旋转物体或计算旋转后的方向向量。 该函数的函数原型为&…...

如何设置渗透测试实验室

导语&#xff1a;在本文中&#xff0c;我将介绍设置渗透实验室的最快方法。在开始下载和安装之前&#xff0c;必须确保你使用的计算机符合某些渗透测试的要求&#xff0c;这可以确保你可以一次运行多个虚拟机而不会出现任何问题。 在本文中&#xff0c;我将介绍设置渗透实验室的…...

Java时间类(八)-- Instant (时间戳类)(常用于Date与LocalDateTime的相互转化)

目录 1. Instant的概述: 2. Instant的常见方法: 3. Date --->Instant--->LocalDateTime 4. LocalDateTime --->Instant--->Date 1. Instant的概述...

C++模板

模板是泛型编程的基础&#xff0c;泛型编程即以一种独立于任何特定类型的方式编写代码。模板的目的是为了提高复用性&#xff0c;将类型参数化&#xff0c;函数模板作用&#xff1a;建立一个通用函数&#xff0c;其函数返回值类型和形参类型可以不具体制定&#xff0c;用一个虚…...

【JavaEE】HTML基础知识

目录 1.HTML结构 2.HTML常见标签 3.表格标签 4.列表标签 5.表单标签 ​6.select 标签 7.textarea 标签 8.无语义标签: div & span 9.标签小练习 1.HTML结构 形如&#xff1a; <body idmyId>hello</body> HTML的书写格式 标签名 (body) 放到 <…...

GitHub 热榜项目 - 日榜(2026-03-25)

GitHub 热榜项目 - 日榜(2026-03-25) 生成于&#xff1a;2026-03-25 统计摘要 共发现热门项目&#xff1a; 14 个 榜单类型&#xff1a;日榜 本期热点趋势总结 本期 GitHub 热榜呈现出 AI Agent&#xff08;智能体&#xff09;从通用化向垂直领域深耕的显著趋势。技术核心…...

c++ 20 有什么新的功能

C20 是继 C11 之后最具革命性的 C 标准更新之一&#xff0c;引入了许多强大的新特性&#xff0c;旨在提高代码的表达力、类型安全性、编译效率和开发体验。以下是 C20 的主要新功能分类总结&#xff1a;一、四大核心语言特性1. 模块&#xff08;Modules&#xff09;目的&#x…...

10分钟精通语音识别:FunASR热词定制实战指南

10分钟精通语音识别&#xff1a;FunASR热词定制实战指南 FunASR作为端到端语音识别工具包&#xff0c;其热词定制功能能够显著提升专业术语的识别准确率。在医疗、金融、科技等专业领域&#xff0c;通过简单的配置文件即可实现98%以上的专业词汇识别精度。本文将从零开始&…...

SDMatte开源大模型部署教程:supervisor托管+自动恢复,企业级稳定性保障

SDMatte开源大模型部署教程&#xff1a;supervisor托管自动恢复&#xff0c;企业级稳定性保障 1. SDMatte模型介绍 SDMatte是一款专注于高质量图像抠图的AI模型&#xff0c;特别擅长处理复杂边缘和半透明物体的提取任务。无论是电商商品图、设计素材还是专业摄影作品&#xf…...

从服务边界到性能边界:理解 ABAP CDS View 里的窄投影及其重要性

结论先讲清楚 在 ABAP CDS 语境里,很多开发者口中的 窄投影,本质上并不是一个独立的官方语法关键字,而是一种建模策略:在 CDS projection view 这一层,只暴露某个具体业务服务真正需要的那一小部分字段、关联、行为和注解,不把底层业务对象里所有能拿到的内容一股脑端出…...

ABAQUS有限元模型:基于CEL算法的斜桩锤击入土模拟

ABAQUS有限元模型&#xff1a;基于cel算法的斜桩锤击入土模型。 使用ABAQUS有限元软件&#xff0c;基于CEL算法&#xff0c;模拟了斜桩通过锤击作用入土的情况&#xff0c;首先进行了土体的地应力平衡&#xff0c;然后对斜桩施加轴力方向的锤击荷载&#xff0c;以1.5s为循环&am…...

RT-Thread内核启动流程与自动初始化机制详解

RT-Thread内核启动流程深度解析1. RT-Thread内核架构概述RT-Thread是一款开源的实时操作系统(RTOS)&#xff0c;其内核设计采用模块化架构&#xff0c;主要由两大部分组成&#xff1a;1.1 内核库实现内核库是RT-Thread独立运行的基础设施&#xff0c;提供了一套精简的C库函数实…...

百川2-13B量化版调优指南:提升OpenClaw任务成功率的关键参数

百川2-13B量化版调优指南&#xff1a;提升OpenClaw任务成功率的关键参数 1. 为什么需要专门调优百川模型参数&#xff1f; 第一次用OpenClaw对接百川2-13B量化版时&#xff0c;我遇到了典型的"自动化尴尬"——明明是个简单的文件整理任务&#xff0c;AI却总在奇怪的…...

论文aigc检测率多少算正常?超标后怎么快速降AI率达标?

论文aigc检测率多少算正常&#xff1f;超标后怎么快速降AI率达标&#xff1f; “我的论文AIGC检测率38%&#xff0c;这算正常吗&#xff1f;” “室友的才12%&#xff0c;我的47%&#xff0c;是不是完蛋了&#xff1f;” “学校说不能超过30%&#xff0c;我现在31%&#xff0c;…...

OpenClaw成本控制:GLM-4.7-Flash任务执行的Token消耗优化策略

OpenClaw成本控制&#xff1a;GLM-4.7-Flash任务执行的Token消耗优化策略 1. 为什么需要关注OpenClaw的Token消耗&#xff1f; 第一次用OpenClaw完成整夜的数据整理任务后&#xff0c;我收到了账单提醒——单次任务消耗了超过18万Token。这个数字让我意识到&#xff0c;如果不…...