二叉樹的非遞歸遍歷

4 人贊了文章

題外話：因為做了一個決定，使得最近一直很忙，一堆事情讓自己壓力很大，稍微忙裡偷閒起來就總是胡思亂想。似乎得讓自己忙得沒有一丁點兒空閑，才能不去亂想吧。所以用了一整下午的時間去研究BinaryTree的非遞歸遍歷演算法，雖然還有些問題，但也是很高興啦，分享出來給大家，希望對有同樣迷惑的人能有所幫助吧。

1.二叉樹的3種遍歷：先序、中序、後序遍歷。

2.一個結論：無論是上面那一種遍歷方式，都有相同之處。下面解釋下這一點：先以滿二叉樹為例。

按照上圖中樹外圍的藍色路徑，從根結點A開始，走一圈回到根結點A。走的過程中，第一次遇到某結點，在其旁邊標記一個△，並在記號裡面寫下該結點的值，下同，當第二次遇到此結點時，在其旁邊標記一個□，當第三次再遇到這一結點時，在其旁邊標記一個○。由圖可知，按照這一路徑，便可遍歷二叉樹。只不過，這樣的遍歷是多餘的，因為有些結點重複訪問了。比如，結點A，我先後遇到他3次，同樣地B、C亦訪問了3次，只有葉子結點DEFG僅訪問了一次。現在規定葉子結點我們也訪問3次，即連著訪問3次，得下圖。

現在，我們按藍色路徑走一遍，按順序記錄下△中的字母，可得序列ABDECFG，這個序列，你會發現它就是先序序列。來，我們再走一遍藍色路徑，按順序記錄下□中的字母，可得序列DBEAFCG，即為中序序列。再再走一遍藍色路徑，按順序記錄下○中的字母，可得序列DEBFGCA，即為後序序列，所以「一個結論」，就是說無論先中後那種次序的遍歷，都是按藍色路徑遍歷，只不過這樣遍歷有重複，我們制定了一個次序使得其不重複罷了。

下面按照這個方法，去看看對於非滿二叉樹，有沒有一樣的結論。

對於非滿二叉樹，我們先添加一些虛結點使之成為滿二叉樹，然後按上面說的，在外圍圈一個藍色路徑，從根結點A開始一圈下來回到A，過程中第幾次遇到某結點就在其旁邊標記對應符號。我們可以只有左右孩子健全的結點(如結點A)才能訪問夠3次，不同的是對於添加上去的虛結點就不用訪問了。

確定每個結點都訪問3次之後，走一遍藍色路徑，按順序記錄下△中的字母，可得序列ABDCE，發現就是先序序列。同樣地，可以檢驗中後序也是成立的。

3.根據第2點裡的「一個結論」，我們可以藉助棧來實現非遞歸的遍歷演算法，以先序遍歷為例。

就用上面做過例子的非滿二叉樹來講：

為了方便，使用如下偽代碼

print(A)，表示列印輸出A

push(A)，表示A進棧

pop()，表示出棧

因為懶得弄動圖表示棧元素的變化，所以趕緊拿起筆紙邊看下面這段話邊畫一畫棧吧，當然你腦子夠好，腦補也行哈。

從A開始，即當前結點為A，print(A)push(A)，當前結點改為B，print(B)push(B)，沒有左孩子了，就pop()，出棧結點為B，判斷B有無右孩子，結果是有右孩子D，則print(D)push(D)，沒有左孩子了，就pop()，出棧結點為D，判斷D有無右孩子，結果是沒有且棧不為空，則pop()，出棧結點為A，判斷A有無右孩子，結果是有右孩子C，則print(C)push(C)，當前結點改為E，print(E)push(E)，沒有左孩子了，就pop()，出棧結點是E，判斷E有無右孩子，結果是沒有而且棧為空，遍歷完成。

//Stackconst int maxSize = 100;class Stack{private: int top; BTNode *data[maxSize];public: Stack(); bool StackEmpty(); bool Push(BTNode *b); bool Pop(BTNode *&b);}; Stack::Stack()//棧的初始化 { top = -1; }bool Stack::StackEmpty()//判斷棧是否為空 { return (top == -1); } bool Stack::Push(BTNode *b)//進棧 { if(top == maxSize-1)//上溢出 return 0; top++; data[top] = b; return 1; }bool Stack::Pop(BTNode *&b)//出棧 { if(top == -1)//下溢出 return 0; b = data[top]; top--; return 1;}//BinaryTreetypedef char Elem;struct BTNode{ BTNode* pL;//指向左孩子 Elem data;//數據域 BTNode* pR; //指向右孩子 }; void PreOrder1(BTNode *b)//先序遍歷{ if(b == NULL) return; Stack s; BTNode *p = b; while(1){ while(p){ cout<<p->data; s.Push(p); p = p->pL; } while(1){ s.Pop(p); if(p->pR){ p = p->pR; break; } else if(s.StackEmpty()) return; } }} void InOrder1(BTNode *b)//中序遍歷{ if(b == NULL) return; Stack s; BTNode *p = b; while(1){ while(p){ s.Push(p); p = p->pL; } while(1){ s.Pop(p); cout<<p->data; if(p->pR){ p = p->pR; break; } else if(s.StackEmpty()) return; } }}

4.可能看了第3點，感覺上就是把演算法直接說了一遍，還是不知道如何從第2點中說的「一個結論」得到這一演算法。我也不是很明白這一點，所以下面是我個人的理解，僅作參考，歡迎大家一起交流。

首先我們設置了一個棧，然後我們按藍色路徑走第一次遇到某結點我讓它進棧，再次遇到它就讓它出棧。所以我們要讓我們的代碼起到一個畫藍色路徑的效果。就是先畫最左邊，即代碼里循環做p =p->pL，直到沒有左孩子了，此時無論p有無右孩子，都將是接連兩次訪問p，所以這時應該讓p出棧，然後我們判斷p有無右孩子，如果有，從p->pR開始畫左邊藍色路徑，即回到一開始循環做p=p->pL那裡。否則，沒有有右孩子，那我們將往回畫藍色路徑了，這時候就是再出棧，然後再判斷出棧結點有無右孩子了。回過頭看，為什麼設置了這樣一個棧，因為我們第一次訪問結點先訪問的，在我們往回畫藍色路徑時就肯定是後訪問的，這樣的順序不就是棧嗎？我們畫藍色路徑，每個結點都訪問了3次，而第一次訪問進棧再次訪問出棧，第三次我們不做處理，所以我們可以通過判斷棧是否為空而得知是否遍歷完成。那問題來了，什麼時候去判斷棧是否為空？答案是，當我們要往回畫藍色路徑要pop()時，我們就判斷棧是否為空，如果為空，說明你把訪問了一次的結點都訪問了第二次，說明遍歷完成了。

5.第4點的分析，我們已經知道了第三次訪問我們並不做處理，所以到底怎麼實現後序遍歷呢？這個問題，就留給大家吧

6.可能網上已經有很多類似的文章博客介紹了二叉樹的非遞歸遍歷演算法，可能都要比我寫得好。但是畢竟是自己花時間研究弄懂了的，算作實實在在的收穫吧，各位大神不喜勿噴。