1、精選優(yōu)質文檔-傾情為你奉上數據結構（雙語）項目文檔報告遞歸、非遞歸兩種算法遍歷二叉樹專 業(yè)： 計算機科學與技術 班 級： 指導教師： 蘇亞光 姓 名： 學 號： 目 錄一、設計思想.3頁二、算法流程圖4.頁三、源代碼10頁四、運行結果. 15頁五、遇到的問題及解決15頁六、心得體會16頁一、設計思想1. 遞歸遍歷二叉樹算法思想:1先序遍歷：首先判斷根結點是否為空，為空則停止遍歷，不為空則將左子作為新的根結點重新進行上述判斷，左子遍歷結束后，再將右子作為根結點判斷，直至結束。到達每一個結點時，打印該結點數據，即得先序遍歷結果。若二叉樹非空，則依次進行如下操作：（1）訪問跟結點；（2）前序遍歷左子

2、樹；（3）前序遍歷右子樹。2. 中序遍歷：首先判斷該結點是否為空，為空則結束，不為空則將左子作為根結點再進行判斷，打印左子，然后打印二叉樹的根結點，最后再將右子作為參數進行判斷，打印右子，直至結束。若二叉樹非空，則依次進行如下操作：（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。3. 后續(xù)遍歷：指針到達一個結點時，判斷該結點是否為空，為空則停止遍歷，不為空則將左子作為新的結點參數進行判斷，打印左子。左子判斷完成后，將右子作為結點參數傳入判斷，打印右子。左右子判斷完成后打印根結點。若二叉樹非空，則依次進行如下操作：（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。2.

3、非遞歸遍歷二叉樹算法思想:1. 先序遍歷：建立一個棧，當指針到達根結點時，打印根結點，判斷根結點是否有左子和右子。有左子和右子的話就打印左子同時將右子入棧，將左子作為新的根結點進行判斷，方法同上。若當前結點沒有左子，則直接將右子打印，同時將右子作為新的根結點判斷。若當前結點沒有右子，則打印左子，同時將左子作為新的根結點判斷。若當前結點既沒有左子也沒有右子，則當前結點為葉子結點，此時將從棧中出棧一個元素，作為當前的根結點，打印結點元素，同時將當前結點同樣按上述方法判斷，依次進行。直至當前結點的左右子都為空，且棧為空時，遍歷結束。2. 中序遍歷：建立一個棧，當指針到達根結點時，把根結點壓棧，判斷根

4、結點是否有左孩子。有左孩子的話將左孩子，將新結點入棧，然后再將指針指向當前結點的左子，直至左子為空，彈棧一個元素，作為當前結點，打印該棧頂元素，將指針指向當前結點右子，將右子作為新的結點，結點入棧，再次進行上面的判斷，直至當前結點右子也為空，則再出棧一個元素作為當前結點，一直到結束，使得當前結點右子為空，且?？?，遍歷結束。3. 后續(xù)遍歷：建立一個棧，然后定義一個tag，取值為0，1，0代表右子沒有去過，1代表去過。初始時指針指向根結點，將根結點壓棧，指針指向左子，則將左子作為當前結點，繼續(xù)判斷直至左孩子為null，設q=null，tag=1。然后取得棧頂元素，設為當前結點，判斷當前結點的右孩子

5、是否等于q，如果相等，則打印當前結點，然后彈出當前結點，并且令q=當前結點的值。然后繼續(xù)判斷，直至右孩子不等于q，則將指針指向右孩子，把右孩子設為當前結點，令tag=0，繼續(xù)步驟，直到全部元素彈棧，棧為空時，遍歷結束。二、 算法流程圖開始判斷結點是否為空null訪問根結點結束先序方式遍歷左子樹先序方式遍歷右子樹是否 圖1.先序遞歸流程圖開始判斷結點是否空按中序方式遍歷左子樹結束訪問根結點按中根遍歷方式遍歷右子樹YN圖2. 中序遞歸流程圖開始判斷結點是否空按后根遍歷方式遍歷左子樹結束按后根遍歷方式遍歷右子樹訪問根結點YN圖3 .后序遞歸流程圖開始申請一個棧stack判斷結點是否空輸出結點值，壓棧

6、，指針指向它的左孩子判斷結點是否空彈出棧頂元素，指向結點的右孩子結束判斷?；蚪Y點是否空NYNYN圖4 . 先序非遞歸流程圖開始申請一個stack判斷結點是否空把結點壓棧，指針指向它的左孩子判斷結點是否空彈棧，設為當前結點，打印結點值，指向右孩子結束判斷?；蚪Y點是否空NYYNN圖1. 流程圖圖2. 流程圖圖3. 流程圖 圖 5. 中序非遞歸流程圖開始申請一個棧stack，用一個bool變量tag標記右孩子已被訪問把當前結點壓棧，p=p->lchild top+判斷標志tag是否為1輸出結點值p = s.pop()p= p->rchild結束NYYNNYYN判斷結點是否空判斷?；蚪Y點是

7、否為空判斷結點是否空 圖 6. 后序非遞歸流程圖三 、源代碼下面給出的是實現遞歸和非遞歸遍歷二叉樹的算法程序的源代碼（合并在一起）：#include <stdio.h>#include <stdlib.h>#define MAX 100 /定義堆棧最大容量enum BOOLFalse,True;enum RVISITRchildnovisit,Rchildvisit; /在后序遍歷二叉樹時用來指示是否已訪問過右子樹typedef struct BiTNode /定義二叉樹節(jié)點結構char data; /數據域 struct BiTNode *lchild,*rchild

8、; /左右孩子指針域BiTNode,*BiTree;typedef struct /定義堆棧結構BiTree elemMAX; /棧區(qū) int top; /棧頂指針BiTreeStack;void Initial(BiTreeStack &); /初始化一個堆棧BOOL Push(BiTreeStack &,BiTree); /將一個元素入棧BOOL Pop(BiTreeStack&,BiTree &); /將一個元素出棧BOOL Gettop(BiTreeStack ,BiTree &); /取得堆棧棧頂元素 BOOL StackEmpty(BiTre

9、eStack); /判斷堆棧是否已空void CreateBiTree(BiTree &); /生成一個二叉樹void PreOrder(BiTree); /先序非遞歸遍歷二叉樹void InOrder(BiTree); /中序非遞歸遍歷二叉樹void PostOrder(BiTree); /后序非遞歸遍歷二叉樹void PreTravel(BiTree ); /先序遞歸遍歷二叉樹void MidTravel(BiTree ); /中序遞歸遍歷二叉樹void PostTravel(BiTree ); /后序遞歸遍歷二叉樹int main() BiTree T; int flag=1;

10、/標記 BOOL temp; printf("二叉樹的遞歸和非遞歸遍歷n"); CreateBiTree(T); /生成一棵二叉樹 printf ("n");printf("遞歸先序遍歷二叉樹: ");PreTravel(T);printf("n"); printf ("n");printf("遞歸中序遍歷二叉樹: ");MidTravel(T);printf("n");printf ("n");printf("遞歸后序遍歷二

11、叉樹: ");PostTravel(T);printf("nnn"); if(T) printf ("nn"); printf("非遞歸先序遍歷二叉樹: "); PreOrder(T); printf("n"); else printf("二叉樹為空n"); if(T) printf("非遞歸中序遍歷二叉樹: "); InOrder(T); printf("n"); else printf("二叉樹為空n"); if(T) p

12、rintf("非遞歸后序遍歷二叉樹: "); PostOrder(T); printf("nnn"); else printf("二叉樹為空n"); void Initial(BiTreeStack &S)S.top=-1; /棧頂指針初始化為-1BOOL Push(BiTreeStack &S,BiTree ch) /將元素ch入棧，成功返回True,失敗返回False if(S.top>=MAX-1) return False; /判斷是否棧滿 else S.top+; /棧頂指針top加一 S.elemS.

13、top=ch; /入棧 return True; BOOL Pop(BiTreeStack &S,BiTree &ch) /將棧頂元素出棧,成功返回True，并用ch返回該元素值，失敗返回False if(S.top<=-1) return False; /判斷是否?？?else S.top-; /棧頂指針減一 ch=S.elemS.top+1; return True; BOOL Gettop(BiTreeStack S,BiTree &ch) /取得棧頂元素，成功返回True，并用ch返回該元素值，失敗返回False if(S.top<=-1) retu

14、rn False; else ch=S.elemS.top; /顯示棧頂元素 return True; BOOL StackEmpty(BiTreeStack S) /判斷堆棧是否已空，若空返回True,不空返回False if(S.top<=-1) return True; else return False; void CreateBiTree(BiTree &T) /生成一棵二叉樹，該二叉樹以T為根結點 char ch; scanf("%c",&ch); /讀入一個字符 if(ch=' ') T=NULL; else T=(BiT

15、Node *)malloc(sizeof(BiTNode); /生成一個新結點 T->data=ch; CreateBiTree(T->lchild); /生成左子樹 CreateBiTree(T->rchild); /生成右子樹 void PreTravel(BiTree T)/先序遍歷if(T) printf("%c",T->data);PreTravel(T->lchild);PreTravel(T->rchild); void MidTravel(BiTree T)/中序遍歷if(T) MidTravel(T->lchild

16、);printf("%c",T->data);MidTravel(T->rchild); void PostTravel(BiTree T)/后序遍歷if(T) PostTravel(T->lchild);PostTravel(T->rchild);printf("%c",T->data); void PreOrder(BiTree T) /先序非遞歸遍歷以T為根結點的二叉樹 BiTreeStack S; BiTree p; Initial(S); p=T; while(p|!StackEmpty(S) if(p) prin

17、tf("%c",p->data); Push(S,p); p=p->lchild; else Pop(S,p); p=p->rchild; printf("n"); void InOrder(BiTree T) /中序非遞歸遍歷以T為根結點的二叉樹 BiTreeStack S; BiTree p; Initial(S); p=T; while(p|!StackEmpty(S) if(p) Push(S,p); p=p->lchild; else Pop(S,p); printf("%c",p->data)

18、; p=p->rchild; printf("n"); void PostOrder(BiTree T) /后序非遞歸遍歷以T為根結點的二叉樹 BiTreeStack S; BiTree p,q; RVISIT tag; Initial(S); p=T; do while(p) Push(S,p); p=p->lchild; q=NULL; tag=Rchildvisit; while(!StackEmpty(S)&&tag) Gettop(S,p); if(p->rchild=q) printf("%c",p->

19、data); Pop(S,p); q=p; else p=p->rchild; tag=Rchildnovisit; while(!StackEmpty(S); printf("n");四 、運算結果例：輸入：12空格空格34空格空格空格 即 ：12 34 圖7. 遞歸和非遞歸遍歷二叉樹結果圖五、遇到的問題及解決這部分我主要遇到了如下兩個問題，其內容與解決方法如下所列：問題1描述： 初步完成編程的工作時，在輸入二叉樹的發(fā)現只能輸入一個字符，而且程序不再進行，最后是自己的不小心將語句char a; scanf("%c",&a);中的%c寫為%

20、d導致的。問題1解決方法：將%d改為%c問題2描述：在構建二叉樹的過程中，我最初用一重指針作為void Create()的形參，導致創(chuàng)建的二叉樹一直為空。后來經過深入思考，用二重指針實現了二叉樹的構建。還有在編寫主函數void main( )時，最初沒有沒有在函數體最后加上”getchar();”存儲回車，導致調用創(chuàng)建函數構造二叉樹時陷入莫名其妙的死循環(huán)。后來通過上網查閱資料，終于認識到錯誤所在。問題2解決方法： 用二重指針實現了二叉樹的構建，在函數體最后加上”getchar();”存儲回車。六 、心得體會課程設計期間，遇見一些問題，一個就是怎樣后序非遞歸遍歷二叉樹，經過分析和斟酌，終于得到比較滿意的程序，使得這個程序變得有一點意義。這一次的課程設計給我們提供了一個既能動手又動腦，獨立實踐的機會，應該緊緊抓住這個機會把所學的專業(yè)課程進一步的鞏固和加深，進一步培養(yǎng)我們的綜合能力。靈活運