二叉树的递归遍历方式是很简单的，当需要用非递归的方式遍历时，就需要借助栈这种数据结构，以前序遍历为例，其定义为先访问根节点，再以前序方式访问左子树，再以前序遍历方式访问右子树，这是个递归的定义。对于前序遍历，最先访问的是根，然后是根左边的孩子，在继续访问孩子的左边孩子，走到底部，再从底部开始倒退回来，逐渐访问右边孩子，很自然的想到使用栈这种数据结构......（可以画一个二叉树看看其前序遍历的过程就明白了），下面以代码说明：
二叉树结构如图：
/*二叉树结构： A / \ B C / \ / E F I / \ \ G H J */前序、中序、后序的递归、非递归访问：
代码还包括递归创建二叉树的部分，其中，后序遍历有两种非递归实现方法（对应使用了一个栈或两个栈）
public class BinTreeTraverse { /** * @ 二叉树的非递归遍历 */ public static void main(String[] args) { String str="ABE##FG##H##CI#J###"; TreeNode<Character> root=createBinTree(new StringBuilder(str)); System.out.print("********************preOrder******************\n"); preOrder(root); System.out.println(); preOrderLoop(root); System.out.print("\n********************inOrder******************\n"); inOrder(root); System.out.println(); inOrderLoop(root); System.out.print("\n*******************postOrder*******************\n"); postOrder(root); System.out.print("\n双栈方式："); postOrderLoop(root); System.out.print("\n单栈方式："); postOrderLoop2(root); } //***************************前序******************************** public static void preOrder(TreeNode<Character> root){ if(root!=null){ System.out.print(root.data+" "); preOrder(root.leftChildren); preOrder(root.rightChildren); } } //PreOrder的非递归实现——需要借助栈空间实现 public static void preOrderLoop(TreeNode<Character> root){ //根据递归的过程来想，它每遇到一个节点，就以之为根节点，不断向左下放遍历，入栈，直到空 //然后栈弹出，又以弹出点右孩子为根（非空的），继续刚才左下滑的过程 MyStack<TreeNode<Character>> stack=new MyStack<TreeNode<Character>>(); TreeNode<Character> temp=root; while(temp!=null || !stack.isEmpty()){ while(temp!=null){ visit(temp); stack.push(temp); temp=temp.leftChildren; } if(!stack.isEmpty()){ temp=stack.pop(); temp=temp.rightChildren; } } } //*****************************中序********************************** public static void inOrder(TreeNode<Character> root){ if(root!=null){ inOrder(root.leftChildren); visit(root); inOrder(root.rightChildren); } } public static void inOrderLoop(TreeNode<Character> root){ TreeNode<Character> temp=root; MyStack<TreeNode<Character>> stack =new MyStack<TreeNode<Character>>(); while(temp!=null || !stack.isEmpty()){ while(temp!=null){ stack.push(temp); temp=temp.leftChildren; } if(!stack.isEmpty()){ temp=stack.pop(); visit(temp); temp=temp.rightChildren; } } } //********************************后序********************************** public static void postOrder(TreeNode<Character> root){ if(root!=null){ postOrder(root.leftChildren); postOrder(root.rightChildren); visit(root); } } public static void postOrderLoop(TreeNode<Character> root){ /*(可结合后序遍历结果进行分析) * 与前序遍历相反，后序遍历相当于每次从根节点开始，一直向右下方向搜寻直到空，逐个入栈，遇到null后， * 依次出栈，让出栈点的左孩子执行相同的操作（需要一个辅助栈保存）；最后将栈的元素一起弹出 * 因此：后序遍历需要用两个栈 * */ TreeNode<Character> temp=root; MyStack<TreeNode<Character>> stack=new MyStack<TreeNode<Character>>(); MyStack<TreeNode<Character>> stackHelp=new MyStack<TreeNode<Character>>(); while(temp!=null || !stack.isEmpty()){ while(temp!=null){ stack.push(temp); stackHelp.push(temp);//此句是唯一与前序遍历不同的地方（进入辅助栈） temp=temp.rightChildren; } if(!stack.isEmpty()){ temp=stack.pop(); temp=temp.leftChildren; } } while(!stackHelp.isEmpty()){ temp=stackHelp.pop(); visit(temp); } } /*使用单个栈也可实现非递归的后序遍历 * 需要有一个节点记录上次访问过的节点 * */ public static void postOrderLoop2(TreeNode<Character> root){ TreeNode<Character> temp = root; TreeNode<Character> preNode =null; MyStack<TreeNode<Character>> stack =new MyStack<TreeNode<Character>>(); while(temp!=null || !stack.isEmpty()){ //同前序一样，左边所有节点入栈 while(temp!=null){ stack.push(temp); temp=temp.leftChildren; } if(!stack.isEmpty()){ temp=stack.peek(); if(temp.rightChildren!=null && temp.rightChildren!=preNode){ temp=temp.rightChildren; }else{//说明右子树为空或已经访问过 temp=stack.pop(); visit(temp); preNode=temp; temp=null; //防止刚出栈的节点的左孩子继续入栈（即跳过上面的while循环） } } } } //******************************************************************** private static void visit(TreeNode<Character> root){ System.out.print(root.data+" "); } //递归的创建二叉树 public static TreeNode<Character> createBinTree(StringBuilder sb){ //只能传StringBuilder，不能传String，因为第二次递归必须使用第一次递归使用完之后的数据 //string虽然也传递的是字串的引用，但递归过程中并不能改变其值substring()返回的是新字串 char data=sb.charAt(0); sb.deleteCharAt(0); TreeNode<Character> rootNode=null; if(data!='#'){ rootNode=new TreeNode<Character>(data); rootNode.leftChildren=createBinTree(sb); rootNode.rightChildren=createBinTree(sb); } return rootNode; } } class TreeNode<E>{ E data; TreeNode<E> leftChildren; TreeNode<E> rightChildren; TreeNode(E data){ this.data=data; leftChildren=null; rightChildren=null; } }运行结果： ********************preOrder****************** A B E F G H C I J A B E F G H C I J ********************inOrder****************** E B G F H A I J C E B G F H A I J C *******************postOrder******************* E G H F B J I C A 双栈方式：E G H F B J I C A 单栈方式：E G H F B J I C A可以看出，非递归的方式均使用了栈这种数据结构，这也是栈在程序设计中最常见的用途之一。
