C語言數據結構之二叉樹的非遞歸后序遍歷算法
前言：
前序、中序、后序的非遞歸遍歷中，要數后序最為麻煩，如果只在棧中保留指向結點的指針，那是不夠的，必須有一些額外的信息存放在棧中。
方法有很多，這里只舉一種，先定義棧結點的數據結構
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
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; } }//這一輪循環已結束，剛剛入棧的那些結點我們不必管它了，下一輪循環會將這些結點照顧的很好。 }} |
如有疑問請留言或者到本站社區交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
原文鏈接：http://blog.csdn.net/yanzongshuai/article/details/12215867
