1、二叉樹非遞歸遍歷收藏先序遍歷從遞歸說起voidpreOrder(TNode*root)if(root!=NULL)Visit(root);preOrder(root-left);preOrder(root-right);遞歸算法非常的簡單。先訪問跟節點，然后訪問左節點，再訪問右節點。如果不用遞歸，那該怎么做呢？仔細看一下遞歸程序，就會發現，其實每次都是走樹的左分支(left),直到左子樹為空，然后開始從遞歸的最深處返回，然后開始恢復遞歸現場，訪問右子樹。其實過程很簡單：一直往左走root-left-left-left-null，由于是先序遍歷，因此一遇到節點，便需要立即訪問；由于一直走到最左邊

2、后，需要逐步返回到父節點訪問右節點，因此必須有一個措施能夠對節點序列回溯。有兩個辦法：用棧記憶：在訪問途中將依次遇到的節點保存下來。由于節點出現次序與恢復次序是反序的，因此是一個先進后出結構，需要用棧。使用棧記憶的實現有兩個版本。第一個版本是模擬遞歸的實現效果，跟LX討論的，第二個版本是直接模擬遞歸。節點增加指向父節點的指針：通過指向父節點的指針來回溯(后來發現還要需要增加一個訪問標志，來指示節點是否已經被訪問，不知道可不可以不用標志直接實現回溯？想了一下，如果不用這個標志位，回溯的過程會繁瑣很多。暫時沒有更好的辦法。)(還有其他辦法可以回溯么？)這3個算法偽代碼如下，沒有測試過。先序遍歷偽代

3、碼：非遞歸版本，用棧實現，版本1/先序遍歷偽代碼：非遞歸版本，用棧實現，版本1voidpreOrder1(TNode*root)StackS;while(root!=NULL)|!S.empty()if(root!=NULL)Visit(root);S.push(root);/先序就體現在這里了，先訪問，再入棧root=root-left;/依次訪問左子樹elseroot=S.pop();/回溯至父親節點root=root-right;preOrder1每次都將遇到的節點壓入棧，當左子樹遍歷完畢后才從棧中彈出最后一個訪問的節點，訪問其右子樹。在同一層中，不可能同時有兩個節點壓入棧，因此棧的大小

4、空間為0(h),h為二叉樹高度。時間方面，每個節點都被壓入棧一次，彈出棧一次，訪問一次，復雜度為O(n)先序遍歷偽代碼：非遞歸版本，用棧實現，版本2/先序遍歷偽代碼：非遞歸版本，用棧實現，版本2voidpre0rder2(TNode*root)if(root!=NULL)StackS;S.push(root);while(!S.empty()TNode*node=S.pop();Visit(node);/先訪問根節點，然后根節點就無需入棧了S.push(node-right);/先push的是右節點，再是左節點S.push(node-left);pre0rder2每次將節點壓入棧，然后彈出，壓

5、右子樹，再壓入左子樹，在遍歷過程中，遍歷序列的右節點依次被存入棧，左節點逐次被訪問。同一時刻，棧中元素為m-1個右節點和1個最左節點，最高為h。所以空間也為0(h)；每個節點同樣被壓棧一次，彈棧一次，訪問一次，時間復雜度0(n)先序遍歷偽代碼：非遞歸版本，不用棧，增加指向父節點的指針/先序遍歷偽代碼：非遞歸版本，不用棧，增加指向父節點的指針voidpre0rder3(TNode*root)while(root!=NULL)/回溯到根節點時為NULL，退出if(!root-bVisited)/判定是否已被訪問Visit(root);root-bVisited=true;if(root-left!

6、=NULL&!root-left-bVisited)/訪問左子樹root=root-left;elseif(root-right!=NULL&!root-right-bVisited)/訪問右子樹root=root-right;else/回溯root=root-parent;preOrder3的關鍵在于回溯。為了回溯增加指向父親節點的指針，以及是否已經訪問的標志位，對比preOrderl與preOrder2，但增加的空間復雜度為0(n)。時間方面，每個節點被訪問一次。但是，當由葉子節點跳到下一個要訪問的節點時，需要先回溯至父親節點，再判斷是否存在沒有被訪問過的右子樹，如果沒有，則繼續回溯，直至

7、找到一顆沒有被訪問過的右子樹，這個過程需要很多的時間。每個葉子節點的回溯需要0(h)時間復雜度，葉子節點最多為(2人(h-1),因此回溯花費的上限為0(h*(2人(h-1)。這個上限應該可以縮小。preOrder3唯一的好處是不需要額外的數據結構-棧。中序遍歷根據上面的先序遍歷，可以類似的構造出中序遍歷的三種方式。仔細想一下，只有第一種方法改過來時最方便的。需要的改動僅僅調換一下節點訪問的次序，先序是先訪問，再入棧；而中序則是先入棧，彈棧后再訪問。偽代碼如下。時間復雜度與空間復雜度同先序一致。/中序遍歷偽代碼：非遞歸版本，用棧實現，版本1voidInOrder1(TNode*root)Stac

8、kS;while(root!=NULL|!S.empty()while(root!=NULL)/左子樹入棧S.push(root);root=root-left;if(!S.empty()root=S.pop();Visit(root-data);/訪問根結點root=root-right;/通過下一次循環實現右子樹遍歷第二個用棧的版本卻并不樂觀。preOrder2能夠很好的執行的原因是，將左右節點壓入棧后，根節點就再也用不著了；而中序和后序卻不一樣，左右節點入棧后，根節點后面還需要訪問。因此三個節點都要入棧，而且入棧的先后順序必須為：右節點，根節點，左節點。但是，當入棧以后，根節點與其左右子

9、樹的節點就分不清楚了。因此必須引入一個標志位，表示是否已經將該節點的左右子樹入棧了。每次入棧時，根節點標志位為true,左右子樹標志位為false。偽代碼如下：/中序遍歷偽代碼：非遞歸版本，用棧實現，版本2voidInOrder2(TNode*root)StackS;if(root!=NULL)S.push(root);while(!S.empty()TNode*node=S.pop();if(node-bPushed)/如果標識位為true,則表示其左右子樹都已經入棧，那么現在就需要訪問該節點了Visit(node);else/左右子樹尚未入棧，則依次將右節點，根節點，左節點入棧if(nod

10、e-right!=NULL)node-right-bPushed=false;/左右子樹均設置為falseS.push(node-right);node-bPushed=true;/根節點標志位為trueS.push(node);if(node-left!=NULL)node-left-bPushed=false;S.push(node-left);對比先序遍歷，這個算法需要額外的增加0(n)的標志位空間。另外，棧空間也擴大，因為每次壓棧的時候都壓入根節點與左右節點，因此棧空間為0(n)。時間復雜度方面，每個節點壓棧兩次，作為子節點壓棧一次，作為根節點壓棧一次，彈棧也是兩次。因此無論從哪個方面

11、講，這個方法效率都不及In0rder1。至于不用棧來實現中序遍歷。頭暈了，暫時不想了。后面再來完善。還有后序遍歷，貌似更復雜。對了，還有個層序遍歷。再寫一篇吧。頭都大了。9.8續中序遍歷的第三個非遞歸版本：采用指向父節點的指針回溯。這個與先序遍歷是非常類似的，不同之處在于，先序遍歷只要一遇到節點，那么沒有被訪問那么立即訪問，訪問完畢后嘗試向左走，如果左孩子補課訪問，則嘗試右邊走，如果左右皆不可訪問，則回溯；中序遍歷是先嘗試向左走，一直到左邊不通后訪問當前節點，然后嘗試向右走，右邊不通，則回溯。(這里不通的意思是：節點不為空，且沒有被訪問過)/中序遍歷偽代碼：非遞歸版本，不用棧，增加指向父節點的

12、指針voidIn0rder3(TNode*root)while(root!=NULL)/回溯到根節點時為NULL，退出while(root-left!=NULL&!root-left-bVisited)/沿左子樹向下搜索當前子樹尚未訪問的最左節點root=root-left;if(!root-bVisited)/訪問尚未訪問的最左節點Visit(root);root-bVisited=true;if(root-right!=NULL&!root-right-bVisited)/遍歷當前節點的右子樹root=root-right;else/回溯至父節點root=root-parent;這個算法時

13、間復雜度與空間復雜度與第3個先序遍歷的版本是一樣的。后序遍歷從直覺上來說，后序遍歷對比中序遍歷難度要增大很多。因為中序遍歷節點序列有一點的連續性，而后續遍歷則感覺有一定的跳躍性。先左，再右，最后才中間節點；訪問左子樹后，需要跳轉到右子樹，右子樹訪問完畢了再回溯至根節點并訪問之。這種序列的不連續造成實現前面先序與中序類似的第1個與第3個版本比較困難。但是按照第2個思想，直接來模擬遞歸還是非常容易的。如下：/后序遍歷偽代碼：非遞歸版本，用棧實現voidPostOrder(TNode*root)StackS;if(root!=NULL)S.push(root);while(!S.empty()TNo

14、de*node=S.pop();if(node-bPushed)/如果標識位為true,則表示其左右子樹都已經入棧，那么現在就需要訪問該節點了Visit(node);else/左右子樹尚未入棧，則依次將右節點,左節點,根節點入棧if(node-right!=NULL)node-right-bPushed=false;/左右子樹均設置為falseS.push(node-right);if(node-left!=NULL)node-left-bPushed=false;S.push(node-left);node-bPushed=true;/根節點標志位為trueS.push(node);和中序遍歷的第2個版本比較，僅僅只是把左孩子入棧和根節點入棧順序調換一下；這種差別就跟遞歸版本的中序與后序一樣。層序遍歷這個很簡單，就不說老。/層序遍歷偽代碼：非遞歸版本，用隊列完成voidLevelOrder(TNode*root)QueueQ;Q.push(root);whil