二叉樹是一種非常重要的數(shù)據(jù)結(jié)構(gòu)，很多其它數(shù)據(jù)結(jié)構(gòu)都是基于二叉樹的基礎(chǔ)演變而來的。對于二叉樹，有前序、中序以及后序三種遍歷方法。因為樹的定義本身就 是遞歸定義，因此采用遞歸的方法去實現(xiàn)樹的三種遍歷不僅容易理解而且代碼很簡潔。而對于樹的遍歷若采用非遞歸的方法，就要采用棧去模擬實現(xiàn)。在三種遍歷 中，前序和中序遍歷的非遞歸算法都很容易實現(xiàn)，非遞歸后序遍歷實現(xiàn)起來相對來說要難一點。

一.前序遍歷

前序遍歷按照“根結(jié)點-左孩子-右孩子”的順序進(jìn)行訪問。

1. 遞歸實現(xiàn)

1 void preOrder1(BinTree *root)     //遞歸前序遍歷 
2 {
3     if(root!=NULL)
4     {
5         cout<<root->data<<" ";
6         preOrder1(root->lchild);
7         preOrder1(root->rchild);
8     }
9 }

2. 非遞歸實現(xiàn)
   根據(jù)前序遍歷訪問的順序，優(yōu)先訪問根結(jié)點，然后再分別訪問左孩子和右孩子。即對于任一結(jié)點，其可看做是根結(jié)點，因此可以直接訪問，訪問完之后，若其左孩子不為空，按相同規(guī)則訪問它的左子樹；當(dāng)訪問其左子樹時，再訪問它的右子樹。因此其處理過程如下：

   對于任一結(jié)點P：

   1. 訪問結(jié)點P，并將結(jié)點P入棧;
   2. 判斷結(jié)點P的左孩子是否為空，若為空，則取棧頂結(jié)點并進(jìn)行出棧操作，并將棧頂結(jié)點的右孩子置為當(dāng)前的結(jié)點P，循環(huán)至1);若不為空，則將P的左孩子置為當(dāng)前的結(jié)點P;
   3. 直到P為NULL并且棧為空，則遍歷結(jié)束。

1 void preOrder2(BinTree *root)     //非遞歸前序遍歷  
2 { 
3     stack<BinTree*> s; 
4     BinTree *p=root;
5     while(p!=NULL||!s.empty()) 
6     {
7         while(p!=NULL) 
8         { 
9             cout<<p->data<<" ";
10             s.push(p);
11             p=p->lchild;
12         }
13         if(!s.empty())
14         {
15             p=s.top();
16             s.pop();
17             p=p->rchild;
18         }
19     }
20 }

二.中序遍歷

中序遍歷按照“左孩子-根結(jié)點-右孩子”的順序進(jìn)行訪問。

1. 遞歸實現(xiàn)

1 void inOrder1(BinTree *root)      //遞歸中序遍歷
2 {
3     if(root!=NULL)
4     {
5         inOrder1(root->lchild);
6         cout<<root->data<<" ";
7         inOrder1(root->rchild);
8     }
9 }

2. 非遞歸
   根據(jù)中序遍歷的順序，對于任一結(jié)點，優(yōu)先訪問其左孩子，而左孩子結(jié)點又可以看做一根結(jié)點，然后繼續(xù)訪問其左孩子結(jié)點，直到遇到左孩子結(jié)點為空的結(jié)點才進(jìn)行訪問，然后按相同的規(guī)則訪問其右子樹。因此其處理過程如下：

   對于任一結(jié)點P:

   1. 若其左孩子不為空，則將P入棧并將P的左孩子置為當(dāng)前的P，然后對當(dāng)前結(jié)點P再進(jìn)行相同的處理；
   2. 若其左孩子為空，則取棧頂元素并進(jìn)行出棧操作，訪問該棧頂結(jié)點，然后將當(dāng)前的P置為棧頂結(jié)點的右孩子；
   3. 直到P為NULL并且棧為空則遍歷結(jié)束。

1 void inOrder
2(BinTree *root)      //非遞歸中序遍歷 
2 { 
3     stack<BinTree*> s; 
4     BinTree *p=root; 
5     while(p!=NULL||!s.empty()) 
6     { 
7         while(p!=NULL) 
8         { 
9             s.push(p);
10             p=p->lchild;
11         }
12         if(!s.empty())
13         {
14             p=s.top();
15             cout<<p->data<<" ";
16             s.pop();
17             p=p->rchild;
18         }
19     }    
20 } 

三.后序遍歷

后序遍歷按照“左孩子-右孩子-根結(jié)點”的順序進(jìn)行訪問。

1. 遞歸實現(xiàn)

1 void postOrder1(BinTree *root)    //遞歸后序遍歷
2 {
3     if(root!=NULL)
4     {
5         postOrder1(root->lchild);
6         postOrder1(root->rchild);
7         cout<<root->data<<" ";
8     }    
9 }

2. 非遞歸實現(xiàn)
   　　
   后序遍歷的非遞歸實現(xiàn)是三種遍歷方式中最難的一種。因為在后序遍歷中，要保證左孩子和右孩子都已被訪問并且左孩子在右孩子前訪問才能訪問根結(jié)點，這就為流程的控制帶來了難題。下面介紹兩種思路。

   第一種思路：對于任一結(jié)點P，將其入棧，然后沿其左子樹一直往下搜索，直到搜索到?jīng)]有左孩子的結(jié)點，此時該結(jié)點出現(xiàn)在棧頂，但是此時不能將其出棧并訪問， 因此其右孩子還為被訪問。所以接下來按照相同的規(guī)則對其右子樹進(jìn)行相同的處理，當(dāng)訪問完其右孩子時，該結(jié)點又出現(xiàn)在棧頂，此時可以將其出棧并訪問。這樣就 保證了正確的訪問順序?？梢钥闯?，在這個過程中，每個結(jié)點都兩次出現(xiàn)在棧頂，只有在第二次出現(xiàn)在棧頂時，才能訪問它。因此需要多設(shè)置一個變量標(biāo)識該結(jié)點是 否是第一次出現(xiàn)在棧頂。

 1 void postOrder2(BinTree *root)    //非遞歸后序遍歷 
2 { 
3     stack<BTNode*> s; 
4     BinTree *p=root; 
5     BTNode *temp; 
6     while(p!=NULL||!s.empty()) 
7     { 
8         while(p!=NULL)              //沿左子樹一直往下搜索，直至出現(xiàn)沒有左子樹的結(jié)點  
9         {
10             BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
11             btn->btnode=p;
12             btn->isFirst=true;
13             s.push(btn);
14             p=p->lchild;
15         }
16         if(!s.empty())
17         {
18             temp=s.top();
19             s.pop();
20             if(temp->isFirst==true)     //表示是第一次出現(xiàn)在棧頂 
21              {
22                 temp->isFirst=false;
23                 s.push(temp);
24                 p=temp->btnode->rchild;    
25             }
26             else                        //第二次出現(xiàn)在棧頂 
27              {
28                 cout<<temp->btnode->data<<" ";
29                 p=NULL;
30             }
31         }
32     }    
33 }

本文作者：張元一