這篇文章給大家分享的是有關(guān)C語言數(shù)據(jù)結(jié)構(gòu)之二叉樹的非遞歸后序遍歷算法怎么用的內(nèi)容。小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過來看看吧。

創(chuàng)新互聯(lián)是專業(yè)的臨沂網(wǎng)站建設(shè)公司，臨沂接單;提供網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè),網(wǎng)頁設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行臨沂網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!

C語言數(shù)據(jù)結(jié)構(gòu)之二叉樹的非遞歸后序遍歷算法

前言：

前序、中序、后序的非遞歸遍歷中，要數(shù)后序最為麻煩，如果只在棧中保留指向結(jié)點(diǎn)的指針，那是不夠的，必須有一些額外的信息存放在棧中。

方法有很多，這里只舉一種，先定義棧結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)

typedef struct{Node * p; int rvisited;}SNode //Node 是二叉樹的結(jié)點(diǎn)結(jié)構(gòu)，rvisited==1代表p所指向的結(jié)點(diǎn)的右結(jié)點(diǎn)已被訪問過。

lastOrderTraverse(BiTree bt){
　　//首先，從根節(jié)點(diǎn)開始，往左下方走，一直走到頭，將路徑上的每一個(gè)結(jié)點(diǎn)入棧。
　　p = bt;
　　while(bt){
　　　　push(bt, 0); //push到棧中兩個(gè)信息，一是結(jié)點(diǎn)指針，一是其右結(jié)點(diǎn)是否被訪問過
　　　　bt = bt.lchild;
　　}

　　//然后進(jìn)入循環(huán)體
　　while(!Stack.empty()){ //只要棧非空
　　　　sn = Stack.getTop(); // sn是棧頂結(jié)點(diǎn)

　　　　//注意，任意一個(gè)結(jié)點(diǎn)N，只要他有左孩子，則在N入棧之后，N的左孩子必然也跟著入棧了(這個(gè)體現(xiàn)在算法的后半部分)，所以當(dāng)我們拿到棧頂元素的時(shí)候，可以確信這個(gè)元素要么沒有左孩子，要么其左孩子已經(jīng)被訪問過，所以此時(shí)我們就不關(guān)心它的左孩子了，我們只關(guān)心其右孩子。

　　　　//若其右孩子已經(jīng)被訪問過，或是該元素沒有右孩子，則由后序遍歷的定義，此時(shí)可以visit這個(gè)結(jié)點(diǎn)了。
　　　　if(!sn.p.rchild || sn.rvisited){
　　　　　　p = pop();
　　　　　　visit(p);
　　　　}
　　　　else //若它的右孩子存在且rvisited為0，說明以前還沒有動(dòng)過它的右孩子，于是就去處理一下其右孩子。
　　　　{ 
　　　　　　//此時(shí)我們要從其右孩子結(jié)點(diǎn)開始一直往左下方走，直至走到盡頭，將這條路徑上的所有結(jié)點(diǎn)都入棧。

　　　　　　//當(dāng)然，入棧之前要先將該結(jié)點(diǎn)的rvisited設(shè)成1，因?yàn)槠溆液⒆拥娜霔Ｒ馕吨挠液⒆颖貙⑾扔谒辉L問(這很好理解，因?yàn)槲覀兛偸菑臈ｍ斎〕鲈貋磉M(jìn)行visit)。由此可知，下一次該元素再處于棧頂時(shí)，其右孩子必然已被visit過了，所以此處可以將rvisited設(shè)置為1。
　　　　　　sn.rvisited = 1;

　　　　　　//往左下方走到盡頭，將路徑上所有元素入棧
　　　　　　p = sn.p.rchild;
　　　　　　while(p != 0){
　　　　　　　　push(p, 0);
　　　　　　　　p = p.lchild;
　　　　　　}
　　　　}//這一輪循環(huán)已結(jié)束，剛剛?cè)霔５哪切┙Y(jié)點(diǎn)我們不必管它了，下一輪循環(huán)會(huì)將這些結(jié)點(diǎn)照顧的很好。
　　}
}

感謝各位的閱讀！關(guān)于“C語言數(shù)據(jù)結(jié)構(gòu)之二叉樹的非遞歸后序遍歷算法怎么用”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！