在計算機科學中二叉樹，binary tree，是一種資料結構，在該資料結構中每個節點最多有兩個子節點，如圖所示：
二叉樹的定義就是這樣簡單，但這種看起來很簡單的資料結構遍歷起來一點都不簡單。
如何遍歷二叉樹所謂遍歷簡單的講就好比在迷宮中尋寶，寶物就藏在某一個樹節點當中，但我們並不知道具體在哪個節點上，因此要找到寶物就需要將全部的樹節點系統性的搜尋一遍。
那麼該怎麼系統性的搜尋一遍二叉樹呢？
給定一個單鏈表你幾乎不需要思考就能知道該如何遍歷，很簡單，拿到頭節點後處理當前節點，然後拿到頭節點的下一個節點(next)重複上述過程直到節點為空。
你會看到遍歷連結串列的規則很簡單，原因就在於連結串列本身足夠簡單，就是一條線，但是二叉樹不一樣，二叉樹不是一條簡單的"線"，而是一張三角形的"網"。
那麼給定一棵二叉樹，你該如何遍歷呢？以上圖為例，你該如何系統性的搜尋一遍所有的節點呢(1,2,3,4,5,6)？
有的同學可能已經看出來了，我們可以一層一層的搜尋，依次從左到右遍歷每一層節點，直到當前層沒有節點為止，這是二叉樹的一種遍歷方法。樹的這種層級遍歷方法利用了樹的深度這一資訊(相對於根節點來說)，同一層的節點其深度相同，那麼我們是不是可以利用樹有左右子樹這一特點來進行遍歷呢？答案是肯定的。
如上圖所示1的左子樹是2，2的左子樹是3，2的右子樹是4。。。
假設我們首先遍歷根節點1，然後呢，你可能會想然後遍歷2的左子樹吧，也就是2，當我們到了2這個節點之後再怎麼辦呢？要遍歷2的右子樹嗎？顯然我們不應該去遍歷2的右子樹，為什麼？原因很簡單，因為從節點1到節點2我們是沿著左子樹的方向來遍歷的，我們沒有理由到節點2的時候改變這一規則，接下來我們繼續沿用這一規則，也就是首先遍歷左子樹。
我們來到了節點3，節點3的左子樹為空，因此無需遍歷，然後呢？顯然我們應該遍歷節點3的右子樹，但是3的右子樹也為空，這時以3為根節點的樹全部遍歷完畢。
當遍歷完節點3後該怎麼辦呢？如果你在迷宮中位於節點3，此時節點3已經是死衚衕了，因此你需要做的就是沿著來時的路原路返回，回退到上一個節點也就是3的父節點2，這在計算機演算法中被稱為回溯，這是系統性搜尋過程中常見的操作，回到2後我們發現2的左子樹已經搜尋完畢，因此接下來需要搜尋的就是2的右子樹也就是節點4，因為節點4還沒有被搜尋過，當來到節點4後我們可以繼續使用上述規則直到這顆樹種所有的節點搜尋完畢為止，為什麼到節點4的時候可以繼續沿用之前的規則，原因很簡單，因為以4為根節點的子樹本身也是一棵樹，因此上述規則同樣適用。
因此總結一下該規則就是：
處理當前節點；搜尋當前節點的左子樹；左子樹搜尋完畢後搜尋當前節點的右子樹；這種先處理當前節點，然後再處理當前節點的左子樹和右子樹的遍歷方式被稱為先序遍歷(pre_order)；當然我們也可以先遍歷左子樹，然後處理當前節點再遍歷右子樹，這種遍歷順序被稱為中序遍歷(in_order)；也可以先遍歷左子樹再遍歷右子樹，最後處理當前節點，這種遍歷順序被稱為後序遍歷(post_order)。
遞迴實現遍歷二叉樹在講解遞迴遍歷二叉樹前我們首先用程式碼表示一下二叉樹的結構：
struct tree {struct tree* left;struct tree* right;int value;};從定義上我們可以看出樹本身就是遞迴定義的，二叉樹的左子樹是二叉樹(struct tree* left)，二叉樹的右子樹也是二叉樹(struct tree* right)。假設給定一顆二叉樹t，我們該如何遍歷這顆二叉樹呢？
struct tree* t; // 給定一顆二叉樹有的同學可能會覺得二叉樹的遍歷是一個非常複雜的過程，真的是這樣的嗎？
我們再來看一下上一節中遍歷二叉樹的規則：
處理當前節點；搜尋當前節點的左子樹；左子樹搜尋完畢後搜尋當前節點的右子樹；假設我們已經實現了樹的遍歷函式，這個函式是這樣定義的：
void search_tree(struct tree* t);只要呼叫search_tree函式我們就能把一棵樹的所有節點打印出來：
struct tree* t; // 給定一顆二叉樹search_tree(t); // 列印二叉樹所有節點要是真的有這樣一個函式實際上我們的任務就完成了，如果我問你用這個函式把樹t的左子樹節點都打印出來該怎麼寫程式碼你肯定會覺得侮辱智商，很簡單啊，不就是把樹t的左子樹傳給search_tree這個函式嗎？
seartch_tree(t->left); // 列印樹t的左子樹那麼列印樹t的右子樹呢？同樣easy啊
search_tree(t->right); // 列印樹t的右子樹是不是很簡單，那麼列印當前節點的值呢？你肯定已經懶得搭理我了 :)
printf("%d ", t->value); // 列印根節點的值至此我們可以打印出根節點的值，也可以打印出樹t的左子樹節點，也可以打印出樹t的右子樹節點，如果我問你既然這些問題都解決了，那麼該如何實現search_tree()這個函式？
如果你不知道，那麼就該我說這句話了：很簡單啊有沒有，不就是把上面幾行程式碼寫在一起嘛
void search_tree(struct tree* t) { printf("%d ", t->value); // 列印根節點的值 seartch_tree(t->left); // 列印樹t的左子樹 search_tree(t->right); // 列印樹t的右子樹}是不是很簡單，是不是很easy，驚喜不驚喜，意外不意外，我們在僅僅只靠給出函式定義並憑藉豐富想象的情況下就把這個函式給實現了 :)
上述程式碼完美符合之前定義的規則。
當然我們需要對特殊情況進行處理，如果給定的一棵樹為空，那麼直接返回，最終程式碼就是：
void search_tree(struct tree* t) { if (t == NULL） // 如果是一顆空樹則直接返回 return; printf("%d ", t->value); // 列印根節點的值 seartch_tree(t->left); // 列印樹t的左子樹 search_tree(t->right); // 列印樹t的右子樹}有的同學可能會一臉懵逼，這個函式就這樣實現了？正確嗎，不用懷疑，這段程式碼無比正確，你可以自己構造一棵樹並試著執行一下這段程式碼。
上述程式碼就是樹的遞迴遍歷。
我知道這些一臉懵逼的同學心裡的怎麼想的，這段程式碼看上去確實正確，執行起來也正確，那麼這段程式碼的執行過程是什麼樣的呢？
遞迴呼叫過程假設有這樣一段程式碼：
void C() {}void A() { B();}void main() { A();}A()會呼叫B()，B()會呼叫C()，那麼函式呼叫過程如圖所示：
實際上每一個函式被呼叫時都有對應的一段記憶體，這段記憶體中儲存了呼叫該函式時傳入的引數以及函式中定義的區域性變數，這段記憶體被稱為函式幀，函式的呼叫過程具有資料結構中棧的性質，也就是先進後出，比如當函式C()執行完畢後該函式對應的函式幀釋放並回到函式B，函式B執行完畢後對應的函式幀被釋放並回到函式A。
有了上述知識我們就可以看一下樹的遞迴呼叫函式是如何執行的了。為簡單起見，我們給定一顆比較簡單的樹：
當在該樹上呼叫search_tree函式時整個遞迴呼叫過程是怎樣的呢，如圖所示：
首先在根節點1上呼叫search_tree()，當列印完當前節點的值後在1的左子樹節點上呼叫search_tree，這時第二個函式幀入棧；列印完當前節點的值(2)後在2的左子樹上呼叫search_tree，這樣第三個函式幀入棧；同樣是列印完當前節點的值後(3)在3的左子樹上呼叫search_tree，第四個函式幀入棧；由於3的左子樹為空，因此第四個函式幀執行第一句時就會退出，因此我們又來到了第三個函式幀，此時節點3的左子樹遍歷完畢，因此開始在3的右子樹節點上呼叫search_tree，接下來的過程如圖所示：
這個過程會一直持續直到節點1的右子樹也遍歷完畢後整個遞迴呼叫過程執行完畢。注意，函式幀中實際上不會包含程式碼，這裡為方便觀察search_tree的遞迴呼叫過程才加上去的。上圖中沒有將整個呼叫過程全部展示出來，大家可以自行推導節點5和節點6是如何遍歷的。
從這個過程中我們可以看到，函式的遞迴呼叫其實沒什麼神秘的，和普通函式呼叫其實是一樣的，只不過遞迴函式的特殊之處在於呼叫的不是其它函式而是本身。
從上面的函式呼叫過程可以得出一個重要的結論，那就是遞迴函式不會一直呼叫下去，否則就是棧溢位了，即著名的Stack Overflow，那麼遞迴函式呼叫棧在什麼情況下就不再增長了呢，在這個例子中就是當給定的樹已經為空時遞迴函式呼叫棧將不再增長，因此對於遞迴函式我們必須指明在什麼情況下遞迴函式將直接返回，也就是常說的遞迴函式的出口。
遞迴實現樹的三種遍歷方法到目前為止，我們已經知道了該如何遍歷樹、如何用程式碼實現以及程式碼的呼叫過程，注意列印語句的位置：
printf("%d ", t->value); // 列印根節點的值seartch_tree(t->left); // 列印樹t的左子樹search_tree(t->right); // 列印樹t的右子樹中序和後序遍歷都可以很容易的用遞迴遍歷方法來實現，如下為中序遍歷：
void search_in_order(struct tree* t) { if (t == NULL） // 如果是一顆空樹則直接返回 return; search_in_order(t->left); // 列印樹t的左子樹 printf("%d ", t->value); // 列印根節點的值 search_in_order(t->right); // 列印樹t的右子樹}後序遍歷則為：
void search_post_order(struct tree* t) { if (t == NULL） // 如果是一顆空樹則直接返回 return; search_in_order(t->left); // 列印樹t的左子樹 search_in_order(t->right); // 列印樹t的右子樹 printf("%d ", t->value); // 列印根節點的值}至此，有的同學可能會覺得樹的遍歷簡直是太簡單了，那麼如果讓你用非遞迴的方式來實現樹的遍歷你該怎麼實現呢？
在閱讀下面的內容之前請確保你已經真正理解了前幾節的內容。
如果你還是不能徹底理解請再多仔細閱讀幾遍。
如何將遞迴轉為非遞迴雖然遞迴實現簡單，但是遞迴函式有自己特定的問題，比如遞迴呼叫會耗費很多的棧空間，也就是記憶體，同時該過程較為耗時，因此其效能通常不及非遞迴版本。
那麼我們該如何實現非遞迴的遍歷樹呢？
要解決這個問題，我們必須清楚的理解遞迴函式的呼叫過程。
從遞迴函式的呼叫過程可以看出，遞迴呼叫無非就是函式幀入棧出棧的過程，因此我們可以直接使用棧來模擬這個過程，只不過棧中儲存的不是函式而是樹節點。
確定用棧來模擬遞迴呼叫這一點後，接下來我們就必須明確兩件事：
什麼情況下入棧什麼情況下出棧我們還是以先序遍歷為例來說明。
仔細觀察遞迴呼叫的過程，我們會發現這樣的規律：
不管三七二十一先把從根節點開始的所有左子樹節點放入棧中檢視棧頂元素，如果棧頂元素有右子樹那麼右子樹入棧並以右子樹為新的根節點重複過程1直到棧空為止現在我們可以回答這兩個問題了。
什麼情況下入棧？
最開始時先把從根節點開始的所有左子樹節點放入棧中，第二步中如果棧頂有右子樹那麼重複過程1，這兩種情況下會入棧。
那麼什麼情況下出棧呢？
當檢視棧頂元素時實際上我們就可以直接pop掉棧頂元素了，這是和遞迴呼叫不同的一點，為什麼呢？因為檢視棧頂節點時我們可以確定一點事，那就是當前節點的左子樹一定已經處理完畢了，因此對於棧頂元素來說我們需要的僅僅是其右子樹的資訊，拿到右子樹資訊後棧頂節點就可以pop掉了。
因此上面的描述用程式碼來表示就是：
void search(tree* root) { if(root == NULL) return ; stack<tree*>s; // 不管三七二十一先把從根節點開始的所有左子樹節點放入棧中 while(root){ s.push(root); root=root->left; } while(!s.empty()){ // 檢視棧頂元素，如果棧頂元素有右子樹那麼右子樹入棧並重復過程1直到棧空為止 tree* top = s.top(); tree* t = top->right; s.pop(); while(t){ s.push(t); t = t->left; } } return r;}上述程式碼是實現樹的三種非遞迴遍歷的基礎，請務必理解。
接下來就可以實現樹的三種非遞迴遍歷了。
實現二叉樹的非遞迴遍歷有的同學可能已經注意到了，上一節中的程式碼中沒有printf語句，如果讓你利用上面的程式碼以先序遍歷方式列印節點該怎麼實現呢？如果你真的已經理解了上述程式碼那麼就非常簡單了，對於先序遍歷來說，我們只需要在節點入棧之前打印出來就可以了：
void search_pre_order(tree* root) { if(root == NULL) return ; stack<tree*>s; // 不管三七二十一先把從根節點開始的所有左子樹節點放入棧中 while(root){ printf("%d ", root->value); // 節點入棧前列印 s.push(root); root=root->left; } while(!s.empty()){ // 檢視棧頂元素，如果棧頂元素有右子樹那麼右子樹入棧並重復過程1直到棧空為止 tree* top = s.top(); tree* t = top->right; s.pop(); while(t){ printf("%d ", root->value); // 節點入棧前列印 s.push(t); t = t->left; } } return r;}那麼對於中序遍歷呢？實際上也非常簡單，我們只需要在節點pop時列印就可以了：
void search_in_order(tree* root) { if(root == NULL) return ; stack<tree*>s; // 不管三七二十一先把從根節點開始的所有左子樹節點放入棧中 while(root){ s.push(root); root=root->left; } while(!s.empty()){ // 檢視棧頂元素，如果棧頂元素有右子樹那麼右子樹入棧並重復過程1直到棧空為止 tree* top = s.top(); printf("%d ", top->value); // 節點pop時列印 tree* t = top->right; s.pop(); while(t){ s.push(t); t = t->left; } } return r;}對於後續遍歷呢？
後續遍歷相對複雜，原因就在於出棧的情況不一樣了。
在先序和中序遍歷過程中，只要左子樹處理完畢實際上棧頂元素就可以出棧了，但是後續遍歷情況不同，什麼是後續遍歷？只有左子樹和右子樹都遍歷完畢才可以處理當前節點，這是後續遍歷，那麼我們該如何知道當前節點的左子樹和右子樹都處理完了呢？
顯然我們需要某種方法記錄下遍歷的過程，實際上我們只需要記錄下遍歷的前一個節點就足夠了。
如果我們知道了遍歷過程中的前一個節點，那麼我們就可以做如下判斷了：
如果前一個節點是當前節點的右子樹，那麼說明右子樹遍歷完畢可以pop瞭如果前一個節點是當前節點的左子樹而且當前節點右子樹為空，那麼說明可以pop瞭如果當前節點的左子樹和右子樹都為空，也就是葉子節點那麼說明可以pop了這樣什麼情況下出棧的問題就解決了，如果不符合這些情況就不能出棧。
只需要根據以上分析對程式碼稍加修改就可以了：
void search_post_order(tree* root) { if(root == NULL) return ; stack<tree*>s; TreeNode* last=NULL; // 記錄遍歷的前一個節點 // 不管三七二十一先把從根節點開始的所有左子樹節點放入棧中 while(root){ s.push(root); root=root->left; } while(!s.empty()){ tree* top = s.top(); if (top->left ==NULL && top->right == NULL || // 當前節點為葉子節點 last==top->right || // 前一個節點為當前節點的右子樹 top->right==NULL && last==top->left){ // 前一個節點為當前節點左子樹且右子樹為空 printf("%d ", top->value); // 節點pop時列印 last = top; // 記錄下前一個節點 s.pop(); } else { tree* t = top->right; while(t){ s.push(t); t = t->left; } } } return r;}樹的遞迴遍歷相對簡單且容易理解，但是遞迴呼叫實際上隱藏了相對複雜的遍歷過程，要想以非遞迴的方式來遍歷二叉樹就需要仔細理解遞迴呼叫過程。