後序遍歷二叉樹演算法
⑴ 先序遍歷和後序遍歷是什麼
1、先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。
首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。
例如，下圖所示二叉樹的遍歷結果是：ABDECF
（1）後序遍歷左子樹
（2）後序遍歷右子樹
（3）訪問根結點
如右圖所示二叉樹
後序遍歷結果：DEBFCA
已知前序遍歷和中序遍歷，就能確定後序遍歷。
(1)後序遍歷二叉樹演算法擴展閱讀：
圖的遍歷演算法主要有兩種，
一種是按照深度優先的順序展開遍歷的演算法，也就是深度優先遍歷；
另一種是按照寬度優先的順序展開遍歷的演算法，也就是寬度優先遍歷。寬度優先遍歷是沿著圖的深度遍歷圖的所有節點，每次遍歷都會沿著當前節點的鄰接點遍歷，直到所有點全部遍歷完成。
如果當前節點的所有鄰接點都遍歷過了，則回溯到上一個節點，重復這一過程一直到已訪問從源節點可達的所有節點為止。
如果還存在沒有被訪問的節點，則選擇其中一個節點作為源節點並重復以上過程，直到所有節點都被訪問為止。
利用圖的深度優先搜索可以獲得很多額外的信息，也可以解決很多圖論的問題。寬度優先遍歷又名廣度優先遍歷。通過沿著圖的寬度遍歷圖的節點，如果所有節點均被訪問，演算法隨即終止。寬度優先遍歷的實現一般需要一個隊列來輔助完成。
寬度優先遍歷和深度優先遍歷一樣也是一種盲目的遍歷方法。也就是說，寬度遍歷演算法並不使用經驗法則演算法， 並不考慮結果的可能地址，只是徹底地遍歷整張圖，直到找到結果為止。圖的遍歷問題分為四類：
1、遍歷完所有的邊而不能有重復，即所謂「歐拉路徑問題」（又名一筆畫問題）；
2、遍歷完所有的頂點而沒有重復，即所謂「哈密頓路徑問題」。
3、遍歷完所有的邊而可以有重復，即所謂「中國郵遞員問題」；
4、遍歷完所有的頂點而可以重復，即所謂「旅行推銷員問題」。
對於第一和第三類問題已經得到了完滿的解決，而第二和第四類問題則只得到了部分解決。第一類問題就是研究所謂的歐拉圖的性質，而第二類問題則是研究所謂的哈密頓圖的性質。
⑵ c++二叉樹的幾種遍歷演算法
遍歷二叉樹的所有結點且僅訪問一次。按照根節點位置的不同分為前序遍歷，中序遍歷，後序遍歷（除此之外還有層次遍歷，但不常用，此處不做解釋）。
1.前序遍歷：根節點->左子樹->右子樹（根節點在前面）。
2.中序遍歷：左子樹->根節點->右子樹（根節點在中間）。
3.後序遍歷：左子樹->右子樹->根節點（根節點在後邊）。
例如：求下面樹的三種遍歷：
前序遍歷：abdefgc；
中序遍歷：debgfac；
後序遍歷：edgfbca。
⑶ 用遞歸演算法先序中序後序遍歷二叉樹
1、先序
void PreOrderTraversal(BinTree BT)
{
if( BT )
{
棗蘆 printf(「%d 」, BT->Data); //對節點做些訪問比如列印
PreOrderTraversal(BT->Left); //訪問左兒子
PreOrderTraversal(BT->Right); //訪問右兒子
}
}
2、中序
void InOrderTraversal(BinTree BT)
{
if(BT)
{
InOrderTraversal(BT->Left);
printf("%d ", BT->Data);
InOrderTraversal(BT->Right);
}
}
3、後序
void PostOrderTraversal(BinTree BT)
{
if (BT)
{
PostOrderTraversal(BT->Left);
PostOrderTraversal(BT->Right);
printf("%d ", BT->Data);
}
}
(3)後序遍歷二叉樹演算法擴展閱讀：
注意事項
1、前序遍歷
從整棵二叉樹的根結點開始，對於任意結點VV，訪問結點VV並將結點VV入棧，並判斷結點VV的左子結點LL是否為空。若LL不為空，則將LL置為當前結點VV；若LL為空，則取出棧頂結點，並將棧頂結點的右子結點置為當前結點VV。
2、中序遍歷
從整棵凳滑帶二叉樹的根結點開始，對於任一結點VV，判斷其左子結點LL是否為空。若LL不為空，則將VV入棧並將L置為當前結點VV；若讓襲LL為空，則取出棧頂結點並訪問該棧頂結點，然後將其右子結點置為當前結點VV。重復上述操作，直到當前結點V為空結點且棧為空，遍歷結束。
3、後序遍歷
將整棵二叉樹的根結點入棧，取棧頂結點VV，若VV不存在左子結點和右子結點，或VV存在左子結點或右子結點，但其左子結點和右子結點都被訪問過了，則訪問結點VV，並將VV從棧中彈出。若非上述兩種情況，則將VV的右子結點和左子結點依次入棧。重復上述操作，直到棧為空，遍歷結束。