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) {

Stackstack =newmUXnWJe Stack();

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) {

Stackstack =new Stack();

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实现

思路是左节点没处理就处理左节点，左节点mUXnWJe处理过了就处理右节点，右节点处理完了就返回。

public static void pos2(Node h) {

if(h!=null) {

Stackstack =new Stack();

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&http://amp;&h!=c.right) {

stack.push(c.right);

}else {

System.out.print(stack.pop().val+" ");

h=c;//记录本次被打印的节点

}

}

}

}

打印结果

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。