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

目录

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://xiahunao.cn/news/2774620.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

JavaScript 跨窗口通信(Cross-Window Communication)

&#x1f9d1;‍&#x1f393; 个人主页&#xff1a;《爱蹦跶的大A阿》 &#x1f525;当前正在更新专栏&#xff1a;《VUE》 、《JavaScript保姆级教程》、《krpano》、《krpano中文文档》 ​ ​ ✨ 前言 在现代 Web 开发中&#xff0c;跨窗口通信是一种常见需求。它允许在…

怎么看待梅西?回家第一天,谢谢自己!新村主任!——早读

回家第一天 引言代码第一篇 平安中原 一图读懂 | 2024年全省公安局处长会议第二篇 人民日报 【夜读】这一年&#xff0c;谢谢自己第三篇 人民日报 来了&#xff01;新闻早班车要闻社会政策 结尾 引言 今天爬的很晚&#xff0c;没想到新闻早班车也排的那么低 回家第一天 昨天出去…

代码随想录算法训练营DAY16 | 二叉树 (3)

一、LeetCode 104 二叉树的最大深度 题目链接&#xff1a;104.二叉树的最大深度https://leetcode.cn/problems/maximum-depth-of-binary-tree/ 思路&#xff1a;采用后序遍历递归求解。 class Solution {int ans 0;public int maxDepth(TreeNode root) {if(root null){retur…

猫头虎分享已解决Bug ‍ || ValueError: Found array with dim 3. Estimator expected <= 2

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

嵌入式学习之Linux入门篇笔记——15,Linux编写第一个自己的命令

配套视频学习链接&#xff1a;http://【【北京迅为】嵌入式学习之Linux入门篇】 https://www.bilibili.com/video/BV1M7411m7wT/?p4&share_sourcecopy_web&vd_sourcea0ef2c4953d33a9260910aaea45eaec8 1.什么是命令&#xff1f; 命令就是可执行程序。 比如 ls -a…

armbian ddns

参考https://mp.weixin.qq.com/s/0Uu_nbGH_W6vAYHPH4kHqg Releases jeessy2/ddns-go GitHub mkdir -p /usr/local/ddns-go cd /usr/local/ddns-gowget https://github.com/jeessy2/ddns-go/releases/download/v6.1.1/ddns-go_6.1.1_freebsd_armv7.tar.gztar zxvf ddns-go_…

用友U8+OA doUpload.jsp 文件上传漏洞

免责声明&#xff1a;文章来源互联网收集整理&#xff0c;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;所产生的一切不良后果与文章作者无关。该…

mac电脑flutter环境配置,解决疑难问题

准备工作 首先搭建flutter的环境需要使用到flutter的sdk&#xff0c;可以直接跳去官网下载&#xff1a;Choose your first type of app - Flutter 中文文档 - Flutter 中文开发者网站 - Flutter&#xff0c;下载时要注意你电脑所使用的芯片是Intel的还是苹果的芯片。 下载好的…

(C++)集合数据文件存储工具

前言 一个简单的实现简便 "map集合" 数据存储本地。 适合不会SQL但又想实现数据存储本地的同学。 操作使用都非常简单。 文件只做了简单的加密处理&#xff0c;如果需要复杂加密的同学可以修改加密函数。 项目结构 1.创建头文件——CAB.h // // Created by xw o…

【lesson47】进程通信之system V(共享内存)补充知识

文章目录 补充知识 补充知识 进行通信的key值问题&#xff0c;进程要通信的对方进程怎么能保证对方能看到&#xff0c;并且看到的就是该进程创建的共享内存的。 所以就通过key值来标识共享内存&#xff0c;key值是几不重要&#xff0c;只要在系统里是唯一的即可。 这样server和…

【动态规划】【前缀和】【数学】2338. 统计理想数组的数目

作者推荐 【动态规划】【前缀和】【C算法】LCP 57. 打地鼠 本文涉及知识点 动态规划汇总 C算法&#xff1a;前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频 LeetCode:2338. 统计理想数组的数目 给你两个整数 n 和 maxValue &#xff0c;用于描述一个 理想…

React环境配置

1.安装Node.js Node.js官网&#xff1a;https://nodejs.org/en/ 下载之后按默认选项安装好 重启电脑即可自动完成配置 2.安装React 国内使用 npm 速度很慢&#xff0c;可以使用淘宝定制的 cnpm (gzip 压缩支持) 命令行工具代替默认的 npm。 ①使用 winR 输入 cmd 打开终端 ②依…

JAVA结课作品——超市管理系统

项目描述&#xff1a;一个简单的超市管理系统&#xff0c;能够实现用户登入和注册功能&#xff0c;共分为前台和后台两个主要界面&#xff0c;普通用户界面操作权限收到限制&#xff0c;只能对商品和销售记录进行简单查询操作&#xff0c;后台中可以进行商品的删除、修改、查询…

如何使用Docker本地部署一个开源网址导航页并分享好友公网使用

&#x1f525;博客主页&#xff1a; 小羊失眠啦. &#x1f3a5;系列专栏&#xff1a;《C语言》 《数据结构》 《Linux》《Cpolar》 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;…

PHP入门指南:进阶篇

PHP入门指南&#xff1a;进阶篇 PHP入门指南&#xff1a;进阶篇1. 面向对象编程&#xff08;OOP&#xff09;1.1 类和对象的基本概念1.2 构造函数和析构函数1.3 属性和方法的访问控制1.4 继承与多态 2. 错误和异常处理2.1 错误处理机制2.2 异常处理机制2.3 自定义异常类 3. PHP…

【GAMES101】Lecture 19 相机

目录 相机 视场 Field of View (FOV) 曝光&#xff08;Exposure&#xff09; 感光度&#xff08;ISO&#xff09; 光圈 快门 相机 成像可以通过我们之前学过的光栅化成像和光线追踪成像来渲染合成&#xff0c;也可以用相机拍摄成像 今天就来学习一下相机是如何成像的…

NeRF从入门到放弃1:原理介绍

基本概念 原始的论文中所介绍的NeRF&#xff08;NeRF: Representing Scenes as Neural Radiance Fields for View Synthesis&#xff0c;用神经辐射场表示场景进行视角合成&#xff09;&#xff0c;是神经辐射场以及体积渲染技术的结合&#xff0c;即用神经辐射场隐式地表示场…

代码随想录算法训练营第29天|491.递增子序列 * * 46.全排列 * 47.全排列 II

文章目录 491.递增子序列思路&#xff1a;代码 思路&#xff1a;优化代码&#xff1a; 46.全排列思路代码一&#xff1a;使用used数组代码二&#xff1a;使用path判断元素 47.全排列 II思路一&#xff1a;层节点和路径都是用used数组做记录思路二&#xff1a;层通过排序后是否重…

【第二届 Runway短视频创作大赛】——截至日期2024年03月01日

短视频创作大赛 关于AI Fil&#xff4d; Festival竞赛概况参加资格报名期间报名方法 提交要求奖品附录 关于AI Fil&#xff4d; Festival 2022年成立的AIFF是一个融合了最新AI技术于电影制作中的艺术和艺术家节日&#xff0c;让我们得以一窥新创意时代的风采。从众多参赛作品中…

C语言笔试题之实现C库函数 strstr()(设置标志位)

实例要求&#xff1a; 1、请你实现C库函数strstr()&#xff08;stdio.h & string.h&#xff09;&#xff0c;请在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标&#xff08;下标从 0 开始&#xff09;&#xff1b;2、函数声明&#xff1a;int strStr(char* h…