java栈实现二叉树的非递归遍历的示例代码

  • 更新时间:2022-07-27 14:32:57
  • 编辑:殳永言
给寻找Java相关教程的朋友们精选了java相关的编程文章,网友胡安雁根据主题投稿了本篇教程内容,涉及到java实现二叉树的非递归遍历、java栈、java实现二叉树的非递归遍历相关内容,已被343网友关注,如果对知识点想更进一步了解可以在下方电子资料中获取。
21天学通Java
21天学通Java
  • 大小:22.9 MB
  • 发布人:巢滨海
  • 下载:Java

java实现二叉树的非递归遍历

一般来说遍历二叉树用到递归,但是用Stack进行遍历也是一个不错的方法。

二叉树设置

class Node{
	public int val;
	public Node left;
	public Node right;
	
	public Node(int v) {
		val=v;
		left=null;
		right=null;
	}
}

public class Main {
	public static void main(String[] args) {
		Node head =new Node(0);
		Node node1=new Node(1);
		Node node2=new Node(2);
		Node node3=new Node(3);
		Node node4=new Node(4);
		Node node5=new Node(5);
		Node node6=new Node(6);
		head.left=node1;
		head.right=node2;
		node1.left=node3;
		node1.right=node4;
		node2.left=node5;
		node2.right=node6;
		pos2(head);
		pos1(head);
		in(head);
	}

前序遍历

思想和流程

  • 弹出就打印
  • 如果有右子树,就压入
  • 如果有左子树,就压入
public static void pos1(Node h) {
	System.out.print("先序遍历 ");
	if(h!=null) {
		Stack<Node>stack =new Stack<Node>();
		stack.push(h);
		while(!stack.isEmpty()) {
			h=stack.pop();
			System.out.print(h.val+" ");
			if(h.right!=null) {
				stack.push(h.right);
			}
			if(h.left!=null) {
				stack.push(h.left);
			}
		}
	}
	System.out.println();
}

后序遍历

前序遍历的顺序是父节点,左,右,而后序遍历的顺序是左,右,父节点,也就是说前序遍历左右替换之后就是后序遍历的倒过来。所以只要把前序遍历时候左右子节点压栈的顺序调换一下,再用另一个栈储存,然后再弹出就是后序遍历了。在此代码就不多写了。

中序遍历

思路和流程

  • 弹出就打印
  • 整条左边界依次入栈
  • 上一条件无法继续,弹出打印,开始右子树
public static void in(Node h) {
	System.out.print("中序遍历 ");
	if(h!=null) {
		Stack<Node>stack =new Stack<Node>();
		while(!stack.isEmpty()||h!=null) {
			if(h!=null) {
				stack.push(h);
				h=h.left;
			}else {
				h=stack.pop();
				System.out.print(h.val+" ");
				h=h.right;
			}
		}
	}
	System.out.println();
}

后序遍历变体

用一个Stack实现
思路是左节点没处理就处理左节点,左节点处理过了就处理右节点,右节点处理完了就返回。

public static void pos2(Node h) {
	if(h!=null) {
		Stack<Node>stack =new Stack<Node>();
		stack.push(h);
		Node c=null;//用c记录上一次被打印的节点
		while(!stack.isEmpty()) {
			c=stack.peek();
			if(c.left!=null&&h!=c.left&&h!=c.right) {
				stack.push(c.left);
			}else if(c.right!=null&&h!=c.right) {
				stack.push(c.right);
			}else {
				System.out.print(stack.pop().val+" ");
				h=c;//记录本次被打印的节点
			}
		}
	}
}

打印结果

到此这篇关于java栈实现二叉树的非递归遍历的文章就介绍到这了,更多相关java实现二叉树的非递归遍历内容请搜索java学习网以前的文章或继续浏览下面的相关文章希望大家以后多多支持java学习网!

相关下载

  • Java开发手册 v1.5.0

    大小:1.3 MB
  • 深入浅出Java多线程(阿里Java大牛)

    大小:3.02 MB
  • JAVA程序设计基础

    大小:4.33 MB

相关教程

  • Java中LinkedList原理代码解析

    Java中LinkedList原理代码解析

    给大家整理了关于Java的教程,这篇文章主要介绍了Java中LinkedList原理代码解析,分享了相关代码示例,小编觉得还是挺不错的,具有一定借鉴价值,需要的朋友可以参考下

    发布时间:2022-06-25

  • Java编程实现邻接矩阵表示稠密图代码示例

    Java编程实现邻接矩阵表示稠密图代码示例

    给大家整理了关于Java的教程,这篇文章主要介绍了Java编程实现邻接矩阵表示稠密图代码示例,具有一定参考价值,需要的朋友可以了解下。

    发布时间:2022-06-12

  • Java在利用反射条件下替换英文字母中的值

    给网友朋友们带来一篇关于java的教程,今天小编就为大家分享一篇关于Java在利用反射条件下替换英文字母中的值,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧

    发布时间:2022-06-11

  • Java StringBuilder的用法示例

    给大家整理了关于Java的教程,这篇文章主要给大家介绍了关于Java StringBuilder用法的相关资料,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

    发布时间:2022-06-14Java StringBuilder用法

  • java_IO向文件中写入和读取内容代码实例

    给网友们整理关于java的教程,这篇文章主要介绍了java_IO向文件中写入和读取内容,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

    发布时间:2022-07-05

  • JavaSE图像验证码简单识别程序详解

    给大家整理一篇关于Java的教程,这篇文章主要为大家详细介绍了JavaSE图像验证码简单识别程序,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2022-07-06

  • Java的jstack命令使用示例详解

    Java的jstack命令使用示例详解

    给网友们整理关于Java的教程,jstack 命令非常的简单,我们可以通过 jstack -h 或者 jstack -help 命令查看它的用法详情,今天通过本文重点给大家介绍Java的jstack命令使用,感兴趣的朋友一起看看吧

    发布时间:2022-06-26Java的jstack命令使用

  • 浅析java中的取整(/)和求余(%)

    给大家整理一篇关于java的教程,这篇文章主要介绍了浅析java中的取整(/)和求余(%),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧

    发布时间:2022-06-15

  • java编程题之从上往下打印出二叉树

    给大家整理了关于java的教程,这篇文章主要为大家详细介绍了java编程题之从上往下打印出二叉树,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2022-07-19

  • java GUI实现学生图书管理简单实例

    java GUI实现学生图书管理简单实例

    给大家整理一篇关于java的教程,这篇文章主要为大家详细介绍了java GUI实现学生图书管理简单示例,具有一定的参考价值,感兴趣的小伙伴们可以参考一下

    发布时间:2022-06-20

用户留言