二叉樹-遍歷終極版
對于二叉樹的遍歷，最熟悉的就是遞歸遍歷了，對二叉樹的非遞歸遍歷大致知道一些，但是不太熟悉，尤其是后續非遞歸遍歷的實現，一直比較懵逼，于是上網查詢了一下，果然大神無處不在，那個后序遍歷的雙棧法，簡直讓人拍案叫絕，下面總結下。
1、先序遍歷
先序遍歷即順序為：根節點->左節點->右節點
遞歸版：
void PreOrderTraverse(BTree T)
{
if (T != NULL)
{
cout << T->val;
PreOrderTraverse(T->left);
PreOrderTraverse(T->right);
}
}
非遞歸版：
根據前序遍歷訪問的順序，優先訪問根結點，然后再分別訪問左孩子和右孩子。即對于任一結點，其可看做是根結點，因此可以直接訪問，訪問完之后，若其左孩子不為空，按相同規則訪問它的左子樹；當訪問完其左子樹后，再訪問它的右子樹。因此其處理過程如下：
對于任一結點P：
1)訪問結點P，并將結點P入棧;
2)判斷結點P的左孩子是否為空，若不為空，則將P的左孩子置為當前的結點P;若為空，則取棧頂結點并進行出棧操作，并將棧頂結點的右孩子置為當前的結點P，循環至1)
3)直到P為NULL并且棧為空，則遍歷結束。
代碼如下：
void PreOrderTraverse(BTree T)
{
std::stack<BTree> S;
while(T||!S.empty())
{
while(T)
{
S.push(T);
cout<<T->val;
T=T->left;
}
if(!S.empty())
{
T=S.top();
S.pop();
T=T->right;
}
}
}
上面那個遞歸版是常規版，這個我覺得更好，思路是這樣的，節點的右左節點分別入棧，根絕棧的“先進后出”特性，那么先輸出的必然是左節點。這個方法代碼簡潔，思路獨特。
void PreOrderTraverse(BTree T) //先序遍歷的非遞歸
{
if(!T)
return ;
stack<BiTree> s;
s.push(T);
while(!s.empty())
{
BiTree temp = s.top();
cout<<temp->data<<" ";
s.pop();
if(temp->rchild)
s.push(temp->rchild);
if(temp->lchild)
s.push(temp->lchild);
}
}
2、中序遍歷
中序遍歷的順序是：左節點、根節點、右節點
遞歸版：
void MidOrderTraaerse(BTree T)
{
if(T!=NULL)
{
MidOrderTraverse(T->left);
cout<<T->val;
MideOrderTraverse(T->right);
}
}
非遞歸版：
根據中序遍歷的順序，對于任一結點，優先訪問其左孩子，而左孩子結點又可以看做一根結點，然后繼續訪問其左孩子結點，直到遇到左孩子結點為空的結點輸出節點值，按相同的規則訪問其右子樹。
因此其處理過程如下：
對于任一結點P，
1)若節點p不為空，則將P入棧并將P的左孩子置為當前的P，然后對P再進行相同的處理；
2)若訪問到左孩子為空后，則取棧頂元素并進行出棧操作，輸出該棧頂結點值，然后將當前的P置為棧頂結點的右孩子；
3)直到P為NULL并且棧為空則遍歷結束
代碼如下：
void MidOrderTraverse(BTree T)
{
std::stack<BTree> S;
while(T||!S.empty())
{
while(T)
{
S.push(T);
T=T->eft;
}
T=S.top();
cout<<T->val;
S.pop();
T=T->ight;
}
}
3、后序遍歷
后序遍歷的順序是：左節點、右節點、根節點
遞歸版：
void BackOrderTraverse(BTree T)
{
if(T!=NULL)
{
BackOrderTraverse(T->left);
BackOrderTraverse(T->right);
cout<<T->val;
}
}
非遞歸版：
1）版本1：
void PostOrder_Nonrecursive1(BTree T) // 后序遍歷的非遞歸
{
stack<BiTree> S;
BiTree curr = T ; // 指向當前要檢查的節點
BiTree previsited = NULL; // 指向前一個被訪問的節點
while(curr != NULL || !S.empty()) // 棧空時結束
{
while(curr != NULL) // 一直向左走直到為空
{
S.push(curr);
curr = curr->lchild;
}
curr = S.top();
// 當前節點的右孩子如果為空或者已經被訪問，則訪問當前節點
if(curr->rchild == NULL || curr->rchild == previsited)
{
cout<<curr->data<<" ";
previsited = curr;
S.pop();
curr = NULL;
}
else
curr = curr->rchild; // 否則訪問右孩子
}
}
2）版本2：
采用雙棧法，這個真是神來之筆，對于想出這個辦法的人，真是佩服的五體投地。為了解釋原理，的看個實際例子，如下。
對于上面上面的二叉樹，對樹先左后右的將各個節點逐個放到棧1中,然后將棧1元素放到棧2中，過程如下：
棧1：A
棧1：空 | 棧2： A
棧1：B C -> B | 棧2：A C
棧1：B F G ->B F | 棧2：A C G
棧1：B F -> B | 棧2：A C G F
棧1：B -> D E | 棧2：A C G F B
棧1：D E -> D | 棧2：A C G F B E
棧1：空 | 棧2：A C G F B E D
最后輸出棧2，就是D E B F G C A,你說6不6.
void PostOrder_Nonrecursive(BTree T) // 后序遍歷的非遞歸 雙棧法
{
stack<BiTree> s1 , s2;
BiTree curr ; // 指向當前要檢查的節點
s1.push(T);
while(!s1.empty()) // 棧空時結束
{
curr = s1.top();
s1.pop();
s2.push(curr);
if(curr->lchild)
s1.push(curr->lchild);
if(curr->rchild)
s1.push(curr->rchild);
}
while(!s2.empty())
{
printf("%c ", s2.top()->data);
s2.pop();
}
}
4、深度優先遍歷
深度優先遍歷，也就深入的遍歷，沿著每一個分支直到走到最后，然后才返回來遍歷剩余的節點。二叉樹不同于圖，圖需要標記節點是否已經訪問過，因為可能會存在環，而二叉樹不會出現環，所以不需要標記。那么，我們只需要一個棧空間，來壓棧就好了。因為深度優先遍歷，遍歷了根節點后，就開始遍歷左子樹，所以右子樹肯定最后遍歷。我們利用棧的性質，先將右子樹壓棧，然后在對左子樹壓棧。此時，左子樹節點是在top上的，所以可以先去遍歷左子樹。
void DepthFirstTravel(BTree T)
{
stack<BTree> s;
s.push(T);
while(!s.empty())
{
T = s.top();
cout << T->data << " ";
s.pop();
if(T->rchild != NULL)
{
s.push(T->rchild);
}
if(T->lchild != NULL)
{
s.push(T->lchild);
}
}
}
5、廣度優先遍歷
對于廣度優先遍歷二叉樹，也就是按層次的去遍歷。依次遍歷根節點，然后是左孩子和右孩子。所以要遍歷完當前節點的所有孩子，這樣才是層次遍歷嘛。此時我們就不能用棧這個數據結構了，因為棧只能在棧頂操作。在這里，我們需要根據左右孩子的順序來輸出，所以就是先進先出的原則，那么我們當然就想到了隊列這個數據結構。可以在rear依次插入左右孩子，在front依次讀取并刪除左右孩子，這樣就保證了層次的輸出。
void BreadthFirstTravel(BTree T)
{
queue<BTree> q;
q.push(T);
while(!q.empty())
{
T = q.front();
cout << T->data << " ";
q.pop();
if(T->lchild != NULL)
{
q.push(T->lchild);
}
if(T->rchild != NULL)
{
q.push(T->rchild);
}
}
}
參考
來自：http://blog.csdn.net/yixianfeng41/article/details/55228458