遞歸遍歷

1. 先序遍歷
   遍歷過(guò)程為：
   ① 訪(fǎng)問(wèn)根結(jié)點(diǎn)；
   ② 先序遍歷其左子樹(shù)；
   ③ 先序遍歷其右子樹(shù)。

void PreOrderTraversal(BinTree BT)//先序遍歷 
{
	 if(BT)
	 {
		  printf("]",BT->Data);
		  PreOrderTraversal(BT->Left);
		  PreOrderTraversal(BT->Right);
	 }
} 

2. 中序遍歷
遍歷過(guò)程為：
① 中序遍歷其左子樹(shù)；
② 訪(fǎng)問(wèn)根結(jié)點(diǎn)；
③ 中序遍歷其右子樹(shù)

void PreOrderTraversal(BinTree BT)//中序遍歷 
{
	 if(BT)
	 {
		  PreOrderTraversal(BT->Left);
		  printf("]",BT->Data);
		  PreOrderTraversal(BT->Right);
	 }
}

3. 后序遍歷
   遍歷過(guò)程為：
   ① 后序遍歷其左子樹(shù)； ② 后序遍歷其右子樹(shù)； ③ 訪(fǎng)問(wèn)根結(jié)點(diǎn)。
   

void PostOrderTraversal( BinTree BT )
{
    if( BT ) { 
        PostOrderTraversal( BT->Left ); 
        PostOrderTraversal( BT->Right); 
        printf(“%d”, BT->Data);
    }
}

非遞歸遍歷

1. 先序遍歷

void InOrderTraversal( BinTree BT ) 
{  
    BinTree T = BT;
    Stack S = CreatStack( MaxSize ); //創(chuàng)建并初始化堆棧S
    while( T || !IsEmpty(S) )
    {
       while(T) //一直向左并將沿途結(jié)點(diǎn)壓入堆棧
       {  
           printf(“]”, T->Data); //（訪(fǎng)問(wèn)）打印結(jié)點(diǎn)
           Push(S,T);
           T = T->Left;
       }
       if(!IsEmpty(S))
       {
           T = Pop(S); /*結(jié)點(diǎn)彈出堆棧*/    
           T = T->Right; /*轉(zhuǎn)向右子樹(shù)*/
       }
    }
}

2. 中序遍歷

void PreOrderTraversal(BinTree BT)//中序遍歷 ，非遞歸
{
    BinTree T = BT;
    Stack S = CreatStack(Maxsize);
    while( T || !IsEmpty(S) )
    {
   	 while( T )
   	  {
   		   Push(S,T);
   		   T = T->Left;
   	  }
   	  if(!IsEmpty(S) )
   	  {
   		   T = Pop( S );
   		   printf("]",T->Data);
   		   T = T->Right;
   	   }
    } 
} 

3. 后序遍歷

void PostorderTraversal(BinTree BT)//序遍歷 ，非遞歸
{
   BinTree T = BT;
   Stack S = CreateStack(MaxSize);
   while(T || !isEmpty(S))//只要沒(méi)有完全輸出，包括在堆棧中的和二叉樹(shù)中的元素，一直進(jìn)行循環(huán)
   {
       while(T)
       {
           Push(S, T);
           T = T->left;
       }
       T = Pop(S);  //沒(méi)有左子節(jié)點(diǎn)時(shí)，先拿出此節(jié)點(diǎn)
       if(!isEmpty(S))
       {
           if(T->right)  //判斷是否有右子節(jié)點(diǎn)，如有，再壓入棧，進(jìn)入下一層；如沒(méi)有則訪(fǎng)問(wèn)
           {
               Push(S, T);
               T = T->right;
           }
           else
           {
               printf("]", T->Data);
               T = NULL;  //將當(dāng)前已訪(fǎng)問(wèn)節(jié)點(diǎn)置為NULL，防止回到上一層時(shí)重復(fù)遍歷
           }
       }
   }
}