數(shù)據(jù)結(jié)構課程設計報告二叉樹

1、word湖南涉外經(jīng)濟學院課程設計報告課程名稱： 數(shù)據(jù)結(jié)構 報告題目： 二叉樹的根本操作 學生姓名： 肖琳桂、康政、張小東、張帆 所在學院： 信息科學與工程學院 專業(yè)班級： 軟工本1402 學生學號： 144300211、02、14、08 指導教師： 李春庭 .word2022 年 12 月 31 日課程設計任務書報告題目二叉樹的根本操作完成時間2周學生姓名肖琳桂 康政專業(yè)班級軟工本 1402指導教師李春庭職稱講師總體設計要求和主要功能設計一個程序，實現(xiàn)二叉樹的創(chuàng)立以及二叉樹的遍歷包括先序遍歷、中序遍歷、后序遍歷和層次遍歷，計算并輸出二叉樹的深度和結(jié)點個數(shù)，功能要求：1二叉樹以二叉鏈表存儲，結(jié)點

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

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

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

5、達能夠?qū)崿F(xiàn)前序遍歷，中序遍歷，后序遍歷，層次遍歷。以及能夠從輸入的數(shù)據(jù)中得知二叉樹的葉子結(jié)點的個數(shù)，二叉樹的深度。在此，二叉樹的每一個結(jié)點中必須包括：值域，左指針域，右指針域。我們抽象出以下問題：實現(xiàn)文件操作，運用文件輸入流，將已經(jīng)寫好二叉樹序列的txt文本文件，加載到程序中，實現(xiàn)文件創(chuàng)立二叉樹。然后采用鏈表存儲的方式遍歷二叉樹先序遍歷、中序遍歷、后序遍歷、層次遍歷。層次遍歷運用循環(huán)隊列的方法實現(xiàn)，需要重新定義隊頭和隊尾，以及隊列的最大長度，并且在屏幕上實現(xiàn)輸出顯示。2功能要求(1)用菜單的形式實現(xiàn)操作界面，提供14個功能選項，功能分別為創(chuàng)立二叉樹、遍歷序列、節(jié)點的孩子信息、退出系統(tǒng)。(2)創(chuàng)

6、立二叉樹。要求用文件讀取和鍵盤輸入兩種不同的方式實現(xiàn)二叉樹的創(chuàng)立。二級菜單說明，輸出創(chuàng)立二叉樹的深度及結(jié)點數(shù)，假設失敗那么有相應提示。(3)遍歷序列。顯示先序，中序，后序和層次遍歷結(jié)果。先序遍歷、中序遍歷、后序遍歷用遞歸的方法實現(xiàn)遍歷。層次遍歷，用循環(huán)隊列的方法實現(xiàn)。(4)每次實現(xiàn)一項操作之后，要有相應的提示返回菜單。二、概要設計1.總體設計圖主菜單遍歷序列創(chuàng)立二叉樹節(jié)點的孩子信息退出系統(tǒng)鍵盤輸入文件輸入中序遍歷后序遍歷層次遍歷先序遍歷2.數(shù)據(jù)結(jié)構設計 數(shù)據(jù)元素為字符，邏輯結(jié)構為樹形結(jié)構，存儲結(jié)構為二叉鏈式存儲，系統(tǒng)操作的數(shù)據(jù)元素主要是創(chuàng)立一個二叉樹，遍歷序列。3.算法設計本系統(tǒng)主要用到的算法

7、有先序遍歷、中序遍歷、后序遍歷、層次遍歷、創(chuàng)立二叉樹和查找節(jié)點。從子菜單界面只能返回到主菜單界面，而不是退出程序。4.主要模塊及模塊之間的關系 運行程序后直接進入“菜單主界面模塊，菜單顯示分為4個模塊，14分別為創(chuàng)立二叉樹、遍歷序列、節(jié)點的孩子信息、退出系統(tǒng)。主界面中的各個模塊都是獨立運行，每完成一項操作后，返回主菜單模塊。通過相應定義的函數(shù)外部接口實現(xiàn)，內(nèi)部數(shù)據(jù)的改變由模塊內(nèi)部完成。三、詳細設計1.結(jié)構體或類設計typedef char TElemType;typedef struct BiTNodeTElemType date;struct BiTNode *lchild,*rchild;

8、BiTNode,*BiTree;2. 主要模塊實現(xiàn)的流程圖開始主菜單界面輸入選擇14 Case=sel？退出系統(tǒng)創(chuàng)立二叉樹遍歷序列中序遍歷層次遍歷先序遍歷后序遍歷結(jié)點的孩子信息Case=1Case=2Case=4Case=33.算法設計先序遍歷：void PreOrderTraverse(BiTree T) if(T) coutdate;PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); 中序遍歷：void InOrderTraver(BiTree T) if(T) InOrderTraver(T-lchild);coutdate;In

9、OrderTraver(T-rchild); 后序遍歷：void PostOrderTraver(BiTree T) if(T) PostOrderTraver(T-lchild);PostOrderTraver(T-rchild);coutdate; 層次遍歷： void ccbl(BiTNode *b) BiTNode *p; BiTNode *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+

10、1)%MaxSize; qh=p-lchild; if(p-rchild!=NULL) h=(h+1)%MaxSize; qh=p-rchild; 四、測試運行1登錄和主界面運行效果圖2運行說明主程序運行后，直接到菜單項選擇擇界面。其中有(14個選項可以選擇)1.創(chuàng)立二叉樹 2.遍歷序列 3.節(jié)點的孩子信息 4.退出系統(tǒng)。除退出以外,每個功能模塊運行完后，返回到主菜單界面，每個界面相互獨立。3. 運行效果圖表 學生情況統(tǒng)計表序號姓名性別出生日期學號專業(yè)聯(lián)系 備注1康政男1994.12144300202軟件工程組長2肖琳桂男1996.08144300211軟件工程3張小東男1994.071443

11、00214軟件工程 4張帆 男1995.08144300208軟件工程五、結(jié)論與心得1.總體評價在此次的課程設計中，由于不夠細心，在程序設計中犯了一些錯誤，花了挺多的時間。但是經(jīng)過一番思考并且在老師的幫助下，找到了導致程序錯誤的原因，經(jīng)過幾次修改和調(diào)試，程序能正常運行，并且能夠完成課程設計任務中的大局部功能。同時在此次的課程設計中讓我更深刻的了解了二叉樹的根本操作，增加了對專業(yè)只是學習的興趣。我想在以后的學習中，我們會繼續(xù)努力，希望在計算機方面有好的成績，也感謝老師給我們這次課程設計的時機，讓我們認識到了自身的缺乏，讓我們能夠不斷地完善自己!2. 所做的工作及體會肖琳桂：編寫程序和課程設計報告

12、。課程設計中我主要擔任程序設計的編寫和設計報告的編寫工作，經(jīng)過兩個星期的上機實踐學習，使我對數(shù)據(jù)結(jié)構有了更進一步的認識和理解，也知道了要想學好它要重在實踐，要通過不斷的上機操作才能更好地學習它。通過實踐我發(fā)現(xiàn)我的很多缺乏之處，然感覺理論上已經(jīng)掌握，但在運用到實踐的過程中仍有意想不到的困惑，因為自己對知識點的掌握不夠熟悉，但通過學習有很大改良。在這次課程設計中使我知道了二又樹的先序、中序、后序、層次遍歷。同時，還包括了求二叉樹深度和結(jié)點個數(shù)，結(jié)點的孩子信息，以及對文件的操作，用文件讀取的方式實現(xiàn)對二叉樹的建立。充分掌握樹的根本操作，以及對線性存儲結(jié)構的理解。也培養(yǎng)了我如何去把握一件事情，如何去做

13、一件事情，又如何完成一件事情的方法和技巧。在設計過程中，和同學們相互探討，相互學習，相互監(jiān)督。我學會了運籌帷幌，學會了寬容，學會了理解，也學會了做人與處世，這次課程設計對找來說受益良多。在今后的日子里，我會認真對待每一件事情，爭取做到最好，努力將知識與實踐相結(jié)合，不斷穩(wěn)固，加深所學的知識，做到學以致用。另外感謝老師的細心教導，以及同學們的幫助。康政：編寫程序和課程設計報告。我在小組中做了編寫程序和撰寫報告的工作。在編寫程序時，遇到很多困難，例如缺少聲明，調(diào)用函數(shù)錯誤等等。通過網(wǎng)上搜查，查詢資料以及老師的指點幫助，完成了很多任務。作為根底不是很好的學生，我在克服自己知識缺乏的過程中也在努力學習新

14、的知識，運用不同的原理編寫出不同的算法。也學習到，算法不能盲目抄襲，很多東西是不同的，必須通過自己的思考和努力的鉆研才能寫出一套完整的代碼，不可心急，越是急越不可能精細的完成任務。撰寫報告的時候，很多地方因細節(jié)問題處理不好導致出了大大小小很多漏洞，不能很精細的完成指定的任務。從中我也明白了，做一件事，尤其是耗時的編寫程序的問題，不能心急也不能馬虎，也許一點點出錯整個程序就會崩潰，還要重新一點點的檢查才能找出問題，大大降低了辦事效率。所以，今后要做的第一件事是慢慢穩(wěn)固檢出，打好根基。第二件事是沉下心來認真做事，不能毛手毛腳，從頭到尾認真細致的做下去，防止出錯惹出更多的麻煩。這次的程序設計使我受益

15、匪淺，學到了很多，做了很多。希望以后可以更多的做這種任務，穩(wěn)固知識，學習新的知識，有了這些經(jīng)驗可以做的更好。張小東：查找資料和打印。這次我在小組中做的事情是查詢資料和打印排版。雖然因為我的專業(yè)底子差一點，現(xiàn)在暫時只能在程序設計時查找一些需要用到的專業(yè)資料，幫助組員完成設計，但我相信下一次我不會僅此于此。這次程序設計我的收獲還是很大了，讓我懂得了學好專業(yè)知識，并不是自己想象中的難，而是你自己是否去努力了。在查找資料的過程中，我是邊查邊學自己不會的知識點。查找途中也遇到了一些當時不能理解的知識點，但經(jīng)過同學的細心解答，最后一些難掌握的知識點都被根本掌握。這讓我懂得編程過程需要很大的耐心，而且要有良

16、好的思維和扎實的專業(yè)根底知識，所以我需要努力的學習，發(fā)現(xiàn)自身缺乏之處并努力改正他，逐步提高自身的能力，不斷取得進步。通過這次課程設計，我認識到知識運用的重要性，并且努力加深對根底知識的理解，從中了解自己需要學習的東西并學會自學。作為一名計算機專業(yè)的學生，今后我會加緊學習，學好專業(yè)知識，為將來打下堅實的根底。張帆：查找資料和打印。這次我在小組中做的事情是查詢資料，打印排版。雖然這些工作并不是主要任務，但是我用心對待，認真為做程序的同學查找資料，為他們挑選所需要的代碼以及算法，及時反應給他們信息。因為根底不是很好，經(jīng)常會剪裁到一些不是很適宜的代碼，我們通過共同分析，共同篩選，最終也獲得了很多收獲。

17、通過和他們一起分析代碼，我也漲了很多知識。懂的了二叉樹的算法，數(shù)據(jù)類型等等。報告的排版也是一項需要耐心的工作，通過晚上的時間，我認認真真的對所寫的設計報告進行了排版，把一些不符合文本框架或者有代碼錯誤的都進行了細致的修改，保證了設計報告的質(zhì)量。從這次的程序設計中，我學到了很多。認認真真做一件事情不會有錯，用什么態(tài)度做什么事會得到什么樣的回報。并且我認為數(shù)據(jù)結(jié)果也不是很難的科目，認真花時間去琢磨一定不會落下很多。所以以后我會細致做事，并在閑暇時間補習功課，爭取盡快補習好原來的知識，再學習新的知識為自己充電。六、程序附錄源代碼#include#include#includeusing namesp

18、ace std;typedef char TElemType;#define MaxSize 1000 int i;typedef struct BiTNodeTElemType date;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void Destory(BiTree &T);/函數(shù)聲明char input255;void Interface();void sjecs(BiTree &T);void jp(BiTree &T);/鍵盤void wj(BiTree &T);/文件void CreateBiTree(BiTree &T);int

19、 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()/主函數(shù)Interface();BiTree T=NULL;bool End=false;char sel;char x;int p=1;int q=1;doInt

20、erface();fflush(stdin);char select=cin.get();system(cls);switch(select)case1:cout創(chuàng)立二叉樹：n;sjecs(T);break;case2: coutnt遍歷序列n;doblxljm();coutn選擇：;fflush(stdin);sel=cin.get();p=1;switch(sel)case1:coutn先序遍歷二叉樹的輸出順序：n;PreOrderTraverse(T);coutn;system(pause);system(cls);break;case2: coutn中序遍歷二叉樹的輸出順序：n;InO

21、rderTraver(T);coutn;system(pause);system(cls);break; case3: coutn后序遍歷二叉樹的輸出順序：n;PostOrderTraver(T);coutn;system(pause);system(cls);break; case4: coutn層次遍歷二叉樹的輸出順序：n; ccbl(T);coutn;system(pause);system(cls);break; case5: p=0;while(p);break;case3: do system(cls);q=1;coutn-結(jié)點的孩子信息：-n; cout如果節(jié)點不存在,不返回任何

22、信息，按任意鍵返回子菜單n; coutx; locate(T,x);system(pause);system(cls); coutn-菜單信息：-n;coutnt0.輸入返回主菜單n;coutt1.繼續(xù)查找節(jié)點n;docoutq;if(q!=0&q!=1) coutdate=x) coutdate; if(T-lchild)coutt節(jié)點的左孩子：lchild-daten;else couttrchild)coutt節(jié)點的右孩子：rchild-daten;else couttlchild;if(p) locate(T-lchild,x);locate(T-rchild,x);void Inte

23、rface()/菜單界面函數(shù)system(cls);coutnt-遍歷序列-n;couttt1.創(chuàng)立二叉樹n;couttt2.遍歷序列n;couttt3.結(jié)點的孩子信息n;couttt4.退出系統(tǒng)n;couttt請選擇14：;coutnt-n;void blxljm()/遍歷序列界面函數(shù)system(cls);coutnt-二叉樹-n; coutt如果沒創(chuàng)立二叉樹,不返回任何信息，按5返回主菜單n;couttt1.先序遍歷二叉樹n;couttt2.中序遍歷二叉樹n;couttt3.后序遍歷二叉樹n;couttt4.層次遍歷二叉樹n;couttt5.返回主菜單n;couttt請選擇15：;cou

24、tlchild)+Count(T-rchild);int Deep(BiTree T)/計算二叉樹的度if(T=NULL)return 0;int u=Deep(T-lchild);int v=Deep(T-rchild);if(uv)return (u+1);return (v+1);void sjecs(BiTree &T)/選擇輸入模式,新建二叉樹bool End=false;if(T)Destory(T);T=NULL;cout請選擇輸入二叉樹序列模式：1：鍵盤輸入 2.文件輸入 3.返回主菜單endl;dochar Selection=cin.get();switch( Select

25、ion)case1: jp(T);break;case2:wj(T);break;case3:End=true;while (!End);void jp(BiTree &T)/鍵盤輸入cout輸入按先序建立二叉樹結(jié)點序列:t;cout例如:ABDECFHGIJn;coutinput;int i=0;CreateBiTree(T);int num=Count(T);int deep=Deep(T);cout 二叉樹創(chuàng)立成功！n;cout 此二叉樹共有num個結(jié)點n;cout 且該二叉樹的深度為： deep 按3返回主菜單界面n;cout請輸入選項：;void wj(BiTree &T)/文件輸入 ifstream fi(a.txt);if(!fi)coutinput;int i=0;CreateBiTree(T);int num=Count(T);int deep=Deep(T);cout 二叉樹創(chuàng)立成功！n;cout 此二叉樹共有num個結(jié)點n;cout 且該二叉樹