二叉樹先序周遊非遞歸詳解
1. 首先給出一顆二叉樹，如下圖所示：
圖1一顆簡單的二叉樹
根據二叉樹的先序周遊的特性，該二叉樹先序周遊順序為：ABDEGCFHI;
2. 一般周遊一顆二叉樹，先序中序或者後序，大家最喜歡也最熟悉的方法是采用遞歸的形式來描述，但是在面試或者筆試的過程中，面試官一般都會要求采用非遞歸形式的二叉樹周遊過程。我們先給出二叉樹的遞歸形式（以先序周遊為例子），然後給出二叉樹的非遞歸形式。
Void priorOrder(BiTree root)
{
If(root!=NULL)
{
Cout<<root->data;//輸出根節點的元素值;
priorOrder(root->left);//周遊左子樹;
priOrder(root->right);//周遊右子樹；
}
}
3. 二叉樹的非遞歸寫法如下，先給出代碼，後面會具體給出代碼分析：
Void priorOrder(BiTree root){
BiTree stack[MaxSize],p;
int top=1;
if(root!=NULL){
stack[++top]=p;//根節點入棧;
while(top>0){
p=stack[top--];//根節點出棧，并将p指向目前出棧的節點;
cout<<p->data<<”\t”;
if(p->right!=NULL)//右孩子不為空，将右孩子入棧；
stack[++top]=p->right;
if(p->left!=NULL) //左孩子不為空，将左孩子入棧；
stack[++top]=p->left;
}
}
}
二叉樹先序周遊非遞歸的思想：首先外層循環的判斷條件時根節點不為空，不為空的情況下，将根節點入棧，然後在棧的大小不為空的前提下循環，将棧頂指針出棧，建立一個臨時的棧，将該棧指向目前出棧的結點，并判斷該結點的右孩子是否為空，為空則不進行處理，不為空，則将右孩子入棧，同時判斷該結點的左孩子是否為空，為空不進行處理，不為空，則将左孩子入棧，關于為什麼要先将右孩子入棧，左孩子後入棧的問題，大家應該清楚（棧是先進後出，二叉樹先序周遊是根左右，右孩子先入棧，坐孩子後入棧，那麼出棧的時候就會先輸出左孩子，然後是右孩子）。
針對上面的圖，對于非遞歸的先序周遊進行圖形化分析：
歡迎大家指出錯誤！