1、递归遍历

// 先序遍历（递归实现）-------------------------------------------------------------
 	  /*
	  1. Visit the node.
	  1. Call itself to traverse the node’s left subtree.
      3. Call itself to traverse the node’s right subtree.
	  4. base case: there is no node
	  */
   private void preOrder(Node localRoot){
      if(localRoot != null)
         {
         visit(localRoot);       // System.out.print(localRoot.iData + " ");
         preOrder(localRoot.leftChild);
         preOrder(localRoot.rightChild);
         }
      }
// 中序遍历（递归实现）-------------------------------------------------------------
   private void inOrder(Node localRoot){
      if(localRoot != null)
         {
         inOrder(localRoot.leftChild);
         visit(localRoot);       //System.out.print(localRoot.iData + " ");
         inOrder(localRoot.rightChild);
         }
      }
// 后序遍历（递归实现）-------------------------------------------------------------
   private void postOrder(Node localRoot){
      if(localRoot != null)
         {
         postOrder(localRoot.leftChild);
         postOrder(localRoot.rightChild);
         visit(localRoot);       //System.out.print(localRoot.iData + " ");
         }
      }
// -------------------------------------------------------------

2、非递归遍历

总体思想是：因为递归的本质是用栈实现的，所以写出非递归的形式要用到栈。入栈的顺序与访问的顺序相反，如中序遍历访问顺序是left,current,right,所以入栈的顺序相反是right,current,left
steo0:初始化当前节点current
step1:初始化栈
step3:出栈,并访问
Note：中序遍历和后序遍历需要先判断bPushed为true时访问
step2:入栈
循环结束条件是：栈为空

//算法框架 pushNode是入栈的方式
public void templet(Node root){
  //special case
  if(root==null)
   return;
   
  //inital current node
  Node current=root;
  
  //initial stack
  Stack s=new Stack();
  pushNode(current,s);
  
  //loop: base case is stack is empty
  while( !s.empty() ){
     //pop
	 current=s.pop();
	 
	 //visit or push
  }//end while  
}//end templet()

前序遍历（即深度优先搜索）

//current left right 
//step1:push in stack 
push current's right child
push current's left child
visit current node
//step2:pop off stack
//step3: loop step1-step2

private void pushPreOrderNode(Node current, Stack s){
	   Node leftChild=current.leftChild;
	   Node rightChild=curret.rightChild;
	     
	   if(rightChild!=null)    //push rightChild
	      s.push(rightChild);
	   if(leftChild!=null)     //push leftChild
	      s.push(leftChild);
	   visit(current);        //current always first visit in preOrder  
}//end pushPreOrderNode()

public void preOrder(Node root){
    //special case
	if(root==null)
	  return ;
	
	//initial current node
	Node current=root;
	//inintial stack
	Stack s=new Stack();
	pushPreOrderNode(current,s);
	
	//base case:stack is empty
	while( !s.empty() ){
	  //pop
	  current=s.pop();
	  //push
	  pushPreOrderNode(current,s);
	}//end while
}//end preOrder()

中序遍历

left,current,right

public void inOrder( Node root){
   //special case
   if(root==null)
       return;
	   
	Node current=root;
	//initial stack
	Stack s=new Stack();
	pushInOrderNode(current,s);
	
	//pop and visit
	while( !s.empty() ){
		 current=s.pop();
		 if(current.bPushed)
			visit(current);
		 else
			pushInOrderNode(current,s);
	}//end while
}//end postOrder()

private void pushInOrderNode(Node current,Stack s){
   Node leftChild=current.leftChild;
   Node rightChild=curret.rightChild;
   
   if(rightChild!=null){   //push rightChild
	  s.push(rightChild);
	  rightChild.bPushed=false;
   }//end if
   
   s.push(current);        //push current
   
   if(leftChild!=null){    //push leftChild
	  s.push(leftChild);
	  leftChild.bPushed=false;
   }//end if
	  
   //set flag, ture present current's left and right has both pushed
   current.bPushed=true;
   }//end if
}//end pushInOrderNode()

后序遍历

left right current
step1:初始化栈
按照step2初始化栈
step2:入栈
入栈顺序：current,right,left
如果current的中左右节点都入栈了，将current标识为true；
将入栈的左右节点标识初始化为false
step3:出栈
出栈节点设置为current,
如果current标识为ture,访问之；如果为false，做step2步骤
step4:重复step2&step3

public void postOrder( Node root){
   //special case
   if(root==null)
       return;
	   
	Node current=root;
	
	//initial stack
	Stack s=new Stack();
	pushPostOrderNode(current,s);
	
	//pop and visit
	while( !s.empty() ){
	     current=s.pop();
		 if(current.bPushed)
		    visit(current);
		 else
		    pushPostOrderNode(current,s);
	}//end while
}//end postOrder()

// 左右子树尚未入栈，则依次将 根节点,右节点,左节点 入栈
private void  pushPostOrderNode(Node current, Stack s){
   Node leftChild=current.leftChild;
   Node rightChild=curret.rightChild;
   
   s.push(current);        //push current
   if(rightChild!=null){   //push rightChild
	  s.push(rightChild);
	  rightChild.bPushed=false;
   }//end if
   if(leftChild!=null){    //push leftChild
	  s.push(leftChild);
	  rightChild.bPushed=false;
   }//end if
	  
   //set flag, ture present current's left and right has both pushed
   current.bPushed=true;	
}//end pushPostOrderNode()

3 深度优先搜索和层次遍历（广度优先搜索）

// -------------------------------------------------------------
/*
二叉树的深度优先搜索即先序遍历，用栈实现（非递归实现）
*/

// -------------------------------------------------------------
/*
层次搜索，即广度优先搜索
step1:specail case
root==null;
step2:initial current
current=root;
step3:initial queue
step4:remove node in queue, and visit the current node
step5:add node in queue
step6:loop step4 and step5
base case: queue is empty
*/

public void gfs(Noode root){
  //step1:specail case
  if(root==null)
    return ;
  
  //step2:initial current
  Node current=root;
  
  //step3:initial queue
  Queue q=new Queue();
  q.add(current);
  
  //step6:loop step4 and step5
  //base case: queue is empty
  while( !q.empty() ){
    //step4:remove node in queue
	current=q.remove();
	visit(current);
	
	Node leftChild=current.leftChild;
	Node rightChild=curret.rightChild;
	
	//step5:add node in queue
	if(leftChild!=null)
	   q.add(leftChild);
	if(rightChild!=null)
	   q.add(rightChild);
  }//end while 
}//gfs()