二叉樹的生成與遍歷

1、課程設計報告課程名稱 數(shù)據(jù)結構課程設計 專 業(yè)： 信息管理與信息系統(tǒng) 班 級： 姓 名： 學 號： 指導教師： 成 績： 2016 年 12 月 16 日一、實驗一問題分析和任務定義題目：二叉樹的生成和遍歷 任務：1、將二叉樹以廣義表形式存儲在一個TXT文件上，通過讀取TXT文件，建立二叉樹；2、求樹的高度；3、實現(xiàn)二叉樹的前序、中序和后序遍歷；4、將輸出結果存儲在文件內。需求分析：在二叉樹的應用中，常常要求在樹中查找具有某種特征的結點，或者對樹中全部結點逐一進行某種處理，這就是二叉樹的遍歷問題。對二叉樹的數(shù)據(jù)結構進行定義，建立一棵二叉樹，然后進行各種實驗操作。二叉樹是一個非線性結構，遍歷時要

2、先明確遍歷的規(guī)則，先訪問根結點還時先訪問子樹，然后先訪問左子樹還是先訪問有右子樹，這些要事先定好，因為采用不同的遍歷規(guī)則會產(chǎn)生不同的結果。本次實驗要實現(xiàn)先序、中序、后序三種遍歷?；诙鏄涞倪f歸定義，以及遍歷規(guī)則，本次實驗也采用的是先序遍歷的規(guī)則進行建樹的以及用遞歸的方式進行二叉樹的遍歷。二、邏輯設計： 主程序 系統(tǒng)總框架圖 樹的深度廣度優(yōu)先遍歷后序遍歷中序遍歷先序遍歷建立二叉樹1、構造二叉樹，本程序構造二叉樹所輸入廣義表為a(b(d，e),c（，f）) a b c d e f2、遍歷功能模塊 可以通過要求對所構造的二叉樹進行先序遍歷、中序遍歷、后序遍歷，廣度優(yōu)先遍歷。3、求二叉樹的深度。功能

3、設計：1) Struct BTNode() 使用鏈式存儲結構定義一個結構體數(shù)組，保存二叉樹的字符信息和定義指向其左孩子和右孩子的指針。2）CreateBTree() 從鍵盤上輸入構造二叉樹的字符以*表示結點的空孩子。3）PreOrder() 此函數(shù)的功能是完成所構造二叉樹的先序遍歷。4）InOrder() 此函數(shù)的功能是完成所構造二叉樹的中序遍歷。5）PostOrder() 此函數(shù)的功能是完成所構造二叉樹的后序遍歷。6）Levelorder（）此函數(shù)的功能是完成所構造的二叉樹的廣度優(yōu)先遍歷7）BTreeDepth() 對構造好的二叉樹求其深度。三、詳細設計：1、二叉鏈表由頭指針唯一確定，若二叉

4、樹為空，則頭指針指向空，若結點的某個孩子不存在，則相應的指針為空。2遍歷模塊1）先序遍歷：先訪問根節(jié)點，然后分別遍歷左子樹，右子樹，遍歷左子樹和右子樹的方法和遍歷整個二叉樹的方法一樣，而訪問根節(jié)點是一個固定操作，所以可用遞歸方法實現(xiàn)。遍歷的結束條件是二叉樹為空。2）中序遍歷：中序遍歷的算法思想和先序遍歷一樣，僅僅是處理結點的次序不同其思想為，若二叉樹為空，則結束遍歷操作，否則中序遍歷根節(jié)點的左子樹，訪問根節(jié)點中序遍歷根結點的右子樹。3）后序遍歷：后序遍歷的基本思想為，若二叉樹為空，則結束遍歷操作，否則后序遍歷根結點的左子樹，后序遍歷根節(jié)點的右子樹，訪問根結點。4)廣度優(yōu)先遍歷：廣度優(yōu)先遍歷的思

5、想為，若二叉樹為空，則結束遍歷操作，否則按層進行遍歷。5）求二叉樹的深度。四、程序編碼：1、二叉鏈表由頭指針唯一確定，若二叉樹為空，則頭指針指向空，若結點的某個孩子不存在，則相應的指針為空。用廣義表輸出二叉樹。源代碼：void CreateBTree(struct BTreeNode * BT,char * a) /*根據(jù)a所定義的二叉樹廣義表字符串建立對應的存儲結構*/struct BTreeNode * p; /*定義s數(shù)組作為存儲根結點指針的棧使用*/struct BTreeNode * sStackMaxSize; /*定義top作為s棧的棧頂指針，初值為-1，表示空棧*/int to

6、p=-1; /*用k作為處理結點的左子樹和右子樹的標記，k=1處理左子樹，k=2處理右子樹*/int k; /*用i掃描數(shù)組a中存儲的二叉樹廣義表字符串，初值為0*/int i=0; /*把樹根指針置為空，即從空樹開始建立二叉樹*/*BT=NULL; /*每循環(huán)一次處理一個字符，直到掃描到字符串結束0為止*/while (ai)switch(ai)case ' ': /*對空格不做任何處理*/ break;case '(': if(top=StackMaxSize-1) printf("棧空間太小，需增加StackMaxSize!n"); e

7、xit(1); top+; stop=p; k=1; break;case ')':if(top=-1)printf("二叉樹廣義表字符串錯!n");exit(1);top-;break;case ',':k=2;break; default:p=(struct BTreeNode * )malloc(sizeof(struct BTreeNode);p->data=ai;p->left=p->right=NULL;if(*BT=NULL)*BT=p;elseif(k=1)stop->left=p;elsestop-&

8、gt;right=p; /*switch end*/ /*為掃描下一個字符串修改i值*/i+;void PrintBTree(struct BTreeNode * BT) /*輸出二叉數(shù)的廣義表表示*/*數(shù)為空時自然結束遞歸，否則執(zhí)行如下操作*/if(BT=NULL) /*輸出根結點的值*/ printf("%c",BT->data); /*輸出左、右子樹*/ if(BT->left!=NULL | BT->right!=NULL) printf("("); /*輸出左括號*/ PrintBTree(BT->left); /*輸出

9、左子樹*/ if(BT->right!=NULL) PrintBTree(BT->right); /*輸出右子樹*/ printf(")"); /*輸出右括號*/ 2遍歷模塊1）先序遍歷：先訪問根節(jié)點，然后分別遍歷左子樹，右子樹，遍歷左子樹和右子樹的方法和遍歷整個二叉樹的方法一樣，而訪問根節(jié)點是一個固定操作，所以可用遞歸方法實現(xiàn)。遍歷的結束條件是二叉樹為空。源代碼：void Preorder(struct BTreeNode * BT)if(BT!=NULL) printf("%c",BT->data); /*訪問根結點*/ Preor

10、der(BT->left); /*前序遍歷左子樹*/Preorder(BT->right); /*前序遍歷右子樹*/2）中序遍歷：中序遍歷的算法思想和先序遍歷一樣，僅僅是處理結點的次序不同其思想為，若二叉樹為空，則結束遍歷操作，否則中序遍歷根節(jié)點的左子樹訪問根節(jié)點中序遍歷根結點的右子樹。 源代碼：void Inorder(struct BTreeNode * BT)if(BT!=NULL) Inorder(BT->left); /*中序遍歷左子樹*/ printf("%c",BT->data); /*訪問根結點*/ Inorder(BT->ri

11、ght); /*中序遍歷右子樹*/3）后序遍歷：后序遍歷的基本思想為，若二叉樹為空，則結束遍歷操作否則后序遍歷根結點的左子樹，后序遍歷根節(jié)點的右子樹，訪問根結點。源代碼 ：void Postorder(struct BTreeNode * BT)if(BT!=NULL) Postorder(BT->left); /*后序遍歷左子樹*/ Postorder(BT->right); /*后序遍歷右子樹*/ printf("%c",BT->data); /*訪問根結點*/4)廣度優(yōu)先遍歷：廣度優(yōu)先遍歷的思想為，若二叉樹為空，則結束遍歷操作，否則按層進行遍歷。源代

12、碼：void Levelorder(struct BTreeNode * BT) /*按層遍歷由BT指針所指向的二叉樹*/struct BTreeNode * p; /*定義隊列所使用的數(shù)組空間，元素類型為指向結點的指針類型*/ struct BTreeNode* qQueueMaxSize;/*定義隊首指針和隊尾指針，初始均置0表示空隊*/ int front=0,rear=0; /*將樹根指針進隊*/if(BT!=NULL) rear=(rear+1)% QueueMaxSize; qrear=BT; /*當隊列非空時執(zhí)行循環(huán)*/while(front!=rear) /*使隊首指針指向隊首

13、元素*/ front=(front+1)% QueueMaxSize; /*刪除隊首元素，輸出隊首元素所指結點的值*/ p=qfront; printf("%c",p->data); /*若結點存在左孩子，則左孩子指針結點進隊*/ if(p->left!=NULL) rear=(rear+1)% QueueMaxSize; qrear=p->left; /*若結點存在右孩子，則右孩子指針結點進隊*/ if(p->right!=NULL) rear=(rear+1)% QueueMaxSize; qrear=p->right; 3、求二叉樹的深度

14、。 源程序：int BTreeDepth(struct BTreeNode * BT) /*求由指針指向的一顆二叉樹的深度*/if(BT=NULL)return 0; /*對于空樹，返回0并結束遞歸*/else /*計算左子樹的深度*/int dep1=BTreeDepth(BT->left); /*計算右子樹的深度*/int dep2=BTreeDepth(BT->right); /*返回樹的深度*/if(dep1>dep2)return dep1+1;elsereturn dep2+1;五、程序調試與測試：1、建立二叉樹2、主菜單界面3、前序遍歷4、中序遍歷5、后序遍歷6

15、、廣度優(yōu)先遍歷7、樹的深度六、結果分析：在調試過程中，碰到諸多問題，比如定義表長過小，處理記錄數(shù)量錯誤時 程序的異常，記錄沖突次數(shù)等等。處理這些問題異常麻煩，有時連續(xù)錯誤，摸不清頭緒，在不斷修改調試之后，終于運行成功，并對所輸入的二叉樹實現(xiàn)了前序、中序、后序以及廣度優(yōu)先遍歷，同時計算了樹的深度。七、課程設計心得體會：二叉樹是常用的數(shù)據(jù)結構。通過實驗加深了我對二叉樹的遍歷的認識，鞏固了課本中所學的關于樹的基本算法。按要求完成了實驗內容。通過實驗，有如下幾點收獲和體會：1、通過實驗還提高了一點改錯能力，對于一些常見問題加深了印象。2、編程需要有耐心，尤其是在調試程序的時候，更是馬虎不得，有時候關鍵

16、就是那么一步，錯過了就得從頭來過了。編程也需要勇氣，要勇于發(fā)現(xiàn)自己的錯誤，也要勇于推翻自己之前的思路，要堅信“沒有最好，只有更好”。編程需要細心，有時一個不注意小錯誤就能引出大問題。編程也需要規(guī)范，不僅為了他人能看得懂程序，也為了方便自己以后程序的更改與進一步的完善。3、程序由算法和數(shù)據(jù)結構組成，一個好的程序不僅算法重要，數(shù)據(jù)結構的設計也很重要。4.以前在學C語言時總覺得函數(shù)的遞歸調用是一樣很復雜的算法，經(jīng)常會理解不了而導致編程的錯誤。但在這次實驗中，二叉樹的先序、中序、后序與廣度優(yōu)先的輸出都用了遞歸算法。而且用起來并不復雜，這使我更進一步學習理解了函數(shù)的遞歸調用并得到靈活的運用。 經(jīng)過本次實

17、驗基本上解決的一些所遇到的問題，我對二叉樹的結構等有了較為深入的理解。我會繼續(xù)我的興趣編寫程序的，相信在越來越多的嘗試之后，自己會不斷進步。八、源程序清單：# include<stdio.h># include<stdlib.h># define QueueMaxSize 20 /*定義隊列數(shù)組長度*/# define StackMaxSize 10 /*定義棧數(shù)組長度*/typedef char ElemType;struct BTreeNodeElemType data; struct BTreeNode * left; struct BTreeNode * rig

18、ht;BTreeNode;void InitBTree(struct BTreeNode* BT) /*初始化二叉樹，即把樹根指針置空*/*BT=NULL;void CreateBTree(struct BTreeNode * BT,char * a) /*根據(jù)a所定義的二叉樹廣義表字符串建立對應的存儲結構*/struct BTreeNode * p; /*定義s數(shù)組作為存儲根結點指針的棧使用*/struct BTreeNode * sStackMaxSize; /*定義top作為s棧的棧頂指針，初值為-1，表示空棧*/int top=-1; /*用k作為處理結點的左子樹和右子樹的標記，k=1

19、處理左子樹，k=2處理右子樹*/int k; /*用i掃描數(shù)組a中存儲的二叉樹廣義表字符串，初值為0*/int i=0; /*把樹根指針置為空，即從空樹開始建立二叉樹*/*BT=NULL; /*每循環(huán)一次處理一個字符，直到掃描到字符串結束0為止*/while (ai)switch(ai)case ' ': /*對空格不做任何處理*/ break;case '(': if(top=StackMaxSize-1) printf("?？臻g太小，需增加StackMaxSize!n"); exit(1); top+; stop=p; k=1; brea

20、k;case ')':if(top=-1)printf("二叉樹廣義表字符串錯!n");exit(1);top-;break;case ',':k=2;break; default:p=(struct BTreeNode * )malloc(sizeof(struct BTreeNode);p->data=ai;p->left=p->right=NULL;if(*BT=NULL)*BT=p;elseif(k=1)stop->left=p;elsestop->right=p; /*switch end*/ /*為掃

21、描下一個字符串修改i值*/i+;void PrintBTree(struct BTreeNode * BT) /*輸出二叉數(shù)的廣義表表示*/*數(shù)為空時自然結束遞歸，否則執(zhí)行如下操作*/if(BT=NULL) /*輸出根結點的值*/ printf("%c",BT->data); /*輸出左、右子樹*/ if(BT->left!=NULL | BT->right!=NULL) printf("("); /*輸出左括號*/ PrintBTree(BT->left); /*輸出左子樹*/ if(BT->right!=NULL) Pr

22、intBTree(BT->right); /*輸出右子樹*/ printf(")"); /*輸出右括號*/ void Preorder(struct BTreeNode * BT)if(BT!=NULL) printf("%c",BT->data); /*訪問根結點*/ Preorder(BT->left); /*前序遍歷左子樹*/Preorder(BT->right); /*前序遍歷右子樹*/void Inorder(struct BTreeNode * BT)if(BT!=NULL) Inorder(BT->left);

23、 /*中序遍歷左子樹*/ printf("%c",BT->data); /*訪問根結點*/ Inorder(BT->right); /*中序遍歷右子樹*/void Postorder(struct BTreeNode * BT)if(BT!=NULL) Postorder(BT->left); /*后序遍歷左子樹*/ Postorder(BT->right); /*后序遍歷右子樹*/ printf("%c",BT->data); /*訪問根結點*/void Levelorder(struct BTreeNode * BT)

24、/*按層遍歷由BT指針所指向的二叉樹*/struct BTreeNode * p; /*定義隊列所使用的數(shù)組空間，元素類型為指向結點的指針類型*/ struct BTreeNode* qQueueMaxSize;/*定義隊首指針和隊尾指針，初始均置0表示空隊*/ int front=0,rear=0; /*將樹根指針進隊*/if(BT!=NULL) rear=(rear+1)% QueueMaxSize; qrear=BT; /*當隊列非空時執(zhí)行循環(huán)*/while(front!=rear) /*使隊首指針指向隊首元素*/ front=(front+1)% QueueMaxSize; /*刪除隊

25、首元素，輸出隊首元素所指結點的值*/ p=qfront; printf("%c",p->data); /*若結點存在左孩子，則左孩子指針結點進隊*/ if(p->left!=NULL) rear=(rear+1)% QueueMaxSize; qrear=p->left; /*若結點存在右孩子，則右孩子指針結點進隊*/ if(p->right!=NULL) rear=(rear+1)% QueueMaxSize; qrear=p->right; int BTreeDepth(struct BTreeNode * BT) /*求由指針指向的一顆二

26、叉樹的深度*/if(BT=NULL)return 0; /*對于空樹，返回0并結束遞歸*/else /*計算左子樹的深度*/int dep1=BTreeDepth(BT->left); /*計算右子樹的深度*/int dep2=BTreeDepth(BT->right); /*返回樹的深度*/if(dep1>dep2)return dep1+1;elsereturn dep2+1;void menu()/窗體顯示菜單printf("n*請在下列序號中選擇一個并輸入*:n");printf(" n");printf(" 1、重新

27、定義二叉樹 n");printf(" 2、前序遍歷二叉樹 n");printf(" 3、中序遍歷二叉樹 n");printf(" 4、后序遍歷二叉樹 n");printf(" 5、廣度優(yōu)先遍歷二叉樹 n");printf(" 6、二叉樹深度 n");printf(" 0、退出 n");printf(" n"); printf("n*:n");void Wrong()/錯誤提示printf("n=>按鍵錯誤!n&

28、quot;);getchar();/保留錯誤信息的顯示void main()/*定義指向二叉樹節(jié)點的操作，并用指針作為樹根指針*/struct BTreeNode * bt; /*定義一個用于存放二叉樹廣義表的字符數(shù)組*/char b50; /*定義ElemType類型的對象X和指針對象px*/ ElemType x,* px; /*初始化二叉樹，即置樹根bt為空*/InitBTree(&bt); /*從鍵盤向字符數(shù)組b輸入二叉樹廣義表標識的字符串*/printf("輸入二叉樹廣義表字符串:n"); printf("輸入格式為:a(c(m,d(s,z),e

29、(t(h,k),b(i)n"); scanf("%s",b); /*建立以bt作為樹根指針的二叉樹的鏈接存儲結構*/CreateBTree(&bt,b);menu(); while(10)/界面的顯示實現(xiàn) int p; scanf("%d",&p); switch(p) case 0:printf("=>謝謝使用!n"); getchar(); break;case 1:printf("請重新輸入二叉樹廣義表字符串:n");printf("輸入格式為:a(c(m,d(s,z),e(t(h,k),b(i)n"); scanf("%s",b)