【数据结构|二叉树遍历】递归与非递归实现前序遍历、中序遍历、后序遍历

递归与非递归实现二叉树的前序遍历、中序遍历、后序遍历。

二叉树图

定义

  1. 前序遍历(Preorder Traversal): 前序遍历的顺序是先访问根节点,然后按照先左后右的顺序访问子节点。对于上面的二叉树,前序遍历的结果是:4 -> 2 -> 1 -> 3 -> 6 -> 5 -> 7。

  2. 中序遍历(Inorder Traversal): 中序遍历的顺序是按照先左后根再右的顺序访问子节点。对于上面的二叉树,中序遍历的结果是:1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。

  3. 后序遍历(Postorder Traversal): 后序遍历的顺序是按照先左后右再根的顺序访问子节点。对于上面的二叉树,后序遍历的结果是:1 -> 3 -> 2 -> 5 -> 7 -> 6 -> 4。

通俗易懂

如果上面的定义看着有点晕,看这里,如上图,在这三个节点中,观察根节点2的遍历位置

前序遍历:213

中序遍历:123

后序遍历:132

总结:不管哪个遍历方式,左右相比,都是左先,1在前,3在后,根节点2依次是前、中、后,递归时把子树看成整体,逻辑同理。

代码

public class BinaryTree {public static void main(String[] args) {int[] nums = {1, 2, 3, 4, 5, 6, 7};TreeNode root = TreeNode.buildTree(nums);System.out.print("前序遍历(递归):");preorderTraversal(root);System.out.println();System.out.print("中序遍历(递归):");inorderTraversal(root);System.out.println();System.out.print("后序遍历(递归):");postorderTraversal(root);System.out.println();System.out.print("前序遍历(栈):");preorderTraversal1(root);System.out.println();System.out.print("中序遍历(栈):");inorderTraversal1(root);System.out.println();System.out.print("后序遍历(栈):");postorderTraversal1(root);System.out.println();}//前序遍历(递归)public static void preorderTraversal(TreeNode root) {if (root == null) {return;}System.out.print(root.val + " "); // 访问根节点preorderTraversal(root.left); // 访问左子树preorderTraversal(root.right); // 访问右子树}// 中序遍历(递归)public static void inorderTraversal(TreeNode root) {if (root == null) {return;}inorderTraversal(root.left); // 访问左子树System.out.print(root.val + " "); // 访问根节点inorderTraversal(root.right); // 访问右子树}// 后序遍历(递归)public static void postorderTraversal(TreeNode root) {if (root == null) {return;}postorderTraversal(root.left); // 访问左子树postorderTraversal(root.right); // 访问右子树System.out.print(root.val + " "); // 访问根节点}// 前序遍历(栈)public static void preorderTraversal1(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();System.out.print(node.val + " "); // 打印当前节点的值if (node.right != null) {stack.push(node.right); // 先将右子节点入栈}if (node.left != null) {stack.push(node.left); // 再将左子节点入栈}}}// 中序遍历(栈)public static void inorderTraversal1(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack = new Stack<>();TreeNode node = root;while (node != null || !stack.isEmpty()) {while (node != null) {stack.push(node);node = node.left; // 先将左子节点入栈}node = stack.pop();System.out.print(node.val + " "); // 打印当前节点的值node = node.right; // 再处理右子节点}}// 后序遍历(栈)public static void postorderTraversal1(TreeNode root) {if (root == null) {return;}Stack<TreeNode> stack1 = new Stack<>();Stack<TreeNode> stack2 = new Stack<>();stack1.push(root);while (!stack1.isEmpty()) {TreeNode node = stack1.pop();if (node.left != null) {stack1.push(node.left); // 先将左子节点入栈}if (node.right != null) {stack1.push(node.right); // 再将右子节点入栈}stack2.push(node); // 将当前节点入栈(用于后序遍历)}while (!stack2.isEmpty()) {System.out.print(stack2.pop().val + " "); // 打印栈中的节点值(即后序遍历结果)}}
}

TreeNode 

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }// 构建二叉树public static TreeNode buildTree(int[] nums) {if (nums == null || nums.length == 0) {return null;}return buildTree(nums, 0, nums.length - 1);}private static TreeNode buildTree(int[] nums, int left, int right) {if (left > right) {return null;}int mid = (left + right) / 2;TreeNode root = new TreeNode(nums[mid]);root.left = buildTree(nums, left, mid - 1);root.right = buildTree(nums, mid + 1, right);return root;}
}

 

运行结果

前序遍历(递归):4 2 1 3 6 5 7 
中序遍历(递归):1 2 3 4 5 6 7 
后序遍历(递归):1 3 2 5 7 6 4 
前序遍历(栈):4 2 1 3 6 5 7 
中序遍历(栈):1 2 3 4 5 6 7 
后序遍历(栈):1 3 2 5 7 6 4  

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

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

相关文章

Java三大特征之继承【超详细】

文章目录 一、继承概念二、继承的语法三、父类成员访问3.1子类中访问父类的成员变量3.2子类和父类成员变量同名3.3子类中访问父类的成员方法 四、super关键字五、子类构造方法六、super和this七、再谈初始化八、protected 关键字九、继承方式十、final 关键字十一、继承与组合 …

npm install报错 -> npm ERR! Unexpected token ‘.‘ 报错解决办法

问题原因&#xff1a; 用nvm1.1.7的版本安装了16.x以上的node, 然后再下载依赖的时候就报错了&#xff1b;总结一下就是nvm版本太低了&#xff0c;他的里面没有集成高版本node导致的。 解决办法&#xff1a; 把nvm切换到新版本就行了。 1. 卸载掉当前所有的node nvm unins…

06 HTTP(下)

06 HTTP&#xff08;下&#xff09; 介绍服务器如何响应请求报文&#xff0c;并将该报文发送给浏览器端。介绍一些基础API&#xff0c;然后结合流程图和代码对服务器响应请求报文进行详解。 基础API部分&#xff0c;介绍stat、mmap、iovec、writev。 流程图部分&#xff0c;描…

一个完整的http请求响应过程

一、 HTTP请求和响应步骤 以上完整表示了HTTP请求和响应的7个步骤&#xff0c;下面从TCP/IP协议模型的角度来理解HTTP请求和响应如何传递的。 二、TCP/IP协议 TCP/IP协议模型&#xff08;Transmission Control Protocol/Internet Protocol&#xff09;&#xff0c;包含了一系…

【ASP.NET MVC】使用动软(三)(11)

一、问题 上文中提到&#xff0c;动软提供了数据库的基本操作功能&#xff0c;但是往往需要添加新的功能来解决实际问题&#xff0c;比如GetModel&#xff0c;通过id去查对象&#xff1a; 这个功能就需要进行改进&#xff1a;往往程序中获取的是实体的其他属性&#xff0c;比如…

【Maven】让maven更高效,优化maven构建项目速度

打开idea的setting&#xff0c;找到maven&#xff0c;设置它多线程数&#xff0c;重启后即可&#xff01; 我这里是8&#xff0c;你们可以随便设置。 如下图&#xff1a;

c语言每日一练(1)

前言&#xff1a; 每日一练系列&#xff0c;每一期都包含5道选择题&#xff0c;2道编程题&#xff0c;博主会尽可能详细地进行讲解&#xff0c;令初学者也能听的清晰。每日一练系列会持续更新&#xff0c;暑假时三天之内必有一更&#xff0c;到了开学之后&#xff0c;将看学业情…

需求飙升120%!芭比产品火爆出圈,意大利人争相购买!

据外媒报道&#xff0c;真人版《芭比》成为今年夏天最火的电影&#xff0c;仅在美国和加拿大&#xff0c;该影片的票房收入就超过3.5亿美元。在意大利《芭比》也备受追捧&#xff0c;目前的票房收入突破1670万欧元&#xff0c;成为2023年观看人数第三多的电影。 除了电影界之外…

uniapp使用视频地址获取视频封面

很多时候我们都需要使用视频的第一帧当作视频的封面&#xff0c;今天我们从uni-app的安卓app这个环境来实现下这个需求。文中需要你对uniapp的renderjs有一定了解&#xff0c;可以先看我的这篇文章初识renderjs uniapp 安卓APP端&#xff08;ios未测试&#xff09; 方法&…

React入门学习笔记2

jsx语法规则 定义虚拟DOM时&#xff0c;不要写引号。标签中混入JS表达式时要用{ }。样式的类名指定不要用class&#xff0c;要用className。内联样式&#xff0c;要用style{{key&#xff1a;value}}的形式去写。只有一个根标签标签必须闭合标签首字母 )若小写字母开头&#xf…

2023-08-05——JVM Method Area(方法区)

方法区 Method Area&#xff08;方法区&#xff09; 方法区是指被所有线程共享的&#xff0c;字段和方法字节码&#xff0c;以及一些特殊方法&#xff0c;如构造函数&#xff0c;接口代码在此定义&#xff0c;简单的说就是所有的定义方法信息都保存在此区域&#xff0c;此区域…

selenium 和 chromedriver 使用的一些总结

1 selenium 下载地址 selenium PyPIhttps://pypi.org/project/selenium/ 2 chromedriver 下载地址 &#xff0c;可以下载最新版的 chromedriver ChromeDriver - WebDriver for Chrome - Downloadshttps://chromedriver.chromium.org/downloadsChrome for Testing availabi…

【沁恒蓝牙mesh】CH58x flash分区与数据存储管理

本文主要介绍了 沁恒蓝牙芯片 CH58x 的flash 分区与数据存储管理 &#x1f4cb; 个人简介 &#x1f496; 作者简介&#xff1a;大家好&#xff0c;我是喜欢记录零碎知识点的小菜鸟。&#x1f60e;&#x1f4dd; 个人主页&#xff1a;欢迎访问我的 Ethernet_Comm 博客主页&…

hcip的mgre和ospf实验

题目 拓扑图 一、配置环回和IP地址 R1 < Huawei>sy Enter system view, return user view with CtrlZ. [Huawei]sysname r1 [r1]int g0/0/1 [r1-GigabitEthernet0/0/1]ip add 64.1.1.1 24 Aug 4 2023 18:56:07-08:00 r1 %%01IFNET/4/LINK_STATE(l)[0]:The line protocol…

LinkedList和ArrayList有什么区别?

ArrayList和LinkedList的大致区别&#xff1a; ArrayList是实现了基于动态数组的数据结构&#xff0c;LinkedList基于链表的数据结构。 对于随机访问get和set&#xff0c;ArrayList觉得优于LinkedList&#xff0c;因为LinkedList要移动指针。 对于新增和删除操作add和remov…

vue页面布局

布局 用element-plus自带的布局&#xff1b; 左边菜单 用他的Menu 菜单、自带收缩和展开&#xff1b;数据可以接口获取或者写死&#xff1b; 使用的如下操作、把主题和默认打开的index存到缓存中 头部&#xff1b; 简单的先分成左右&#xff1b;再简单的分成左右 1、左…

高通滤波器,低通滤波器

1.高通滤波器是根据像素与邻近像素的亮度差值来提升该像素的亮度。 import cv2 import numpy as np from scipy import ndimagekernel_3_3 np.array([[-1,-1,-1],[-1,8,-1],[-1,-1,-1]]) print(kernel_3_3) kernel_5_5 np.array([[-1,-1,-1,-1,-1],[-1,1,2,1,-1],[-1,2,4,2,-…

FDM3D打印系列——超可动可变形机体打印

大家好&#xff0c;我是阿赵。继续来分享一下3D打印的成果。   这次打印的对象不得了&#xff0c;是超时空要塞系列的可变形VF战机。打印完这个模型&#xff0c;绝对是学习到了很多的东西&#xff0c;下面给大家分享一下。 一、成果展示&#xff1a; 不要怀疑&#xff0c;不…

Elasticsearch 商业启示

上月的“红帽事件”&#xff0c;说明开源软件的“客服模式”行不通&#xff0c;那么&#xff0c;开源软件如何赚钱呢&#xff1f;既不能卖软件&#xff0c;又不能卖支持服务&#xff0c;该怎么办呢&#xff1f;我现在的看法是&#xff0c;只剩下一种模式是可行的&#xff0c;开…

Java 监听Mysql binlog

使用 mysql-binlog-connector-java 1. mysql-binlog-connector-java 官网 2. Java代码中&#xff0c;如何监控Mysql的binlog&#xff1f; 前置条件 1. mysql服务器表结构 CREATE TABLE student (id int NOT NULL AUTO_INCREMENT,name varchar(255) CHARACTER SET utf8mb4 C…