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

2、后，需要逐步返回到父節(jié)點(diǎn)訪(fǎng)問(wèn)右節(jié)點(diǎn)，因此必須有一個(gè)措施能夠?qū)?jié)點(diǎn)序列回溯。有兩個(gè)辦法：用棧記憶：在訪(fǎng)問(wèn)途中將依次遇到的節(jié)點(diǎn)保存下來(lái)。由于節(jié)點(diǎn)出現(xiàn)次序與恢復(fù)次序是反序的，因此是一個(gè)先進(jìn)后出結(jié)構(gòu)，需要用棧。使用棧記憶的實(shí)現(xiàn)有兩個(gè)版本。第一個(gè)版本是模擬遞歸的實(shí)現(xiàn)效果，跟LX討論的，第二個(gè)版本是直接模擬遞歸。節(jié)點(diǎn)增加指向父節(jié)點(diǎn)的指針：通過(guò)指向父節(jié)點(diǎn)的指針來(lái)回溯(后來(lái)發(fā)現(xiàn)還要需要增加一個(gè)訪(fǎng)問(wèn)標(biāo)志，來(lái)指示節(jié)點(diǎn)是否已經(jīng)被訪(fǎng)問(wèn)，不知道可不可以不用標(biāo)志直接實(shí)現(xiàn)回溯？想了一下，如果不用這個(gè)標(biāo)志位，回溯的過(guò)程會(huì)繁瑣很多。暫時(shí)沒(méi)有更好的辦法。)(還有其他辦法可以回溯么？)這3個(gè)算法偽代碼如下，沒(méi)有測(cè)試過(guò)。先序遍歷偽代

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

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

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

6、=NULL&!root-left-bVisited)/訪(fǎng)問(wèn)左子樹(shù)root=root-left;elseif(root-right!=NULL&!root-right-bVisited)/訪(fǎng)問(wèn)右子樹(shù)root=root-right;else/回溯root=root-parent;preOrder3的關(guān)鍵在于回溯。為了回溯增加指向父親節(jié)點(diǎn)的指針，以及是否已經(jīng)訪(fǎng)問(wèn)的標(biāo)志位，對(duì)比preOrderl與preOrder2，但增加的空間復(fù)雜度為0(n)。時(shí)間方面，每個(gè)節(jié)點(diǎn)被訪(fǎng)問(wèn)一次。但是，當(dāng)由葉子節(jié)點(diǎn)跳到下一個(gè)要訪(fǎng)問(wèn)的節(jié)點(diǎn)時(shí)，需要先回溯至父親節(jié)點(diǎn)，再判斷是否存在沒(méi)有被訪(fǎng)問(wèn)過(guò)的右子樹(shù)，如果沒(méi)有，則繼續(xù)回溯，直至

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

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

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

10、e-right!=NULL)node-right-bPushed=false;/左右子樹(shù)均設(shè)置為falseS.push(node-right);node-bPushed=true;/根節(jié)點(diǎn)標(biāo)志位為trueS.push(node);if(node-left!=NULL)node-left-bPushed=false;S.push(node-left);對(duì)比先序遍歷，這個(gè)算法需要額外的增加0(n)的標(biāo)志位空間。另外，棧空間也擴(kuò)大，因?yàn)槊看螇簵５臅r(shí)候都?jí)喝敫?jié)點(diǎn)與左右節(jié)點(diǎn)，因此棧空間為0(n)。時(shí)間復(fù)雜度方面，每個(gè)節(jié)點(diǎn)壓棧兩次，作為子節(jié)點(diǎn)壓棧一次，作為根節(jié)點(diǎn)壓棧一次，彈棧也是兩次。因此無(wú)論從哪個(gè)方面

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

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

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

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