萬盛學電腦網

 萬盛學電腦網 >> 腳本專題 >> javascript >> 二叉樹的非遞歸後序遍歷算法案例解析

二叉樹的非遞歸後序遍歷算法案例解析

 這篇文章主要介紹了二叉樹的非遞歸後序遍歷算法實例,需要的朋友可以參考下

前序、中序、後序的非遞歸遍歷中,要數後序最為麻煩,如果只在棧中保留指向結點的指針,那是不夠的,必須有一些額外的信息存放在棧中。 方法有很多,這裡只舉一種,先定義棧結點的數據結構    代碼如下: 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;       }     }//這一輪循環已結束,剛剛入棧的那些結點我們不必管它了,下一輪循環會將這些結點照顧的很好。   } }  
copyright © 萬盛學電腦網 all rights reserved