非递归方式实现二叉树的先序、中序、后序遍历：
任何递归函数都可以改成非递归
自己设计压栈来实现
先序遍历：
弹出就打印
如果有右孩子，压入右孩子
如果有左孩子，压入左孩子
后序遍历：需要用到两个栈
额外申请一个栈s2，弹出后放入s2中
如果有左孩子，压入左孩子
如果有右孩子，压入右孩子
中序遍历：
整条左边界依次入栈
条件1不满足，弹出就打印，并来到弹出结点的右树继续执行条件1
后续遍历：只需要用到一个栈，另外设置两个变量h和c，h记录之前打印的结点的位置，c记录栈顶的位置。
package com.harrison.class07; import java.util.Stack; public class Code02_UnRecursiveTraversalBT { public static class Node{ public int value; public Node left; public Node right; public Node(int v) { value=v; } } public static void pre(Node head) { System.out.println("pre-order："); if(head!=null) { Stack<Node> s=new Stack<>(); s.push(head); while(!s.isEmpty()) { head=s.pop(); System.out.print(head.value+" "); if(head.right!=null) { s.push(head.right); } if(head.left!=null) { s.push(head.left); } } } System.out.println(); } public static void pos1(Node head) { System.out.println("pos-order："); if(head!=null) { Stack<Node> s1=new Stack<>(); Stack<Node> s2=new Stack<>(); s1.push(head); while(!s1.isEmpty()) { head=s1.pop(); s2.push(head); if(head.left!=null) { s1.push(head.left); } if(head.right!=null) { s1.push(head.right); } } while(!s2.isEmpty()) { System.out.print(s2.pop().value+" "); } } System.out.println(); } public static void in(Node head) { System.out.println("in-order："); if(head!=null) { Stack<Node> s=new Stack<>(); while(!s.isEmpty() || head!=null) { if(head!=null) { s.push(head); head=head.left; }else { head=s.pop(); System.out.print(head.value+" "); head=head.right; } } } System.out.println(); } public static void pos2(Node h) { System.out.println("pos-order："); if(h!=null) { Stack<Node> stack=new Stack<>(); stack.push(h); Node c=null; 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().value+" "); h=c; } } } System.out.println(); } public static void main(String[] args) { Node head = new Node(1); head.left = new Node(2); head.right = new Node(3); head.left.left = new Node(4); head.left.right = new Node(5); head.right.left = new Node(6); head.right.right = new Node(7); pre(head); System.out.println("========"); in(head); System.out.println("========"); pos1(head); System.out.println("========"); pos2(head); System.out.println("========"); } }
