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实现二叉树的非递归遍历内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com！