關於二叉樹的遍歷梳理（遞歸、非遞歸、線索二叉樹）

　　二叉樹作為的基本數據結構，應用廣泛，在生活中處處可見，而遍歷二叉樹在二叉樹應用中十分常見。與線性存儲結構不同，二叉樹每個節點都有可能有兩棵子樹，從二叉樹的存儲結構可知：

1 template <typename T>
2 typedef struct BiTNode
3 {
4     T data;
5     struct BiTNode *lchild, *rchild;
6 }BiTree;

　　根節點、左子樹、右子樹——二叉樹的基本組成單位。那麼，根據的遞歸的思想（數據結構嚴蔚敏版）：當一個複雜的問題可以分解成若幹子問題來處理時，其中某些子問題與原問題有相同的特征屬性，則可利用和原問題相同的分析處理方法；反之，這些子問題解決了，原問題也就迎刃而解了。遞歸遍歷就是將原二叉樹分解為若幹子樹。

 1 template <typename T>
 2 int PreOrderTraverse(BiTree & Tree, int (*Visit)(T & e))
 3 {
 4     //Visit函數理解為列印e，若成功返回1，否則返回0。
 5     if (Tree) //判斷樹是否為空樹
 6     {
 7         if (Visit(Tree.data)) //列印節點數據
 8             if (PreOrderTraverse(Tree.lchild, Visit) //向左遍歷
 9                 if (PreOrderTraverse(Tree.rchild, Visit) return 1; //左遍歷退出遍歷右側
10         return 0;
11     }
12     else return 1;
13 }

　　從遞歸工作過程可以看出，第i層棧頂，左子樹返回i-1層進行右子樹遍歷，而右子樹返回則直接刪除棧頂返回（這取決於遍歷的方式：先序遍歷，中序遍歷，後序遍歷）。

　　由此，可以模仿遞歸演算法寫出非遞歸演算法的遍歷函數。

 1 template <typename T>
 2 void PreOrderTraverse(BiTNode & Tree, int (*Visit(T e))
 3 {
 4     InitStack(S); //初始化棧S
 5     BiTree p; 
 6     Push(S, Tree); //根節點入棧
 7     while (!StackEmpty(S))
 8     {
 9         while (GetTop(S, p) && p) 
10         {
11             Visit(p.data);
12             Push(S,(p.lchild); //左子樹壓棧
13         } //while
14         Pop(S, *p); //空指針出棧，用p返回其節點---------1
15         if (!StackEmpty(S))
16         {
17             Pop(S, p); //-------------------------------2
18             Push(S,p.rchild);
19         } //if
20     } //while
21 }

　　使用棧來管理遍歷的過程，由於是先序遍歷，所以每向左壓一次棧時便Visit一次節點，到達最左端時（依次從根節點Visit了左子樹各子樹的根節點）向右壓棧，到達右葉子節點時回退，由於第17行的退棧，會使得棧頂變為上上層的根節點。也就是遍歷右子樹時不需要保存當前層的根指針，可直接修改棧頂的指針。說的有些不清楚，但這和遞歸演算法思路一致，不過是自己管理棧的進出。

　　註意，粗略一看可能會產生疑惑：Pop退棧p多退了一層。這裡第一個Pop函數退出空指針，p是其返回值也為空，經過第二個Pop函數p才為有效棧頂。就比如，小紅組裝某個物件將步驟列了個清單，她將要著手去做這一步驟時，將該步驟從清單划去，划去的這一時刻是上一件事產生的影響。

　　這兩種遍歷是對非線性結構進行線性化操作，引用雙向鏈表的前驅後繼的思想，修改二叉樹的現有數據結構，新增兩個標誌域——LTag和RTag。

 1 template <typename T>
 2 typedef struct BiThrNide
 3 {
 4     T data;
 5     int LTag,RTag;
 6     BiThrTree *lchild, *rchild;
 7 }BiThrTree;
 8 
 9 void InOrderTraverse(BiThrTree & Tree, int (*Visit(T e)))
10 {
11     //Tree的lchild指向樹的根節點
12     //標誌符LTag、RTag為0則指針域指向孩子節點，為1指向前驅或後繼
13     BiThrTree p;
14     while (p != Tree)
15     {
16         while (p.LTag == 0) p = p.lchild; //向左遍歷
17         if (!Visit(p.data)) exit(ERROR);
18         while (p.RTag == 1 && p.rchild != Tree) //沒有右子樹，指向後繼，且後繼不為頭結點
19         {
20             P = P.rchild; //向後繼遍歷
21             Visit(p.data);
22         }
23         p = p.rchild;
24     }
25 }

　　由於線索二叉樹存儲結構較普通二叉樹豐滿，所以遍歷過程也更為好理解，此處不做贅述。