您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

二叉树的遍历-递归和非递归

时间:2019-09-09 13:12:00  来源:  作者:
二叉树的遍历-递归和非递归

盗图

前言

最近准备面试 ,复习了一下数据结构 中的二叉树,整理了二叉树的前序、中序、后序、深度和广度遍历以及递归和非递归实现方法,如有好的方案大家可以一起讨论。

前序遍历

先遍历根节点,然后再遍历左子树,最后再遍历右子树

JAVA 示例:

/**
 * 前序遍历
 */
public void previousTraverse() {
 if (Objects.nonNull(root)) {
 doPreviousTraverse(root);
 }
}
private void doPreviousTraverse(Node root) {
 //先遍历根节点
 System.out.println(root.getData());
 if (Objects.nonNull(root.getLeft())) {
 doPreviousTraverse(root.getLeft());
 }
 if (Objects.nonNull(root.getRight())) {
 doPreviousTraverse(root.getRight());
 }
}

中序遍历

思路:先遍历左子树,然后遍历根节点,最后遍历右子树

java 示例

/**
 * 中序遍历
 */
public void middleTraverse() {
 if (Objects.nonNull(root)) {
 doMiddleTraverse(root);
 }
}
private void doMiddleTraverse(Node root) {
 //先遍历左节点
 if (Objects.nonNull(root.getLeft())) {
 doMiddleTraverse(root.getLeft());
 }
 //遍历根节点
 System.out.println(root.getData());
 //遍历右节点
 if (Objects.nonNull(root.getRight())) {
 doMiddleTraverse(root.getRight());
 }
}

后序遍历

思路:先遍历左子树,然后遍历右子树,再遍历根节点

java示例

/**
 * 后序遍历
 */
public void afterTraverse() {
 if (Objects.nonNull(root)) {
 doAfterTraverse(root);
 }
}
private void doAfterTraverse(Node root) {
 //先遍历左节点
 if (Objects.nonNull(root.getLeft())) {
 doAfterTraverse(root.getLeft());
 }
 // 遍历右节点
 if (Objects.nonNull(root.getRight())) {
 doAfterTraverse(root.getRight());
 }
 //遍历根节点
 System.out.println(root.getData());
}

广度遍历

思路:使用队列来辅助实现,首先把根节点放到队列里,然后弹出 根节点 打印根节 点的値,判断左子节点是否为空,不为空放入队列,判断右节点是否为空,不为空 放入队列,一次重复上述步骤,找到队列里没有数据结束,打印出来的序列则为该 树的广度遍历。

java 示例:

/**
 * 广度遍历
 */
public void broadCastTraverse() {
 if (Objects.nonNull(root)) {
 //定义一个存放节点的队列
 LinkedList<Node> nodes = new LinkedList<>();
 nodes.addLast(root);
 while (!nodes.isEmpty()) {
 Node node = nodes.removeFirst();
 System.out.println(node.getData());
 if (Objects.nonNull(node.getLeft())) {
 nodes.addLast(node.getLeft());
 }
 if (Objects.nonNull(node.getRight())) {
 nodes.addLast(node.getRight());
 }
 }
 }
}

深度遍历 即先序遍历 若不采用递归方式则序借助栈的后进先出

 先将根节点事先放到栈中然后执行下面的步骤:
 1.从栈顶弹出节点
 2.打印节点的値
 3.判断该节点的右子节点是否为空,若不为空则将右子节点放入栈中
 4.判断该节点的左子节点是否为空,若不为空则将左子节点放入栈中
 重复上述步骤,直到栈为空

java 示例

/**
 * 深度遍历 即先序遍历 若不采用递归方式则序借助栈的后进先出
 * 先将根节点事先放到栈中然后执行下面的步骤:
 * 1.从栈顶弹出节点
 * 2.打印节点的値
 * 3.判断该节点的右子节点是否为空,若不为空则将右子节点放入栈中
 * 4.判断该节点的左子节点是否为空,若不为空则将左子节点放入栈中
 * 重复上述步骤,直到栈为空
 */
public void deepTraverse() {
 if (Objects.nonNull(root)) {
 Stack<Node> nodes = new Stack<>();
 nodes.push(root);
 while (!nodes.isEmpty()) {
 Node node = nodes.pop();
 System.out.println(node.getData());
 if (Objects.nonNull(node.getRight())) {
 nodes.push(node.getRight());
 }
 if (Objects.nonNull(node.getLeft())) {
 nodes.push(node.getLeft());
 }
 }
 }
}

中序遍历 非递归遍历 借用栈来实现

思路:
1.首先将根节点 入栈
2.依次将左节点入栈直到左节点为空
3.弹出栈顶打印判断是否有右节点,若有则入栈 

java 示例

/**
 * Non-recursive traversal
 *
 * 中序遍历 非递归遍历 借用栈来实现
 * 思路:
 * 1.首先将根节点 入栈
 * 2.依次将左节点入栈直到左节点为空
 * 3.弹出栈顶打印判断是否有右节点,若有则入栈
 */
public void nonRecursiveTraverse() {
 if (Objects.nonNull(root)) {
 Node node = root;
 Stack<Node> nodes = new Stack<>();
 while (Objects.nonNull(node) || !nodes.isEmpty()) {
 if (Objects.nonNull(node)) {
 //将根节点入栈
 nodes.push(node);
 node = node.getLeft();
 } else {
 Node someLeft = nodes.pop();
 System.out.println(someLeft.getData());
 if (Objects.nonNull(someLeft.getRight())) {
 node = someLeft.getRight();
 }
 }
 }
 }
}

完整源码位置

https://github.com/241600489/homeworks/tree/master/src/main/java/zym/sort/tree/binary

后记

看完之后如果觉得有用麻烦点个赞加个关注哦

参考

https://blog.csdn.net/qq_38875300/article/details/89299647



Tags:递归   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
一、问题提出问题:把m个苹果放入n个盘子中,允许有的盘子为空,共有多少种方法?注:5,1,1和1 5 1属同一种方法m,n均小于10二、算法分析设f(m,n) 为m个苹果,n个盘子的放法数目,则先对...【详细内容】
2021-11-17  Tags: 递归  点击:(49)  评论:(0)  加入收藏
对于二叉树,它的特点就是任何一个节点,左节点小于父节点、右节点大于父节点遍历二叉树有多种方式,如中序遍历、层序遍历、后序遍历,中序遍历的思路就是左-->父--->右的顺序,下面...【详细内容】
2021-11-02  Tags: 递归  点击:(39)  评论:(0)  加入收藏
正文在传统的后台管理系统里面经常会需要展示多级菜单关系,今天我们来学一下如何使用一条SQL语句展示多级菜单。现在我们有一张corpinfo单位表,里面有一个belong字段指向上级...【详细内容】
2020-12-25  Tags: 递归  点击:(227)  评论:(0)  加入收藏
1、引言今天我们来学习递归,如果单说学习算法, 递归并不能说是算法,而是一种编程的手法,为什么现在要学习这个呢?因为后面在学习其他算法时,要牵涉一些递归的调用方法,是为以后理解...【详细内容】
2020-09-21  Tags: 递归  点击:(50)  评论:(0)  加入收藏
前言递归,是一个非常重要的概念,也是面试中非常喜欢考的。因为它不但能考察一个程序员的算法功底,还能很好的考察对 时间空间复杂度 的理解和分析。本文只讲一题,也是几乎所有算...【详细内容】
2020-09-21  Tags: 递归  点击:(61)  评论:(0)  加入收藏
一、概述在本篇文章中,给大家介绍一下如何将文件进行zip压缩以及如何对zip包解压。所有这些都是使用Java提供的核心库 java.util.zip 来实现的。二、压缩文件首先我们来学...【详细内容】
2020-08-10  Tags: 递归  点击:(53)  评论:(0)  加入收藏
开始之前,首先来看一个通常我们不会以递归的形式思考的问题。假设我们想计算整数n的阶乘。n的阶乘可写作n!,其结果是1~n之间的各数之积。比如,4!=4&times;3&times;2&times;1。一...【详细内容】
2020-08-05  Tags: 递归  点击:(123)  评论:(0)  加入收藏
书上用了一个阶乘功能来演示递归:7.1 递归(阶乘)function factorial(number){ if (number <= 1){ return 1; }else { return number * arguments.calle...【详细内容】
2020-06-23  Tags: 递归  点击:(71)  评论:(0)  加入收藏
你对递归很纠结吗?虽然代码量少,理解起来太费劲?如果你这么想那就对了。因为我们人类的思维方式和递归的实现逻辑是有冲突的!我们想问题根本不那么想。可是程序员面试不得不准...【详细内容】
2020-06-21  Tags: 递归  点击:(117)  评论:(0)  加入收藏
比如我需要将 jpg 结尾的图片文件修改为 png 结尾的如果能用rename命令,运行下面的find . -name &#39;*.jpg&#39; -exec rename .jpg .png {} +如果不能用rename命令,使用下...【详细内容】
2020-06-19  Tags: 递归  点击:(92)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条