이 진 트 리 우선 순위 옮 겨 다 니 기, 중간 순서 옮 겨 다 니 기, 뒤 순서 옮 겨 다 니 는 재 귀 알고리즘 과 비 재 귀 알고리즘

typedef struct TNode *Position;
typedef Position BinTree; /*       */
struct TNode{ /*       */
    int Data; /*      */
    BinTree Left;     /*       */
    BinTree Right;    /*       */
};

/*****************    ******************/ 
/*****    *****/ 
void PreOrderTraversal(BinTree BT)
{
	if( BT ){
		printf("%d ",BT->Data);       //       
		PreOrderTraversal(BT->Left);  //       
		PreOrderTraversal(BT->Right); //        
	}
}

/*****    *****/ 
void InOrderTraversal(BinTree BT)
{
	if( BT ){
		InOrderTraversal(BT->Left);
		printf("%d ",BT->Data);
		InOrderTraversal(BT->Right);
	}
}

/*****    *****/ 
void PostOrderTraversal(BinTree BT)
{
	if( BT ){
		PostOrderTraversal(BT->Left);
		PostOrderTraversal(BT->Right);
		printf("%d ",BT->Data);
	}
}

/*****************     ******************/ 
/*****    *****/ 
void PreOrderTraversal_(BinTree BT)
{
	BinTree T = BT;
	Stack S = CreatStack(MaxSize); /*        S*/ 
	while( T || !IsEmpty(S) ){
		while( T ){  /*              ,        */ 
			printf("%5d ",T->Data);  /*  （  ）  */
			Push(S,T);
			T = T->Left; 
		}
		
		if( !IsEmpty(S) ){
			T = Pop(S);   /*      */ 
			T = T->Right;  /*     */ 
		}
	}
 } 
 
/*****    *****/ 
void InOrderTraversal_(BinTree BT)
{
	BinTree T = BT;
	Stack S = CreatStack(MaxSize); /*        S*/ 
	while( T || !IsEmpty(S) ){
		while( T ){  /*              ,        */ 
			Push(S,T);
			T = T->Left; 
		}
		
		if( !IsEmpty(S) ){
			T = Pop(S);   /*      */
			printf("%5d ",T->Data);  /*  （  ）  */ 
			T = T->Right;  /*     */ 
		}
	}
}

/*****    *****/ 
/*1
             （visit）  
     ，    
         ，         2
   ，      1，    +1，    ，T     (     ),      
  ，   ，T   (        ),      
*/
 void PostOrderTraversal_1(BinTree BT)
{
    BinTree T,BT;
    Stack S = CreatStack(Maxsize);
    while( T || !IsEmpty(s)) {
        while(T){
            T->visit++;//visit   0
            Push(S,T);
            T = T->Left;
        }
        
        if( !isEmpty(S) ){
            T = Pop(S);//    
            if(T->visit==2){
                printf("%5d",T->data);
                T = NULL;
            }
            else{
                T->visit++;
                Push(S,T);//       2，    
                T = T->Right;
            }
        }
    }
}

/*2
        root, left, right          ，
     root, right, left，     “  ”。
          left, right,root ，
   “  ”       .
*/
void PostOrderTraversal_2( BinTree BT )
{
   BinTree T,BT;
   Stack S = CreatStack( MaxSize ); /*        S*/
   Stack Q = CreatStack( MaxSize ); /*        Q，      */
   while( T || !IsEmpty(S) ){
       while(T){ /*              */
           Push(S,T);
           Push(Q,T);/*           ，    */
           T = T->Right; /*     */
       }
       
       if(!IsEmpty(S)){
       T = Pop(S); 
       T = T->Left; /*     */
       }
   }
    
   while( !IsEmpty(Q) ){
       T = Pop(Q);
       printf("%5d ", T->Data); 
   }
}

/*3
         ，    ，     
                   ，
       ，        r           
*/
void PostOrderTraversal_3(BinTree BT){
    BinTree T = BT;
    BinTree r = NULL; 
    Stack S = CreatStack(MaxSize);
    while( T || !isEmpty(S) ){
        if( T ){          //       
            Push(S, T);
            T = T->left;
        }
        else{
            GetTop(S,T);  //      
            if(T->right && T->right != r)
                T = T->right;
            else{
                T = Pop(S);
                printf("%5d ", T->data);
                r = T;      //          
                T = NULL;   //        T   
            }
        }
    }
}