国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 編程 > C++ > 正文

C語言數據結構之二叉樹的非遞歸后序遍歷算法

2020-05-23 13:46:49
字體:
來源:轉載
供稿:網友

C語言數據結構之二叉樹的非遞歸后序遍歷算法

前言:

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

方法有很多,這里只舉一種,先定義棧結點的數據結構

typedef struct{Node * p; int rvisited;}SNode //Node 是二叉樹的結點結構,rvisited==1代表p所指向的結點的右結點已被訪問過。lastOrderTraverse(BiTree bt){  //首先,從根節點開始,往左下方走,一直走到頭,將路徑上的每一個結點入棧。  p = bt;  while(bt){    push(bt, 0); //push到棧中兩個信息,一是結點指針,一是其右結點是否被訪問過    bt = bt.lchild;  }  //然后進入循環體  while(!Stack.empty()){ //只要棧非空    sn = Stack.getTop(); // sn是棧頂結點    //注意,任意一個結點N,只要他有左孩子,則在N入棧之后,N的左孩子必然也跟著入棧了(這個體現在算法的后半部分),所以當我們拿到棧頂元素的時候,可以確信這個元素要么沒有左孩子,要么其左孩子已經被訪問過,所以此時我們就不關心它的左孩子了,我們只關心其右孩子。    //若其右孩子已經被訪問過,或是該元素沒有右孩子,則由后序遍歷的定義,此時可以visit這個結點了。    if(!sn.p.rchild || sn.rvisited){      p = pop();      visit(p);    }    else //若它的右孩子存在且rvisited為0,說明以前還沒有動過它的右孩子,于是就去處理一下其右孩子。    {       //此時我們要從其右孩子結點開始一直往左下方走,直至走到盡頭,將這條路徑上的所有結點都入棧。      //當然,入棧之前要先將該結點的rvisited設成1,因為其右孩子的入棧意味著它的右孩子必將先于它被訪問(這很好理解,因為我們總是從棧頂取出元素來進行visit)。由此可知,下一次該元素再處于棧頂時,其右孩子必然已被visit過了,所以此處可以將rvisited設置為1。      sn.rvisited = 1;      //往左下方走到盡頭,將路徑上所有元素入棧      p = sn.p.rchild;      while(p != 0){        push(p, 0);        p = p.lchild;      }    }//這一輪循環已結束,剛剛入棧的那些結點我們不必管它了,下一輪循環會將這些結點照顧的很好。  }}

如有疑問請留言或者到本站社區交流討論,感謝閱讀,希望能幫助到大家,謝謝大家對本站的支持!


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 华宁县| 碌曲县| 南漳县| 大丰市| 五家渠市| 无极县| 越西县| 盘锦市| 新田县| 昌江| 娄烦县| 巨鹿县| 铜山县| 平潭县| 溧阳市| 拜城县| 延川县| 绥江县| 阜南县| 成安县| 涟源市| 屯留县| 聂拉木县| 蒙自县| 岐山县| 石棉县| 庄河市| 桦甸市| 武冈市| 磴口县| 定远县| 澜沧| 普兰店市| 福建省| 盘锦市| 永顺县| 邵阳市| 桂林市| 自治县| 台东县| 福清市|