前面写了一些关于树的操作，但是没有实现树的遍历的非递归写法。
通常树有四种遍历方法：1.层次遍历（需要用到树的高度，此文没有考虑）
2.前序遍历(根左右)；3.中序遍历(左根右)；4.后序遍历(左右根)
树的结构如下：
层次遍历：123456789
前序遍历：124895367
中序遍历：849251637
后序遍历：894526731
java代码实现三种遍历的递归和和非递归实现
package com.lip.datastructure.tree;import java.util.Stack;/** * @author lip */public class Tree{public static void main(String[] args){Node<Integer>root=getNode();System.out.println("前序遍历（非递归）");preOrder(root);System.out.println("前序遍历（递归）");preOrderRecursive(root);System.out.println();System.out.println("中序遍历（非递归）");infixOrder(root);System.out.println("中序遍历（递归）");infixOrderRecursive(root);System.out.println();System.out.println("后序遍历（非递归）");postOrder(root);System.out.println("后序遍历（递归）");postOrderRecursive(root);}public static Node getNode(){Node<Integer>node1=new Node(1);Node<Integer>node2=new Node(2);Node<Integer>node3=new Node(3);node1.left=node2;node1.right=node3;Node<Integer>node4=new Node(4);Node<Integer>node5=new Node(5);node2.left=node4;node2.right=node5;Node<Integer>node6=new Node(6);Node<Integer>node7=new Node(7);node3.left=node6;node3.right=node7;Node<Integer>node8=new Node(8);Node<Integer>node9=new Node(9);node4.left=node8;node4.right=node9;return node1;}//前序遍历，非递归@SuppressWarnings("rawtypes")public static void preOrder(Node root){Stack<Node>stack=new Stack<Node>();stack.push(root);while(stack.size()>0){Node tempNode=stack.pop();if(tempNode!=null){System.out.print(tempNode.data);stack.push(tempNode.right);stack.push(tempNode.left);}}System.out.println();}//前序遍历(根左右)，递归public static void preOrderRecursive(Node root){if(root!=null){System.out.print(root.data);preOrderRecursive(root.left);preOrderRecursive(root.right);}}//中序遍历（左根右），非递归public static void infixOrder(Node root){Stack<Node>stack=new Stack<Node>();stack.push(root);while(stack.size()>0){Node temp=stack.pop();if(temp!=null){if((temp.left==null)&&(temp.right==null))System.out.print(temp.data);else{stack.push(temp.right);stack.push(new Node(temp.data));stack.push(temp.left);}}}System.out.println();}//中序遍历（左根右），，递归public static void infixOrderRecursive(Node root){if(root!=null){infixOrderRecursive(root.left);System.out.print(root.data);infixOrderRecursive(root.right);}}//后序遍历（左右根），非递归public static void postOrder(Node root){Stack<Node>stack=new Stack<Node>();stack.push(root);Node temp;while(stack.size()>0){temp=stack.pop();if(temp!=null){if(temp.left==null&&temp.right==null)System.out.print(temp.data);else {stack.push(new Node(temp.data));stack.push(temp.right);stack.push(temp.left);}}}System.out.println();}//后序遍历（左右根），递归public static void postOrderRecursive(Node root){if(root!=null){postOrderRecursive(root.left);postOrderRecursive(root.right);System.out.print(root.data);}}} class Node <T> {public Node left;public Node right;public T data;public Node(T data){this.data=data;} }
其实递归和非递归的区别也就是非递归使用stack来回溯（也可以看做是一种特殊的递归）
成功是什么?就是走过了所有通向失败的路，
