二叉树的非递归遍历---JAVA实现

二叉树的递归遍历方式是很简单的，当需要用非递归的方式遍历时，就需要借助栈这种数据结构，以前序遍历为例，其定义为先访问根节点，再以前序方式访问左子树，再以前序遍历方式访问右子树，这是个递归的定义。对于前序遍历，最先访问的是根，然后是根左边的孩子，在继续访问孩子的左边孩子，走到底部，再从底部开始倒退回来，逐渐访问右边孩子，很自然的想到使用栈这种数据结构......（可以画一个二叉树看看其前序遍历的过程就明白了），下面以代码说明：

二叉树结构如图：

/*二叉树结构：
       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

可以看出，非递归的方式均使用了栈这种数据结构，这也是栈在程序设计中最常见的用途之一。