什么是二叉樹
在計算機科學中二叉樹，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;
}
總結
樹的遞回遍歷相對簡單且容易理解，但是遞回呼叫實際上隱藏了相對復雜的遍歷程序，要想以非遞回的方式來遍歷二叉樹就需要仔細理解遞回呼叫程序，
寫在最后
歡迎大家關注我的公眾號【風平浪靜如碼】，海量Java相關文章，學習資料都會在里面更新，整理的資料也會放在里面，
覺得寫的還不錯的就點個贊，加個關注唄！點關注，不迷路，持續更新！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/241706.html
標籤：Java
上一篇：【對線面試官】 Java 泛型