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,leftsteo0:初始化当前节点currentstep1:初始化栈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:pop current node	//step2:visit current node	//step3:push current's right child	//step4:push current's left child	//step5: loop step1-step5privete void pushPreOrderNode(Node current, Stack s){   if(current==null)      return ;   	if(!s.empty()){	   leftChild=current.leftChild;	   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 if }//end pushPreOrderNode()public void preOrder(Node root){    //special case	if(root==null)	  return ;		//inintial 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){    if(current==null)	  return;	if(!s.empty()){	   leftChild=current.leftChild;	   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);	      rightChild.bPushed=false;	   }//end if		  	   //set flag, ture present current's left and right has both pushed	   current.bPushed=true;	   }//end if	}//end if}//end pushInOrderNode()// -------------------------------------------------------------// 后序遍历（递归实现）-------------------------------------------------------------/*left right currentstep1:初始化栈按照step2初始化栈step2:入栈入栈顺序：current,right,left如果current的中左右节点都入栈了，将current标识为true；将入栈的左右节点标识初始化为falsestep3:出栈出栈节点设置为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){    if(current==null)	  return;	if(!s.empty()){	   leftChild=current.leftChild;	   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 if	}//end if	}//end pushPostOrderNode()

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

// -------------------------------------------------------------/*二叉树的广度深度优先搜索即先序遍历，用栈实现（非递归实现）*/// -------------------------------------------------------------/*层次搜索，即广度优先搜索step1:specail caseroot==null;step2:initial currentcurrent=root;step3:initial queuestep4:remove node in queue, and visit the current nodestep5:add node in queuestep6:loop step4 and step5base 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()