分享下關於三種二叉樹遍歷的非遞歸實現的，轉到這兒來吧。程序都是偽代碼，因為是考研復習期間寫的，數據結構參考了嚴蔚敏的《數據結構》。
《數據結構 C++ 語言描述》(Data Structures C++ ) PDF+源碼 劉衛東，沈官林 譯 http://www.linuxidc.com/Linux/2014-09/107319.htm
先看遞歸實現：
void Traverse(BiTree T){
if(T){
//visit,先序遍歷
Traverse(T->lchild);
//visit,中序遍歷
Traverse(T->rchild);
//visit,後序遍歷
}
}
可以看到三種遍歷方法的遞歸實現形式完全一樣，只需改變visit的位置，就得到不同遍歷序列。因此從情感上覺得非遞歸實現應該形式也完全一樣，這是課本給的中序非遞歸實現：
void InOrderTraverse（BiTree T, status(* visit)(TElemType e)）{
InitStack(s); p=T;
while(p || !StackEmpty(s)){
if(p){
Push(s,p); p=p->lchild;
}else{
Pop(s,p);visit(p->data);p=p->rchild;
}
}
}
只需將visit(p->data);移動到Push(s,p); 後，就能得到先序遍歷的非遞歸實現。然後在考慮後序遍歷時，發現這種形式不適用後序遍歷，所以後來不得不自己寫了一個後序遍歷的非遞歸程序。然而心裡始終覺得不舒服，為什麼遞歸實現上明明如此統一，到了非遞歸實現後序遍歷就與眾不同了呢？由於復習時間很緊張，對於這個問題基本都是零零散散的，走路蹲點發呆無聊的時候，漫無邊際地胡思亂想~直到某天蹲點的時候，想明白了。
課本的非遞歸實現對棧的使用並不和遞歸棧相同，因此結點的進出棧順序也和遞歸棧明顯不同，基於這個道理，寫了一個完全仿照遞歸棧工作的非遞歸實現，關鍵是出棧的條件發生了變化，而且從直覺上，這個程序的出棧和進棧語句(Push，Pop)，賦值左孩子和右孩子(p=p->lchild或rchild)都應只出現一次，如果出現了多次，應該是功能重復了，可以再進行縮減。
status Traverse(BiTree T, status(* visit)(TElemType e)){
IniTStack(s); p=T; p1=NULL;
while(p || !StackEmpty(s)){
if(p){
Push(s,p);
//visit,先序
p=p->lchild;
}else{
GetTop(s,p);
//visit,中序
if(p->rchild==p1 || p->rchild==NULL){
Pop(s,p1);p=NULL;
//visit,後序
}else{
p=p->rchild;p1=NULL;
}
}
}
}
在這種形式下，只需改變visit的位置就能得到三種遍歷的非遞歸實現，結點的進出棧順序完全和遞歸棧一樣，判斷結點是否出棧的條件是：上一次出棧的結點是棧頂元素的右孩子。
對幾棵二叉樹進行了試驗，結果是對的，但不知道有沒有疏忽的地方。
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
