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

java分别使用递归和非递归实现二叉树中序遍历

时间:2021-11-02 13:09:36  来源:  作者:留住此刻

对于二叉树,它的特点就是任何一个节点,左节点小于父节点、右节点大于父节点遍历二叉树有多种方式,如中序遍历、层序遍历、后序遍历,中序遍历的思路就是左-->父--->右的顺序,下面给出递归和非递归的两种方法,递归很好理解,非递归就是一直找到最左节点,然后回溯节点,如果存在右节点,则重复上述过程

如将下面的二叉树使用中序遍历输出有序数组

java分别使用递归和非递归实现二叉树中序遍历

 

 

代码如下

import JAVA.util.ArrayList;
import java.util.List;
import java.util.Stack;
/**
 * 中序遍历的非递归和递归的实现
 * 
 * @author ssj
 *
 */
public class MiddleList {
	public static void main(String[] args) {
		// 创建一颗二叉树
		Node root = new Node("10");
		Node n6 = new Node("6");
		Node n14 = new Node("14");
		n6.setParent(root);
		n14.setParent(root);
		root.setLeft(n6);
		root.setRight(n14);
		Node n4 = new Node("4");
		Node n8 = new Node("8");
		n6.setLeft(n4);
		n6.setRight(n8);
		Node n12 = new Node("12");
		Node n16 = new Node("16");
		n14.setLeft(n12);
		n14.setRight(n16);
		System.out.println("---------递归遍历结果--------------------");
		List list = new ArrayList();
		middleListDG(root, list);
		System.out.println(list);
		System.out.println("---------非递归遍历结果--------------------");
		List list2 = middleList(root);
		System.out.println(list2);
	}
	/**
	 * 递归中序遍历
	 * 
	 * @param root
	 * @return
	 */
	public static void middleListDG(Node root, List list) {
		if (root == null) {
			return;
		}
		middleListDG(root.left, list);
		list.add(root.name);
		middleListDG(root.right, list);
	}
	/**
	 * 非递归中序遍历
	 * @param root
	 * @return
	 */
	public static List middleList(Node root) {
		Stack<Node> sk = new Stack<Node>();
		List list = new ArrayList();
		Node n = root;
		while (n != null) {
			// 一直找到最左边的节点
			while (n != null) {
				sk.push(n);
				n = n.left;
			}
			// 输出最左边的节点
			while (!sk.empty()) {
				Node n2 = sk.pop();
				list.add(n2.getName());
				// 如果该节点存在右节点,先输出所有的右节点,即重复以上过程
				if (n2.right != null) {
					n = n2.right;
					break;
				}
			}
		}
		return list;
	}
}
/**
 * 树节点
 * @author ssj
 *
 */
class Node {
	public String name;
	public Node left;
	public Node right;
	public Node parent = null;
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public Node getParent() {
		return parent;
	}
	public void setParent(Node parent) {
		this.parent = parent;
	}
	public Node(String name) {
		super();
		this.name = name;
	}
	public Node getLeft() {
		return left;
	}
	public void setLeft(Node left) {
		this.left = left;
	}
	public Node getRight() {
		return right;
	}
	public void setRight(Node right) {
		this.right = right;
	}
}

输出结果

java分别使用递归和非递归实现二叉树中序遍历

 



Tags:遍历   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
这个也就是提供一个思路,需求是这样的,我XX的闺蜜有个rar的压缩包,不知道他是从哪里挣来的,说这个对他比较重要,但是有密码打不开,唉,可怜了我的电脑了因为这个是暴力破解,是把所有...【详细内容】
2021-11-04  Tags: 遍历  点击:(38)  评论:(0)  加入收藏
对于二叉树,它的特点就是任何一个节点,左节点小于父节点、右节点大于父节点遍历二叉树有多种方式,如中序遍历、层序遍历、后序遍历,中序遍历的思路就是左-->父--->右的顺序,下面...【详细内容】
2021-11-02  Tags: 遍历  点击:(38)  评论:(0)  加入收藏
stack容器#include <iostream>using namespace std;#include <stack>//容器头文件void test(){stack<int>p;p.push(100);p.push(1000);p.push(100);while(!p.empty()){cout<...【详细内容】
2021-08-17  Tags: 遍历  点击:(81)  评论:(0)  加入收藏
stl 常用遍历算法(for_each transform)示例代码(结论在结尾!!!!)#include<iostream>using namespace std;#include"vector"#include"map"#include"string"#include"list"#in...【详细内容】
2021-08-13  Tags: 遍历  点击:(89)  评论:(0)  加入收藏
前言本篇内容将按照下图展开: 遍历ObjectObject最常见的遍历方法方法就是使用 for...in... ,但其有一定的局限性,比如只能遍历可枚举属性。虽然Object无法直接使用 for循环 和...【详细内容】
2021-04-27  Tags: 遍历  点击:(261)  评论:(0)  加入收藏
一、1062年,42岁的王安石已然人到中年。每天下班后,同僚们嘻嘻哈哈的走向勾栏瓦肆中,探寻人生真谛。他却默默收拾好破旧的公文包,拖着一身疲惫回到老小区的家中,守着人老珠黄的糟...【详细内容】
2021-01-20  Tags: 遍历  点击:(175)  评论:(0)  加入收藏
背景今天双十一,昨晚有好多电商行业的 IT 工程师们挑灯夜战,为这个全民狂欢的购物节护航。还记得三年前我们公司一个产品上线前一周时,办公室内拉起“跟 Bug 死扛到底”的横幅,B...【详细内容】
2020-11-11  Tags: 遍历  点击:(65)  评论:(0)  加入收藏
为了方便例子讲解,现有数组和字面量对象如下var demoArr = [&#39;Javascript&#39;, &#39;Gulp&#39;, &#39;CSS3&#39;, &#39;Grunt&#39;, &#39;jQuery&#39;, &#39;angular&#39...【详细内容】
2020-08-28  Tags: 遍历  点击:(74)  评论:(0)  加入收藏
vector是相同类型对象的集合,集合中的每个对象有个对应的索引。vector常被称为容器(container)。C++中遍历vector的所有元素是相当常用的操作,这里介绍四种方式。1、通过下标...【详细内容】
2020-06-20  Tags: 遍历  点击:(342)  评论:(0)  加入收藏
通过Map.values()遍历所有的value,不能遍历key public class TestDemo{ public static void main(String[] args) { HashMap<String,String> hashMap = new Has...【详细内容】
2020-03-08  Tags: 遍历  点击:(47)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(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:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯&middot;奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条