1、湖南涉外經濟學院課程設計報告課程名稱：數據結構報告題目：二叉樹的基本操作學生姓名：肖琳桂、康政、張小東、張帆所在學院：信息科學與工程學院專業班級：軟工本1402學生學號： 144300211、02、14、08指導教師：李春庭2015年 12 月 31日課程設計任務書報告題目二叉樹的基本操作完成時間2 周肖琳桂專 業軟工本學生姓名指導教師李春庭職稱講師康政班級1402總體設計要求和主要功能設計一個程序，實現二叉樹的創建以及二叉樹的遍歷（包括先序遍歷、中序遍歷、后序遍歷和層次遍歷），計算并輸出二叉樹的深度和結點個數，功能要求：1二叉樹以二叉鏈表存儲，結點數據類型采用字符表示，按二叉樹的先序遍歷序列

2、創建。2用文本編輯器編寫一個data.txt的文件 , 包含 3 個以上創建按二叉樹的先序遍歷序列 ( 即序列中包含空樹節點 ) ，每個序列長度不少于10 個，在運行程序時自動載入，也可以由鍵盤輸入創建二叉樹。|3菜單功能：創建二叉樹（二級菜單說明選擇文件中的第幾個，輸出創建二叉樹的深度及結點數，若失敗則有相應提示），遍歷序列（顯示先序，中序，后序和層次遍歷結果），結點的孩子信息，退出系統。工作內容及時間進度安排第 17 周：周 1- 周 2：立題、論證方案設計周 3- 周 5 ：程序設計及程序編碼第 18周：周 1- 周 3 ：程序調試周 4- 周 5 ：驗收答辯摘要本課程設計主要說明如何在

3、C+編程環境下實現二叉樹的遍歷，遍歷方式包括 : 二叉樹的先序遍歷、中序遍歷、后序遍歷，層次遍歷等四種遍歷方式。同時，此次課程設計還包括了求二叉樹深度和結點個數， 結點的孩子信息， 以及對文件的操作，用文件讀取的方式實現對二叉樹的建立。 以通過此次課程設計， 使學生充分掌握樹的基本操作， 以及對線性存儲結構的理解。 同時，在對樹的遍歷的操作過程中，同樣是運用遞歸的方式實現遍歷， 在對樹實現層次操作的時候， 要求用循環隊列的操作方式來實現層次遍歷。 此次課程設計對數據結構內容綜合性的運用的要求較高。關鍵詞：二叉樹，先序遍歷， 中序遍歷，后序遍歷， 層次遍歷，節點，線性存儲 , 節點的孩子信息目錄

4、課程設計任務書1一、需求分析41問題描述42功能要求4二、概要設計51. 總體設計圖52. 數據結構設計53. 算法設計54. 主要模塊及模塊之間的關系5三、詳細設計61. 結構體（或類）設計62.主要模塊實現的流程圖63. 算法設計7四、測試運行81登錄和主界面運行效果圖82運行說明83.運行效果圖8五、結論與心得101. 總體評價102. 所做的工作及體會10六、程序附錄（源代碼）13七、參考文獻20一、需求分析1問題描述設計一個二叉樹。 二叉樹形象地說即樹中每個節點最多只有兩個分支， 它是一種重要的數據類型。 可以運用于建立家譜， 公司所有的員工的職位圖， 以及各種事物的分類和各種機構的

5、職位圖表等。二叉樹是通過建立一個鏈式存儲結構，達到能夠實現前序遍歷，中序遍歷，后序遍歷，層次遍歷。以及能夠從輸入的數據中得知二叉樹的葉子結點的個數， 二叉樹的深度。 在此，二叉樹的每一個結點中必須包括：值域，左指針域，右指針域。我們抽象出下列問題： 實現文件操作，運用文件輸入流， 將已經寫好二叉樹序列的 txt 文本文件，加載到程序中， 實現文件創建二叉樹。然后采用鏈表存儲的方式遍歷二叉樹（先序遍歷、中序遍歷、后序遍歷、層次遍歷）。層次遍歷運用循環隊列的方法實現，需要重新定義隊頭和隊尾，以及隊列的最大長度，并且在屏幕上實現輸出顯示。2功能要求(1) 用菜單的形式實現操作界面，提供（ 14）個功

6、能選項，功能分別為創建二叉樹、遍歷序列、節點的孩子信息、退出系統。(2) 創建二叉樹。要求用文件讀取和鍵盤輸入兩種不同的方式實現二叉樹的創建。二級菜單說明，輸出創建二叉樹的深度及結點數，若失敗則有相應提示。(3) 遍歷序列。顯示先序，中序，后序和層次遍歷結果。先序遍歷、中序遍歷、后序遍歷用遞歸的方法實現遍歷。層次遍歷，用循環隊列的方法實現。(4) 每次實現一項操作之后，要有相應的提示返回菜單。4二、概要設計1. 總體設計圖主菜單創建二叉樹遍歷序列節點的孩子信退出系統息鍵文先中后層盤件序序序次輸輸遍遍遍遍入入歷歷歷歷2. 數據結構設計數據元素為字符， 邏輯結構為樹形結構， 存儲結構為二叉鏈式存儲

7、， 系統操作的數據元素主要是創建一個二叉樹，遍歷序列。3. 算法設計本系統主要用到的算法有先序遍歷、中序遍歷、后序遍歷、層次遍歷、創建二叉樹和查找節點。從子菜單界面只能返回到主菜單界面，而不是退出程序。4. 主要模塊及模塊之間的關系運行程序后直接進入“菜單主界面”模塊，菜單顯示分為4 個模塊，（14）分別為創建二叉樹、遍歷序列、節點的孩子信息、退出系統。主界面中的各個模塊都是獨立運行，每完成一項操作后， 返回主菜單模塊。通過相應定義的函數（外部接口）實現，內部數據的改變由模塊內部完成。5三、詳細設計1. 結構體（或類）設計typedef char TElemType;typedef struc

8、t BiTNodeTElemType date;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;2. 主要模塊實現的流程圖開始主菜單界面輸入選擇（ 14）Case=sel？Case=4退出系統Case=1創建二叉樹Case=2遍歷序列先序遍歷中序遍歷后序遍歷層次遍歷Case=3結點的孩子信 息63. 算法設計先序遍歷：void PreOrderTraverse(BiTree T) if(T) cout<<T->date; PreOrderTraverse(T->lchild); PreOrderTraverse(T->

9、;rchild); 中序遍歷：void InOrderTraver(BiTree T) if(T) InOrderTraver(T->lchild); cout<<T->date; InOrderTraver(T->rchild); 后序遍歷：void PostOrderTraver(BiTree T) if(T) PostOrderTraver(T->lchild); PostOrderTraver(T->rchild); cout<<T->date; 層次遍歷：void ccbl(BiTNode *b) BiTNode *p;Bi

10、TNode *qMaxSize;int qm,h;qm=h=-1;h+; qh=b;while(qm != h) qm=(qm+1)%MaxSize; p=qqm; printf("%c ",p->date); if(p->lchild!=NULL) h=(h+1)%MaxSize;qh=p->lchild; if(p->rchild!=NULL) h=(h+1)%MaxSize; qh=p->rchild; 7四、測試運行1登錄和主界面運行效果圖2運行說明主程序運行后，直接到菜單選擇界面。其中有(1 4 個選項可以選擇 )1. 創建二叉樹 2

11、. 遍歷序列 3. 節點的孩子信息4. 退出系統。除退出以外 , 每個功能模塊運行完后，返回到主菜單界面，每個界面相互獨立。3. 運行效果圖8表 學生情況統計表序姓名性出生日期學號專業聯系電話備注號別1康政男1994.12144300202軟件工長2肖琳桂男1996.08144300211軟件工程157175144943張小東男1994.07144300214軟件工程4張帆男1995.08144300208軟件工程9五、結論與心得1. 總體評價在此次的課程設計中， 由于不夠細心， 在程序設計中犯了一些錯誤， 花了挺多的時間。但是經過一番思考并且在老師的幫助下， 找到了

12、導致程序錯誤的原因，經過幾次修改和調試， 程序能正常運行， 并且能夠完成課程設計任務中的大部分功能。同時在此次的課程設計中讓我更深刻的了解了二叉樹的基本操作， 增加了對專業只是學習的興趣。 我想在以后的學習中， 我們會繼續努力， 希望在計算機方面有好的成績， 也感謝老師給我們這次課程設計的機會， 讓我們認識到了自身的不足，讓我們能夠不斷地完善自己 !2.所做的工作及體會肖琳桂：編寫程序和課程設計報告。 課程設計中我主要擔任程序設計的編寫和設計報告的編寫工作， 經過兩個星期的上機實踐學習， 使我對數據結構有了更進一步的認識和理解，也知道了要想學好它要重在實踐， 要通過不斷的上機操作才能更好地學習

13、它。通過實踐我發現我的很多不足之處， 然感覺理論上已經掌握， 但在運用到實踐的過程中仍有意想不到的困惑， 因為自己對知識點的掌握不夠熟悉， 但通過學習有很大改進。在這次課程設計中使我知道了二又樹的先序、 中序、后序、層次遍歷。同時，還包括了求二叉樹深度和結點個數， 結點的孩子信息， 以及對文件的操作， 用文件讀取的方式實現對二叉樹的建立。 充分掌握樹的基本操作， 以及對線性存儲結構的理解。也培養了我如何去把握一件事情， 如何去做一件事情， 又如何完成一件事情的方法和技巧。在設計過程中，和同學們相互探討，相互學習，相互監督。我學會了運籌帷幌，學會了寬容，學會了理解，也學會了做人與處世，這次課程設

14、計對找來說受益良多。在今后的日子里， 我會認真對待每一件事情， 爭取做到最好， 努力將知識與實踐相結合，不斷鞏固，加深所學的知識，做到學以致用。另外感謝老師的細心教導，以及同學們的幫助。10康政：編寫程序和課程設計報告。 我在小組中做了編寫程序和撰寫報告的工作。 在編寫程序時，遇到很多困難， 例如缺少聲明，調用函數錯誤等等。 通過網上搜查，查詢資料以及老師的指點幫助， 完成了很多任務。 作為基礎不是很好的學生， 我在克服自己知識不足的過程中也在努力學習新的知識， 運用不同的原理編寫出不同的算法。也學習到，算法不能盲目抄襲，很多東西是不同的，必須通過自己的思考和努力的鉆研才能寫出一套完整的代碼，

15、 不可心急，越是急越不可能精細的完成任務。撰寫報告的時候， 很多地方因細節問題處理不好導致出了大大小小很多漏洞，不能很精細的完成指定的任務。從中我也明白了，做一件事，尤其是耗時的編寫程序的問題，不能心急也不能馬虎，也許一點點出錯整個程序就會崩潰，還要重新一點點的檢查才能找出問題， 大大降低了辦事效率。 所以，今后要做的第一件事是慢慢鞏固檢出， 打好根基。第二件事是沉下心來認真做事， 不能毛手毛腳，從頭到尾認真細致的做下去， 避免出錯惹出更多的麻煩。 這次的程序設計使我受益匪淺，學到了很多，做了很多。希望以后可以更多的做這種任務，鞏固知識，學習新的知識，有了這些經驗可以做的更好。張小東：查找資料

16、和打印。 這次我在小組中做的事情是查詢資料和打印排版。 雖然因為我的專業底子差一點， 現在暫時只能在程序設計時查找一些需要用到的專業資料，幫助組員完成設計， 但我相信下一次我不會僅此于此。 這次程序設計我的收獲還是很大了， 讓我懂得了學好專業知識， 并不是自己想象中的難， 而是你自己是否去努力了。在查找資料的過程中， 我是邊查邊學自己不會的知識點。 查找途中也遇到了一些當時不能理解的知識點， 但經過同學的細心解答， 最后一些難掌握的知識點都被基本掌握。 這讓我懂得編程過程需要很大的耐心， 而且要有良好的思維和扎實的專業基礎知識，所以我需要努力的學習，發現自身不足之處并努力改正他，逐步提高自身的

17、能力， 不斷取得進步。 通過這次課程設計， 我認識到知識運用的重要性，并且努力加深對基礎知識的理解， 從中了解自己需要學習的東西并學會自學。作為一名計算機專業的學生，今后我會加緊學習，學好專業知識，為將來打下堅實的基礎。11張帆：查找資料和打印。 這次我在小組中做的事情是查詢資料， 打印排版。 雖然這些工作并不是主要任務， 但是我用心對待， 認真為做程序的同學查找資料， 為他們挑選所需要的代碼以及算法， 及時反饋給他們信息。 因為基礎不是很好， 經常會剪裁到一些不是很合適的代碼， 我們通過共同分析， 共同篩選， 最終也獲得了很多收獲。通過和他們一起分析代碼， 我也漲了很多知識。 懂的了二叉樹的

18、算法，數據類型等等。 報告的排版也是一項需要耐心的工作， 通過晚上的時間， 我認認真真的對所寫的設計報告進行了排版， 把一些不符合文本框架或者有代碼錯誤的都進行了細致的修改， 保證了設計報告的質量。 從這次的程序設計中， 我學到了很多。認認真真做一件事情不會有錯， 用什么態度做什么事會得到什么樣的回報。并且我認為數據結果也不是很難的科目，認真花時間去琢磨一定不會落下很多。所以以后我會細致做事，并在閑暇時間補習功課，爭取盡快補習好原來的知識，再學習新的知識為自己充電。12六、程序附錄（源代碼）#include<iostream>#include<fstream>#incl

19、ude<stdlib.h>using namespace std;typedef char TElemType;#define MaxSize 1000int i;typedef struct BiTNodeTElemType date;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void Destory(BiTree &T);/函數聲明char input255;void Interface();void sjecs(BiTree &T);void jp(BiTree &T);/鍵盤void wj(BiTr

20、ee &T);/文件void CreateBiTree(BiTree &T);int Count(BiTree T);int Deep(BiTree T);void PreOrderTraverse(BiTree T);/先序void InOrderTraver(BiTree T);/中序void PostOrderTraver(BiTree T);/后序void ccbl(BiTNode *b);/層次遍歷void blxljm();void locate(BiTree T,char x);void main()/主函數Interface();BiTree T=NULL;bo

21、ol End=false;char sel;13char x;int p=1;int q=1;doInterface();fflush(stdin);char select=cin.get();system("cls");switch(select)case'1':cout<<" 創建二叉樹： n"sjecs(T);break; case'2': cout<<"nt遍歷序列 n"doblxljm();cout<<"n選擇： "fflush(stdi

22、n);sel=cin.get();p=1;switch(sel)case'1':cout<<"n先序遍歷二叉樹的輸出順序：n"PreOrderTraverse(T);cout<<"n"system("pause");system("cls");break;case'2':cout<<"n中 序 遍 歷 二 叉 樹 的 輸 出 順 序 ：n"InOrderTraver(T);cout<<"n"sys

23、tem("pause");system("cls");break;case'3':cout<<"n后 序 遍 歷 二 叉 樹 的 輸 出 順 序 ：n"PostOrderTraver(T);cout<<"n"system("pause");system("cls");break ;case'4':cout<<"n層 次 遍 歷 二 叉 樹 的 輸 出 順 序 ： n"ccbl(T);cou

24、t<<"n"system("pause");system("cls");break;case'5': p=0;while(p);break;case'3': do system("cls");q=1;14cout<<"n-結點的孩子信息：-n"cout<<"（如果節點不存在 , 不返回任何信息，按任意鍵返回子菜單） n"cout<<"輸入要查找的節點： "cin>>

25、x;locate(T,x);system("pause");system("cls");cout<<"n-菜單信息： -n"cout<<"nt0.輸入返回主菜單 n"cout<<"t1.繼續查找節點 n"docout<<"t請選擇： "cin>>q;if(q!=0&&q!=1) cout<<"輸入格式不對請重新輸入n"while(q!=0&&q!=1);

26、while(q);break;case'4':End=true;system("pause");while(!End);void locate(BiTree T,char x) /在二叉樹 T 中查找值為 x 的節點BiTree p;p=T;if(T=NULL) return;else if(T->date=x)cout<<p->date;if(T->lchild)cout<<"t"<<"節點的左孩子："<<T->lchild->date&l

27、t;<"n"else cout<<"t"<<"節點沒有左孩子 n"if(T->rchild)cout<<"t節點的右孩子："<<T->rchild->date<<"n"else cout<<"t"<<"節點沒有右孩子 n"else p=T->lchild;15if(p) locate(T->lchild,x);locate(T->r

28、child,x);void Interface()/菜單界面函數system("cls");cout<<"nt-遍歷序列 -n"cout<<"tt1.創建二叉樹 n"cout<<"tt2.遍歷序列 n"cout<<"tt3.結點的孩子信息 n"cout<<"tt4.退出系統 n"cout<<"tt請選擇（ 14）： "cout<<"nt-n"void b

29、lxljm()/遍歷序列界面函數system("cls");cout<<"nt-二叉樹-n"cout<<"t（如果沒創建二叉樹 , 不返回任何信息，按5 返回主菜單） n"cout<<"tt1.先序遍歷二叉樹 n"cout<<"tt2.中序遍歷二叉樹 n"cout<<"tt3.后序遍歷二叉樹 n"cout<<"tt4.層次遍歷二叉樹 n"cout<<"tt5.返回

30、主菜單 n"cout<<"tt請選擇（ 15）： "cout<<"nt-n"int Count(BiTree T)/計算節點數量if(T=NULL)return 0;return 1+Count(T->lchild)+Count(T->rchild);16int Deep(BiTree T)/計算二叉樹的度if(T=NULL)return 0;int u=Deep(T->lchild);int v=Deep(T->rchild);if(u>v)return (u+1);return (v+1

31、);void sjecs(BiTree &T)/選擇輸入模式 , 新建二叉樹bool End=false;if(T)Destory(T);T=NULL;cout<<" 請選擇輸入二叉樹序列模式：（ 1：鍵盤輸入 2. 文件輸入 3. 返回主菜單） "<<endl;dochar Selection=cin.get();switch( Selection)case'1': jp(T);break;case'2':wj(T);break;case'3':End=true;while (!End);vo

32、id jp(BiTree &T)/鍵盤輸入cout<<" 輸入按先序建立二叉樹結點序列:t"cout<<" 例如 :ABDECFHGIJn"cout<<" 輸入 :"cin>>input;int i=0;CreateBiTree(T);int num=Count(T);int deep=Deep(T);17cout<<"二叉樹創建成功！ n"cout<<"此二叉樹共有 "<<num<<&quo

33、t;個結點 n"cout<<"且該二叉樹的深度為： "<< deep<<"（按 3 返回主菜單界面）n"cout<<" 請輸入選項： "void wj(BiTree &T)/文件輸入ifstream fi("a.txt");if(!fi)cout<<"數據文件不存在！ n"exit(0);fi>>input;int i=0;CreateBiTree(T);int num=Count(T);int deep=Deep(T);cout<<"二叉樹創建成功！ n"cout<<"此二叉樹共有 "<<num<<"個結點 n"cout<<"且該二叉樹的深度為： "<< dee