1、數據結構（雙語）項目文檔報告用遞歸、非遞歸兩種方法遍歷二叉樹專 業： 計算機科學與技術 班 級： 指導教師： 姓 名： 學 號： 目 錄一、設計思想.03二、算法流程圖.04三、源代碼.06四、運行結果.12五、遇到的問題及解決.14六、心得體會.15一、設計思想1遞歸：（1）主函數main（）主程序要包括：定義的二叉樹T、建樹函數、先序遍歷函數、中序遍歷函數、后序遍歷函數。（2）建樹函數定義一個輸入的數是字符型的，當ch為空時，T就為空值，否則的話就分配空間給T，T就指向它的結點，然后左指針域指向左孩子，右指針指向右孩子，若還有，繼續調用,依次循環下去，直到ch遇到空時，結束。最后要返回建立

2、的二叉樹T。（3）先序遍歷函數根據先序遍歷規則，當T為非空時，先輸出結點處的數據，指針指向左、右孩子，依次進行下去。(4) 中序遍歷函數根據中序遍歷規則，當T為非空時，先左指針指向左孩子數據，然后輸出結點處的數據，再右指針指向右孩子，依次進行下去。(5）后序遍歷函數根據后序遍歷規則，當T為非空時，先右指針指向右孩子，然后左指針指向左孩子，最后輸出結點處的數據，依次進行下去。2.非遞歸：（1）跟遞歸遍歷二叉樹的前提一樣，首先應該創建一個二叉樹，同樣使用先序遞歸的方式創建二叉樹。 （2）然后是中序，先序，后序非遞歸遍歷二叉樹。 （3）中序非遞歸遍歷二叉樹的思想是：首先是根節點壓

3、棧，當根節點的左子樹不是空的時候，左子樹壓棧。直到左子樹為空的時候，不再壓棧。將棧頂元素出棧，訪問棧頂元素，并將棧頂的右子樹進棧。當右子樹的左子樹不是空的時候，左子樹一直進棧，直到左子樹為空，則不再進棧。重復上面的操作，直到?？盏臅r候。 (4)先序非遞歸遍歷二叉樹的思想是：首先是根節點進棧，然后當棧不為空的時候，將棧頂元素出棧，然后訪問。同時將出棧元素的右子樹進棧，左子樹進棧。重復上面的操作，直到棧為空。 (5）后序非遞歸遍歷二叉樹的思想：首先是根節點進棧，當根節點的左子樹不為空的時候，左子樹進棧，直到左為空的時候，左子樹不再進棧。指針指向的是右子樹，當右子樹為空的時候，直

4、接訪問根節點。當右子樹不為空的時候，則右子樹的指針進棧，當右子樹的左子樹不為空的時候，則左也進棧，直到左為空。重復上面的操作，直到棧為空的時候，則遍歷樹完成。 二、算法流程圖1.遞歸2.非遞歸三、源代碼1.遞歸#include "stdio.h"#include "conio.h"#include <stdlib.h>#include<stack>typedef struct node char data; struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTr

5、ee; /定義二叉樹類型的指針/*先序創建二叉樹*/int CreateBinTree(BinTree *T) char ch; *T=(BinTree)malloc(sizeof(BinTnode); if(!*T) printf("overflow"); do ch=getchar(); if(ch=' ') *T=NULL; return 0; else (*T)->data=ch; CreateBinTree(&(*T)->lchild); CreateBinTree(&(*T)->rchild); return 1

6、; while(ch!='0');/*中序遞歸遍歷*/void InorderTransverse(BinTree s)if (s)InorderTransverse(s->lchild); printf("%c", s->data);InorderTransverse(s->rchild);/先序遞歸遍歷二叉樹void PreOrderTranverseTree(BinTree s)if (s) printf("%c", s->data);PreOrderTranverseTree(s->lchild);P

7、reOrderTranverseTree(s->rchild);/后序遞歸遍歷二叉樹void PostOrderTranverseTree(BinTree s)if (s) PreOrderTranverseTree(s->lchild);PreOrderTranverseTree(s->rchild);printf("%c", s->data);/*主方法*/void main() BinTree T;printf("請按照先序的順序輸入要創建的樹:n");CreateBinTree(&T); /*中序序列創建二叉樹*/

8、printf("中序遞歸遍歷的序列是:"); InorderTransverse(T); printf("n"); /先序遞歸遍歷 printf("先序遞歸遍歷的序列是:"); PreOrderTranverseTree(T); printf("n"); /后序遞歸遍歷 printf("后序遞歸遍歷的序列是:"); PostOrderTranverseTree(T); printf("n");2.非遞歸#include "stdio.h"#include

9、"conio.h"#include <stack>#include <stdlib.h>typedef struct node char data; struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; /定義二叉樹類型的指針typedef struct BinTree data100; int top;SeqStack;void initStack(SeqStack *S) S->top =-1;void Push(SeqStack *S,BinTree x) if

10、(S->top=100-1) printf("the stack is overflow"); else S->top=S->top+1; S->dataS->top=x; int Pop(SeqStack *S,BinTree *p) if(S->top=-1) printf("the stack is underflow"); return 0; else *p=S->dataS->top; -S->top; return 1; int EmptyStack(SeqStack S) if(S.to

11、p=-1) return 1; else return 0; /* 棧不空的情況*/ int GetTop(SeqStack S,BinTree *p) if(S.top=-1) printf("the stack is empty"); return 0; else *p=S.dataS.top; return 1; char visit(BinTree p)return (*p).data;/*創建二叉樹*/int CreateBinTree(BinTree *T) char ch; *T=(BinTree)malloc(sizeof(BinTnode); if(!*T

12、) printf("overflow"); else do ch=getchar(); if(ch!=' ') *T=NULL; return 0; else (*T)->data=ch; CreateBinTree(&(*T)->lchild); CreateBinTree(&(*T)->rchild); return 1; while(ch!='0'); /*中序非遞歸遍歷*/void InorderTransverse(BinTree T) SeqStack S; BinTree p; initStac

13、k(&S);/初始化棧 printf("中序非遞歸序列是:"); Push(&S,T); /根指針進棧 T為指向二叉樹的指針 while(!EmptyStack(S) /棧不是空的情況 while(GetTop(S,&p) && p) Push(&S,p->lchild); /gettop得到的結果也必須是一棵子樹才行 ,進棧應該進的是樹根的指針 Pop(&S,&p); if(!EmptyStack(S) /printf("%c",visit(p); Pop(&S,&p

14、); printf("%c",visit(p); Push(&S,p->rchild); /*先序非遞歸遍歷*/void PreorderTransverse(BinTree T) SeqStack S; BinTree p; initStack(&S);/初始化棧 Push(&S,T); /根指針進棧 T為指向二叉樹的指針 printf("先序非遞歸序列是:"); while(!EmptyStack(S) Pop(&S,&p); /根節點出棧 if(p!=NULL) printf("%c"

15、;,visit(p); Push(&S,p->rchild); Push(&S,p->lchild);/*后序非遞歸遍歷*/void PostorderTransverse(BinTree T) SeqStack S; BinTree p,q; initStack(&S);/初始化棧 p=T; printf("后序非遞歸序列是:"); while(p |!EmptyStack(S) /跳出while循環的原因是因為左子樹或者右子樹為空了 if(p!=q) while(p!=NULL) Push(&S,p); if(p->lc

16、hild!=NULL) p=p->lchild; else p=p->rchild; if(EmptyStack(S) break; GetTop(S,&q); if(q->rchild=p) /進棧的是右子樹 Pop(&S,&p); printf("%c",visit(p); p=q; else p=q->rchild; /*主方法*/void main() BinTree T;printf("請按照先序的順序輸入創建的樹:n");/*創建樹*/ CreateBinTree(&T);/中序非遞歸遍

17、歷 InorderTransverse(T); printf("n"); /先序非遞歸遍歷 PreorderTransverse(T); printf("n"); /后序非遞歸遍歷 PostorderTransverse(T);四、運行結果1.遞歸輸入結果2.非遞歸輸入結果五、遇到的問題及解決經過一個星期的寫代碼，我遇到了很多問題，并一一解決了，比如：1. 創建二叉樹時：void createBiTree(BiTNode *T)和void createBiTree(BiTNode *&T)沒分清楚區別。后來查找資料找到void createBiTree(BiTNode *T)是將結點的指針（地址）傳遞到函數中進行處理void createBiTree(BiTNode *&