遞歸非遞歸兩種算法遍歷二叉樹

1、一、設(shè)計思想1 .用遞歸算法遍歷設(shè)計思想：主要是通過不同程序順序，從而實現(xiàn)遞歸的順序遍歷前序遍歷：先判斷節(jié)點是否為空，如果不為空，則輸出。再判斷左節(jié)點是否為空，如 果不為空，則遞歸調(diào)用，直到遍歷到最左邊。接著再遍歷最左邊的右子樹，如果此時右子 樹不為空，則遞歸遍歷左子樹的操作，直到遍歷到葉子節(jié)點。如果右子樹為空，則回溯上 次的遞歸調(diào)用，重復輸出和遍歷右子樹的操作。中序遍歷：先遍歷左節(jié)點是否為空，如果不為空，則遞歸調(diào)用，直到遍歷到最左邊或者葉子節(jié)點，然后輸出，接著再遍歷最左邊的右子樹，如果此時右子樹不為空，則遞歸 重復遍歷左子樹的操作， 直到遍歷到葉子節(jié)點。 如果右子樹為空，則回溯到上次遞歸調(diào)用

2、, 重復輸出和遍歷右子樹的操作。后序遍歷：先判斷左節(jié)點是否為空，如果不為空則一直遞歸直到遍歷到最左邊，然后 遍歷右節(jié)點，再接著遍歷到左子樹的最右邊，直到遍歷到葉子節(jié)點。此時輸出，回溯到上 次遞歸，繼續(xù)執(zhí)行后面的操作，重復，直到將整個樹遍歷完畢。2 .用非遞歸算法遍歷設(shè)計思想：主要是通過棧的存取，判空，從而實現(xiàn)樹的遍歷前序遍歷：通過一個循環(huán)實現(xiàn)。先輸出節(jié)點的數(shù)值，因為棧的特性，則需要先判斷右 子樹是否為空，如果不為空，則將右子樹壓棧。然后判斷左子樹是否為空，如果不為空， 則將左子樹壓棧。接著再將棧里面的子樹彈出賦給給當前節(jié)點變量，重復上述操作，直到 棧為空后退出循環(huán)。中序遍歷：通過循環(huán)實現(xiàn)。將樹

3、一直遍歷到最左端，并將中間所經(jīng)過的節(jié)點保存在棧 中，當遍歷到最左邊的時候，則彈出棧里面的子樹。輸出數(shù)值，將當前節(jié)點賦值為當前節(jié) 點的右子樹，遍歷右子樹，即重復上述操作，直到當前節(jié)點為空，并且棧內(nèi)元素為0。后序遍歷：通過循環(huán)和標記棧實現(xiàn)。將數(shù)一直遍歷到最左端，并將中間的節(jié)點保存在 樹棧中，同時同步的添加一個標記棧。當遍歷到最左邊的時候，彈棧并賦值給當前棧，然 后判斷標記棧的數(shù)值，如果數(shù)值為0的話則代表當前樹沒有遍歷過，遍歷右子樹。然后重復上面的操作，如果數(shù)值為 1的話則代表此時數(shù)已經(jīng)遍歷過了，可以開始輸出了，為了避 免重復輸出，將當前棧賦為空。重復循環(huán)操作，直到棧內(nèi)沒有元素，且當前節(jié)點為空（因

4、為一直左的操作并沒有將右子樹壓棧）。、算法流程圖圖1遞歸算法-先序遍歷遞歸算法-中序遍歷圖2遞歸算法-后序遍歷圖3圖4非遞歸算法-先序遍歷圖5非遞歸算法-中序遍歷Output圖6非遞歸算法-后序遍歷三、源代碼#include<stdio.h>#include<stdlib.h>typedef char ElemType;/定義樹結(jié)構(gòu)typedef struct treeElemType data;struct tree * Ichild;struct tree * rchild;unsigned int isOut; 專為后序遍歷設(shè)置的，0為不需要被輸出，1為需要被輸出

5、TreeNode, *Tree;/定義棧結(jié)構(gòu)typedef struct stackTree * base;Tree * top;int stacksize;SqStack;void InitStack( SqStack &s );void Push( SqStack &s, Tree e );void GetTop( SqStack s, Tree &e );void Pop( SqStack &s, Tree &e );int StackEmpty( SqStack s );void CreateTree(Tree &t);void PreO

6、rder(Tree t);void PreOrder1(Tree t);void InOrder(Tree t);void InOrder1(Tree t);void PostOrder(Tree t);void PostOrder1(Tree t);int main()Tree T;printf("n按先序序列輸入結(jié)點序列，'*代表空：");CreateTree(T);printf("n遞歸先序遍歷的結(jié)果：");PreOrder(T);printf("n非遞歸先序遍歷的結(jié)果：");PreOrderl(T);printf(&q

7、uot;n遞歸中序遍歷的結(jié)果：");InOrder(T);printf("n非遞歸中序遍歷的結(jié)果：");InOrderl(T);printf("n遞歸后序遍歷的結(jié)果：")；PostOrder(T);printf("n非遞歸后序遍歷的結(jié)果：");PostOrderl(T);printf("n");return 0;void InitStack( SqStack &s ) /初始化棧s.base = (Tree *)malloc(100*sizeof(Tree);if ( !s.base ) prin

8、tf("InitStack 內(nèi)存分配出錯，程序?qū)⑼瞥鰣?zhí)行！n");exit (-1);s.top = s.base;s.stacksize = 100;void Push (SqStack &s, Tree e ) / 元素入棧 接收一個stack類型變量和一個tree*類型變量if ( s.top - s.base >= s.stacksize )s.base = (Tree *)realloc(s.base,(s.stacksize+20)*sizeof(Tree);if ( !s.base ) printf("Push 內(nèi)存分配出錯，程序?qū)⑼顺?/p>

9、執(zhí)行n");exit (-1); s.top = s.base + s.stacksize;/s.stacksize += 20;e->isOut = 0;*s.top+ = e;/獲得棧頂元素 void GetTop( SqStack s, Tree &e )e = *(s.top - 1); /s.top為 tree*類型void Pop( SqStack &s, Tree &e )出棧if ( s.top = s.base )printf("棧為空 n");return ;e = *(-s.top);int StackEmpty

10、( SqStack s )/ 判斷棧是否為空if ( s.top = s.base )return 1;return 0;void CreateTree(Tree &t)/以先序序列建立樹char ch;scanf("%c",&ch); if ( ch = '*')t = NULL; else t = (Tree)malloc(sizeof(TreeNode);if ( !t )printf(" 分配內(nèi)存出錯！");return ;t->data = ch;CreateTree(t->lchild);Creat

11、eTree(t->rchild);遞歸先序遍歷，遍歷順序：根、左、右void PreOrder(Tree t) / /先訪問根節(jié)點，再先序遍歷左子樹，再先序遍歷右子樹if ( t )/如果樹t不為空樹，才繼續(xù)執(zhí)行先序遍歷printf("%c ”,t->data);PreOrder(t->lchild);PreOrder(t->rchild);void InOrder(Tree t) /遞歸中序遍歷，遍歷順序：左、中、右/先中序遍歷左子樹，再訪問根節(jié)點，再中序遍歷右節(jié)點if ( t ) /如果樹t為空樹，則停止向下遍歷InOrder(t->lchild);

12、printf("%c ",t->data);InOrder(t->rchild);void PostOrder(Tree t) /遞歸后序遍歷，遍歷順序：左、右、根if ( t ) PostOrder(t->lchild);PostOrder(t->rchild);printf("%c ",t->data); void PreOrder1(Tree t)非遞歸先序遍歷Tree p = t;/p 為 tree*類型變量SqStack s;InitStack(s);while ( p | !StackEmpty(s) ) /當樹

13、的節(jié)點不為空 或 棧不為空執(zhí)行循環(huán)if ( p ) /當數(shù)的此節(jié)點不為空時，打印此節(jié)點值且將此節(jié)點入棧printf("%c ”,p->data);Push(s,p);p = p->lchild; else /否則父節(jié)點出棧，p指向父節(jié)點的右子樹Pop(s,P)； p = p->rchild;void InOrder1(Tree t) / 非遞歸中序遍歷Tree p = t;SqStack s;InitStack(s);while ( p | !StackEmpty(s) if ( p )Push(s,p);p = p->lchild; elsePoP(s,P)

14、；printf("%c ”,p->data);p = p->rchild; void PostOrder1(Tree t) /非遞歸后序遍歷，遍歷順序：左、右、根t->isOut = 0;/初始值表示不輸出Tree p = t;SqStack s;InitStack(s);while ( p | !StackEmpty(s) ) /節(jié)點非空 或 棧非空執(zhí)行循環(huán)if ( P )if ( p->isOut )/左右子樹都已輸出，則該節(jié)點也輸出Pop(s,p);printf("%c ”,p->data);if (!StackEmpty(s)GetTo

15、p(s,p); /得到該節(jié)點元素的父節(jié)點elsep = NULL; elseif ( (p->lchild) && (p->lchild->isOut = 1)/如果存在左子樹，并且左子樹已經(jīng)遍歷完，則說明該節(jié)點已經(jīng)入棧p->isOut = 1;p = p->rchild;else /否則入棧該節(jié)點的樹，并且走向它的左子樹Push(s,p);p = p->lchild;elseGetTop(s,p);if ( p->rchild )p = p->rchild;elsePoP(s,P)；printf("%c ”,p->

16、;data);p->isOut = 1;if (!StackEmpty(s) GetTop(s,p);if ( p->lchild = NULL ) p->isOut = 1; /右子樹已輸出，將父節(jié)點 isOut置1 elsep = NULL;四、運行結(jié)果1 , 'lj：,DebugZf21.eKe'按先序序列輸入結(jié)點序列，代表空，123*45*6*7*89*遞歸先序遍歷的結(jié)果：1 2 3 4 5 6 7 8 9非遞婦先序遍歷的結(jié)果：123456780遞歸中序遍歷的結(jié)果：325461798非遞歸中序遍歷的結(jié)果；3 2 5 4 6 1 7 9 8遞歸后序遍歷的

17、結(jié)果 3 5 6 4 2 9 8 7 1非遞歸后序遍歷的結(jié)果：356429871Press any key to continue.圖7遍歷二叉樹運行結(jié)果圖五、遇到的問題及解決這部分我主要遇到了如下三個問題，其內(nèi)容與解決方法如下所列： 第一個問題：遞歸的使用，沒有完全理解遞歸的含義描述：遞歸的使用是每次都將上次調(diào)用的現(xiàn)場保留，直到本次的方法的完成才會返回 上次的調(diào)用的現(xiàn)場，由于沒有完全的了解， 所以在調(diào)用的時候回忽略掉上次保存的現(xiàn)場。解決：通過例子來解決分析，每次將遞歸調(diào)用的現(xiàn)場都記錄下來，然后再進行下次遞 歸，從而避免了忽略掉的現(xiàn)場，得到錯誤的思想。第二個問題：非遞歸如何實現(xiàn)遍歷描述：對于非

18、遞歸，我們不能像遞歸一樣能保存中間的現(xiàn)場，而如果不能保存上次樹 則不能調(diào)用當前樹的下下個左子樹或者右子樹，所以我們必須得想出一種新的方法去實現(xiàn) 現(xiàn)場的保存。解決：通過一個棧來保存中間的調(diào)用線程，由于 while循環(huán)也有像遞歸一樣的過程, 所以只要我們將每次調(diào)用的當前樹的保存下來，那么下次調(diào)用的時候直接將棧里面的樹彈 出即可訪問上一次的保存的現(xiàn)場的樹。第三個問題：對于非遞歸后序的實現(xiàn)描述：由于后續(xù)遍歷又本身的特殊性，左子樹，右子樹，中間節(jié)點這樣的一個順序， 如果分開保存左子樹和右子樹，那么在遍歷右子樹后會丟失掉上次現(xiàn)場保留的中間節(jié)點， 如果要像中序遍歷一樣的方法保存的話，那么每次彈出后遍歷右節(jié)點也會丟失上次現(xiàn)場保 留的中間節(jié)點。解決：通過一個標簽的形式，在每次壓棧的時候都給樹標記下，由于都是先訪問左子 樹，再訪問右子樹，也就是說每棵樹都是訪問兩次。那么就可以通過判斷樹的標志而實現(xiàn) 此時是否遍歷左節(jié)點和右節(jié)點完成，從而輸出中間節(jié)點。六、心得體會這次的實驗相對來說不是很復雜，但是有些本質(zhì)上的理論知識沒有深入理解的話，那 么簡單的東西也會變得很復雜，所以說，越是簡單的東西，包含的知識量越多。二叉樹遍歷的實驗，讓我進一步深刻理解了二叉樹創(chuàng)建的