【数据结构】二叉树的三种遍历(非递归讲解)

目录

1、前言

2、二叉树的非递归遍历

2.1、先序遍历

2.2、中序遍历

2.3、后序遍历


1、前言

学习二叉树的三种非递归遍历前,首先来了解一下递归序

递归序就是按照先序遍历的顺序,遇到的所有结点按顺序排列,重复的结点也必须记录。

我们可以发现递归序中每个结点都会遇到三次。

这是因为当进入某一结点时,对该结点进行第一次操作,然后调用其左孩子结点,等左孩子结点结束调用时会返回自己,此时就可以对自己进行第二次操作,然后再调用其右孩子结点,等左孩子结点结束调用时又会返回自己,此时就可以对自己进行第三次操作,因为不管怎样,调用完孩子结点后终究会返回到父结点。

直接给出结论:

递归序中第一次遇到该节点时打印结点,第二次第三次均不做任何操作,这就是先序遍历

递归序中第二次遇到该节点时打印结点,第一次第三次均不做任何操作,这就是中序遍历

递归序中第三次遇到该节点时打印结点,第一次第二次均不做任何操作,这就是后序遍历

关于递归序详细的讲解,可以看我之前写的一篇博客,里面有详细讲解,这里就不过多赘述:

【算法与数据结构】二叉树的三种遍历代码实现(上)—— 用递归序知识点讲解-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/zzzzzhxxx/article/details/133609612?spm=1001.2014.3001.5501

2、二叉树的非递归遍历

任何递归函数都可以改成非递归函数,因为递归函数不是什么玄学,只是递归时系统帮忙解决了压栈问题。那么不用递归方式的话只要自己手动进行压栈依然可以完成递归能够实现的功能。

有了上面递归序的知识点作为铺垫,就可以很好的理解非递归的实现了。

2.1、先序遍历

递归序中第一次遇到该节点时打印结点,第二次第三次均不做任何操作,这就是先序遍历

首先使用cur依次将二叉树所有左边界节点入栈,并且打印节点。当此时cur走到叶子节点后,将栈顶元素出栈,并让cur指向出栈元素的右孩子,继续进行左边界节点入栈操作。

    public List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>();if(root == null) {return list;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while(cur != null || !stack.isEmpty()) {if(cur != null) {stack.push(cur);System.out.print(cur.val + " ");  //第一次遇到时进行打印cur = cur.left;} else {cur =  stack.pop();   //第二次遇到cur = cur.right;}}return list;}

2.2、中序遍历

递归序中第二次遇到该节点时打印结点,第一次第三次均不做任何操作,这就是中序遍历。 

首先使用cur依次将二叉树所有左边界节点入栈。当此时cur走到叶子节点后,将栈顶元素出栈后并打印,此时第二次遇到该元素。然后让cur指向出栈元素的右孩子,继续进行左边界节点入栈操作。

    public List<Integer> inorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>();if(root == null) {return list;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while(cur != null || !stack.isEmpty()) {if(cur != null) {stack.push(cur);   //第一次遇到cur = cur.left;} else {cur =  stack.pop();System.out.print(cur.val + " ");   //第二次遇到时进行打印cur = cur.right;}}return list;}

2.3、后序遍历

递归序中第三次遇到该节点时打印结点,第一次第二次均不做任何操作,这就是后序遍历

首先使用cur依次将二叉树所有左边界节点入栈。当此时cur走到叶子节点后,使用peek()查找出栈顶元素top(并非出栈)后并打印,然后判断top节点是否存在右孩子,当存在时则让cur指向top节点的右孩子,继续进行左边界节点入栈操作。当top不存在右孩子时则将栈顶元素出栈并打印栈顶元素,此时第三次遇到该元素。

    public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new LinkedList<>();if(root == null) {return list;}Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = null;while(cur != null || !stack.isEmpty()) {if(cur != null) {stack.push(cur);   //第一次遇到cur = cur.left;} else {TreeNode top = stack.peek();   //第二次遇到if(top.right != null && prev != top.right) {   //当该节点右子树不为空,并且之前没有去过右子树时cur = top.right;						} else {     //该节点右子树为空或者是已经去过一次右子树了top = stack.pop();System.out.print(cur.val + " ");   //第三次遇到时进行打印prev = top;}}}return list;}

博主推荐: 

【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/zzzzzhxxx/article/details/136030138?spm=1001.2014.3001.5501 【数据结构】二叉搜索树的模拟实现-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/zzzzzhxxx/article/details/135910604?spm=1001.2014.3001.5501

 【LeetCode力扣】面试题 17.14. 最小K个数(top-k问题)-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/zzzzzhxxx/article/details/135737266?spm=1001.2014.3001.5501

如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!

如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!

如果觉得作者写的不错,求给博主一个大大的点赞支持一下,你们的支持是我更新的最大动力!

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

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

相关文章

【数据结构】链表OJ面试题5(题库+解析)

1.前言 前五题在这http://t.csdnimg.cn/UeggB 后三题在这http://t.csdnimg.cn/gbohQ 给定一个链表&#xff0c;判断链表中是否有环。http://t.csdnimg.cn/Rcdyc 给定一个链表&#xff0c;返回链表开始入环的第一个结点。 如果链表无环&#xff0c;则返回 NULLhttp://t.cs…

大厂的供应链域数据中台设计

关注我&#xff0c;紧跟本系列专栏文章&#xff0c;咱们下篇再续&#xff01; 作者简介&#xff1a;魔都技术专家兼架构&#xff0c;多家大厂后端一线研发经验&#xff0c;各大技术社区头部专家博主&#xff0c;编程严选网创始人。具有丰富的引领团队经验&#xff0c;深厚业务架…

Linux 软件管理(YUM RPM)

1 YUM yum&#xff08;全称为 Yellow dog Updater, Modified&#xff09;是一个在Fedora和RedHat以及CentOS中的Shell前端软件包管理器。基于RPM包管理&#xff0c;能够从指定的服务器自动处理依赖性关系&#xff0c;并且一次安装所有依赖的软件包&#xff0c;无须繁琐地一次次…

算法学习——LeetCode力扣栈与队列篇1

算法学习——LeetCode力扣栈与队列篇1 232. 用栈实现队列 232. 用栈实现队列 - 力扣&#xff08;LeetCode&#xff09; 描述 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作&#xff08;push、pop、peek、empty&#xff09;&#xff1a; 实现 MyQu…

ChatGPT4 教你如何完成SQL的实践应用

对数据库的各项应用与操作都离不开SQL来对数据进行增删改查。 例如 &#xff1a; 有一张某公司职员信息表如下&#xff1a; 需求1&#xff1a;在公司职员信息表中&#xff0c;请统计各部门&#xff0c;各岗位下的员工人数。 如果这个SQL语句不会写或者不知道怎么操作可以交给…

Unity入门学习

目录 Unity环境搭建Unity引擎是什么软件下载和安装工程文件夹 Unity界面基础Scene场景和Hierarchy层级窗口Game游戏和Project工程Inspector和Console工具栏和父子关系 Unity工作原理反射机制和游戏场景预设体和资源包的导入导出 Unity脚本基础脚本基本规则生命周期函数Inspecto…

产品效果图为何要用渲染100农场?渲染100邀请码1a12

产品效果图很重要&#xff0c;它能帮助设计人员和消费者理解产品特点&#xff0c;是不可或缺的一步。产品效果图渲染耗时耗力&#xff0c;不仅慢而且容易出错&#xff0c;在这种情况下&#xff0c;使用渲染农场就成了必备选择&#xff0c;以目前国内最好的渲染农场渲染100为例&…

JAVA设计模式之原型模式详解

原型模式 1 原型模式介绍 定义: 原型模式(Prototype Design Pattern)用一个已经创建的实例作为原型&#xff0c;通过复制该原型对象来创建一个和原型对象相同的新对象。 西游记中的孙悟空 拔毛变小猴,孙悟空这种根据自己的形状复制出多个身外化身的技巧,在面向对象软件设计领…

Antd+React+react-resizable实现表格拖拽功能

1、先看效果 2、环境准备 在package.json 引入相关的依赖 "dependencies": {"antd": "^5.4.0","react-resizable": "^3.0.4",},"devDependencies": {"types/react": "^18.0.33","types…

github和gitee

github GitHub是一个面向开源及私有软件项目的托管平台&#xff0c;因为只支持Git作为唯一的版本库格式进行托管&#xff0c;故名GitHub。 github可以给提交的代码打上标签&#xff0c;方便版本的迭代和回退&#xff0c;也是一个存储代码的仓库 github工作区 gitee是gitHub的…

Oracle数据表ID自增操作

一、Oracle ID自增长功能介绍 Oracle数据库默认不支持像 SQLServer、MySQL中的自增长&#xff08;auto increment&#xff09;功能&#xff0c;即自动为每一行记录的自增长字段生成下一个值。 二、Oracle ID自增长方法 第一种&#xff0c;通过序列&#xff08;sequence&#…

第四篇:SQL语法-DDL-数据定义语言

大年初一限定篇&#x1f600; &#xff08;祝广大IT学习者、工作者0 error 0 warning&#xff01;&#xff09; 一&#xff0c;DDL数据库操作 &#xff08;一&#xff09;库的查询操作 1.列出所有已定义数据库 show databases; 2.查询当前所处数据库 select database(); &…

【Spring】Bean 的生命周期

一、Bean 的生命周期 Spring 其实就是一个管理 Bean 对象的工厂&#xff0c;它负责对象的创建&#xff0c;对象的销毁等 所谓的生命周期就是&#xff1a;对象从创建开始到最终销毁的整个过程 什么时候创建 Bean 对象&#xff1f;创建 Bean 对象的前后会调用什么方法&#xf…

使用python-numpy实现一个简单神经网络

目录 前言 导入numpy并初始化数据和激活函数 初始化学习率和模型参数 迭代更新模型参数&#xff08;权重&#xff09; 小彩蛋 前言 这篇文章&#xff0c;小编带大家使用python-numpy实现一个简单的三层神经网络&#xff0c;不使用pytorch等深度学习框架&#xff0c;来理解…

c#cad 创建-圆(二)

运行环境 vs2022 c# cad2016 调试成功 一、代码说明 这段代码是一个AutoCAD插件&#xff0c;用于在模型空间中创建一个圆形。 首先&#xff0c;我们需要定义一个命令类CreateCircleCommand&#xff0c;并在命名空间CreateCircleInCad中声明。 在CreateCircleCommand类中&a…

DNS 域名系统——应用层

目录 1 域名系统 DNS 1.1 域名系统 1.2 互联网的域名结构 1.2.1 顶级域名 TLD(Top Level Domain) (1) 国家顶级域名 nTLD (2) 通用顶级域名 gTLD (3) 基础结构域名 (infrastructure domain) 1.3 域名服务器 1.3.1 域名服务器的四种类型 &#xff08;1…

电子电器架构 —— 区域控制器是未来架构的正解吗?

电子电器架构 —— 区域控制器是未来架构的正解吗? 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师(Wechat:gongkenan2013)。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 本就是小人物,输了就是输了,不要在意别人怎么看自己。江湖一碗茶…

【数据结构】双向链表(链表实现+测试+原码)

前言 在双向链表之前&#xff0c;如果需要查看单链表来复习一下&#xff0c;链接在这里&#xff1a; http://t.csdnimg.cn/Ib5qS 1.双向链表 1.1 链表的分类 实际中链表的结构非常多样&#xff0c;以下情况组合起来就有8种链表结构&#xff1a; 1.1.1 单向或者双向 1.1.2 …

【技巧】PCB布局技巧:带条纹的电容

这些都是无极性电容&#xff0c;所以这个条纹不是极性标记。一位读者得回答正确&#xff0c;它代表电容卷绕时&#xff0c;卷绕在外层的那一极。我发现现在很少有工程师知道电容一端的条纹代表什么&#xff0c;也不知道条纹端和不带条纹端互换带来的不同效果。即使你从来不使用…

排序算法的时间复杂度存在下界问题

对于几种常用的排序算法&#xff0c;无论是归并排序、快速排序、以及更加常见的冒泡排序等&#xff0c;这些排序算法的时间复杂度都是大于等于O(n*lg(n))的&#xff0c;而这些排序算法存在一个共同的行为&#xff0c;那就是这些算法在对元素进行排序的时候&#xff0c;都会进行…