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라고 판단할 때 방문2: step 입고 순환 종료 조건은: 창고가 비어 있음

//  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()