樹的展示系統(tǒng)和二叉樹的轉(zhuǎn)換系統(tǒng)

1、數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計報告課題名稱： 樹的展示系統(tǒng)和二叉樹的轉(zhuǎn)換系統(tǒng) 專 業(yè)： 班 級： 姓 名： 指導(dǎo)教師： 成 績： 2011年12月30日目 錄1 前言-32需求分析-53概要設(shè)計（特殊功能）-54詳細(xì)設(shè)計-55源代碼及調(diào)試-56用戶使用說明及測試結(jié)果-197總結(jié)及分析-268 參考文獻(xiàn)-271.前言1.1 課題簡介本次我們選擇的課程設(shè)計的題目名稱是：樹的展示系統(tǒng)和二叉樹的轉(zhuǎn)換系統(tǒng)，這一題目。目的是為了，能讓自己的編程得到鍛煉，熟悉各種數(shù)據(jù)結(jié)構(gòu)的性質(zhì)，并學(xué)會合理地選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)來讓編出的程序更富有健壯性。這一題目，要實現(xiàn)，樹的生成，樹的顯示，二叉樹的顯示，二叉樹的遍歷。預(yù)期希望能夠?qū)崿F(xiàn)上

2、述基本功能。1.2 方案及其論證1.2.1系統(tǒng)平臺需求1. 系統(tǒng)開發(fā)平臺操作系統(tǒng)：Windows xp系列開發(fā)工具：Visual C+ 6.02. 開發(fā)環(huán)境介紹本次課程設(shè)計我們采用的是vc+6.0的編程環(huán)境.VC+是微軟公司開發(fā)的一個IDE(集成開發(fā)環(huán)境),換句話說,就是使用c+的一個開發(fā)平臺.有些軟件就是這個編出來的.vc+是Windows平臺上的C+編程環(huán)境，學(xué)習(xí)VC要了解很多Windows平臺的特性并且還要掌握MFC、ATL、COM等的知識，難度比較大。Windows下編程需要了解Windows的消息機制以及回調(diào)（callback）函數(shù)的原理；MFC是Win32API的包裝類，需要理解文

3、檔視圖類的結(jié)構(gòu)，窗口類的結(jié)構(gòu)，消息流向等等；COM是代碼共享的二進(jìn)制標(biāo)準(zhǔn)，需要掌握其基本原理等等。VC作為一個主流的開發(fā)平臺一直深受編程愛好者的喜愛，但是很多人卻對它的入門感到難于上青天，究其原因主要是大家對他錯誤的認(rèn)識造成的，嚴(yán)格的來說 VC+不是門語言，雖然它和C+之間有密切的關(guān)系,如果形象點比喻的話，可以C+看作為一種”工業(yè)標(biāo)準(zhǔn)”，而VC+則是某種操作系統(tǒng)平臺下的”廠商標(biāo)準(zhǔn)”,而”廠商標(biāo)準(zhǔn)”是在遵循”工業(yè)標(biāo)準(zhǔn)”的前提下擴展而來的。VC+應(yīng)用程序的開發(fā)主要有兩種模式，一種是WIN API方式，另一種則是MFC方式，傳統(tǒng)的WIN API開發(fā)方式比較繁瑣，而MFC則是對WIN API再次封裝，

4、所以MFC相對于WIN API開發(fā)更具備效率優(yōu)勢，但為了對WINDOWS開發(fā)有一個較為全面細(xì)致的認(rèn)識，筆者在這里還是以講解WIN API的相關(guān)內(nèi)容為主線。要想學(xué)習(xí)好VC必須具備良好的C/C+的基礎(chǔ)，必要的英語閱讀能力也是必不可少的，因為大量的技術(shù)文檔多以英文形式發(fā)布。vc6.0的優(yōu)點是界面簡潔，占用資源少，操作方便。系統(tǒng)功能結(jié)構(gòu)主要有四塊：樹的生成，樹的顯示，二叉樹的顯示，二叉樹的遍歷實現(xiàn)技術(shù)：運用這個學(xué)期學(xué)過的數(shù)據(jù)結(jié)構(gòu)的知識，與之前的知識相結(jié)合，在vc+ 6.0中進(jìn)行編程實現(xiàn)。1.2.2設(shè)計進(jìn)度安排:12.26號(星期一),地點：機房，布置任務(wù)，上網(wǎng)查找資料，分組和分工，選擇課題，和老師溝通

5、，確認(rèn)課題的目標(biāo)。學(xué)習(xí)課設(shè)范例，了解馬氏編程模板的特點與風(fēng)格。了解變量定義的細(xì)節(jié)。了解工作量和難度的要求。地點：機房 開始整體構(gòu)建，界面設(shè)計，功能設(shè)計。 馬春江12.27號(星期二), 上午：地點：機房，8:10到。開始編程，按照分工，自己完成自己的一部分。下午：地點：機房 繼續(xù)編程，實現(xiàn)各種細(xì)節(jié)。 梅琴12.28號(星期三), 上午：地點：寢室。各個組長開始通過電子郵件收集小組成員的作品，進(jìn)行集中聯(lián)調(diào)。下午：地點：寢室。小組成員在組長的計算機上觀摩和討論。改進(jìn)一些錯誤或者不完善的地方。各小組組長。12.29號(星期四), 上午： 地點；寢室。小組分工書寫開發(fā)報告。每個人需要提交一份報告，小組

6、還有另外一個小組開發(fā)報告。另外有一個宣講的PPT。小組成員交流，互相聽取個人報告，小組開發(fā)報告定稿。各小組組長12.30號(星期五), 上午：地點：寢室。組長為中心。做一些修改或驗收性完善。下午：地點：機房。2:30到。4:30之前驗收完畢。之后的算遲交。馬老師、梅老師。12.31號(星期六), 老師批改報告，查閱程序內(nèi)部編碼，電話或qq訪談個別小組成員或組長。結(jié)束批改，形成初步成績單。馬老師、梅老師。2需求分析所謂"需求分析"，是指對要解決的問題進(jìn)行詳細(xì)的分析，弄清楚問題的要求，包括需要輸入什么數(shù)據(jù)，要得到什么結(jié)果，最后應(yīng)輸出什么?？梢哉f，在軟件工程當(dāng)中的“需求分析”就是

7、確定要計算機“做什么”。1樹的生成（存儲結(jié)構(gòu)：雙指針鏈表 （兒子兄弟掛法）2樹的顯示3樹的層次遍歷4二叉樹的顯示5二叉樹的遍歷3概要設(shè)計（特殊功能）概要設(shè)計的主要任務(wù)是把需求分析得到的DFD轉(zhuǎn)換為軟件結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)。設(shè)計軟件結(jié)構(gòu)的具體任務(wù)是：將一個復(fù)雜系統(tǒng)按功能進(jìn)行模塊劃分、建立模塊的層次結(jié)構(gòu)及調(diào)用關(guān)系、確定模塊間的接口及人機界面等。數(shù)據(jù)結(jié)構(gòu)設(shè)計包括數(shù)據(jù)特征的描述、確定數(shù)據(jù)的結(jié)構(gòu)特性、以及數(shù)據(jù)庫的設(shè)計。顯然，概要設(shè)計建立的是目標(biāo)系統(tǒng)的邏輯模型，與計算機無關(guān)。本程序的目的就是實現(xiàn)樹的生成，樹的顯示，樹的層次遍歷，二叉樹的遍歷等基本功能，具體函數(shù)見第五部分的源程序4詳細(xì)設(shè)計詳細(xì)設(shè)計是軟件工程中軟件

8、開發(fā)的一個步驟，就是對概要設(shè)計的一個細(xì)化，就是詳細(xì)設(shè)計每個模塊實現(xiàn)算法，所需的局部結(jié)構(gòu)。我在這個程序中用的存儲結(jié)構(gòu)為：雙指針鏈表，主要是通過兒子、兄弟掛鏈法來來建立一棵樹，建立樹的時候我采用的是3種輸入，一，內(nèi)部預(yù)置；二，鍵盤輸入；三，文件讀入。3種輸入的形式是字符串型的，用的是廣義表形式，如：a(b,c(d,e),f)；通過鏈表遍歷方式的不同，我分別輸出了該樹的樹的顯示（廣義表的形式）、樹的顯示（凹入表示法）、樹的層次遍歷、以及該樹轉(zhuǎn)換成的二叉樹的顯示(凹入表示法)、二叉樹的顯示(廣義表的形式)、二叉樹的先根遍歷、二叉樹的中根遍歷、二叉樹的后根遍歷、二叉樹的層次遍歷。最后我通過釋放結(jié)點，進(jìn)行

9、銷毀這棵樹的操作。5源代碼及調(diào)試5.1源代碼 /* *2.樹的展示系統(tǒng)和二叉樹的轉(zhuǎn)換系統(tǒng) */#include "iostream.h"#include "stdlib.h"#include "windows.h"#include "string.h"#include "stdio.h"#define Maxnum 30typedef struct BTreechar data;struct BTree *lchild,*rchild;BTNode;void Menu()cout<<

10、endl;cout<<"=>>=>>=>>=>>=>>=>>=>>=>>=>>=>>=>>=>>="<<endl;cout<<" <<程>>=<<序>>=<<相>>=<<關(guān)>>=<<信>>=<<息>> "<<endl; co

11、ut<<""<<endl; cout<<"程序功能： 樹的展示系統(tǒng)和二叉樹的轉(zhuǎn)換系統(tǒng) "<<endl; cout<<""<<endl; cout<<"指導(dǎo)教師： 馬春江、梅琴 "<<endl; cout<<" "<<endl;cout<<"1: 樹的生成 "<<endl;cout<<"2: 樹的顯示（廣義表的形式

12、） "<<endl;cout<<"3: 樹的顯示（凹入表示法） "<<endl;cout<<"4: 樹的層次遍歷 "<<endl; cout<<"5: 二叉樹的顯示(凹入表示法) "<<endl; cout<<"6: 二叉樹的顯示(廣義表的形式) "<<endl;cout<<"7: 二叉樹的先根遍歷 "<<endl;cout<<"8:

13、 二叉樹的中根遍歷 "<<endl;cout<<"9: 二叉樹的后根遍歷 "<<endl;cout<<"10:二叉樹的層次遍歷 "<<endl;cout<<"11:判斷樹是否為空 "<<endl;cout<<"12:銷毀整棵樹 "<<endl; cout<<"0: 退出系統(tǒng) "<<endl; cout<<"=>>=>

14、>=>>=>>=>>=>>=>>=>>="<<endl;void Show1(BTNode *bt)/凹入表示法輸出樹FILE *fp;BTNode *StMaxnum,*p;int SMaxnum,top=-1,n,i,width=4;if(fp=fopen("樹(凹入表示法).txt","at+")=NULL)printf("Cannot open file strike any key exit!");getchar();exit

15、(1);if(bt!=NULL)top+;Sttop=bt; /根結(jié)點入棧Stop=width;while(top>-1)p=Sttop;n=Stop;for(i=1;i<=n;i+)/n為顯示長寬cout<<" "fputc(' ',fp);cout<<p->data<<""<<endl;fputc(p->data,fp);fputc(' ',fp);fputc('n',fp);top-; if(p->rchild!=NULL)

16、top+;Sttop=p->rchild;Stop=n; /表示右子樹if(p->lchild!=NULL)top+;Sttop=p->lchild;Stop=n+width; /表示左子樹fputc('n',fp);fclose(fp);/生成樹void CreateBTree(BTNode *&bt,char *str)/樹的存儲（兒子兄弟掛鏈法）BTNode *StMaxnum,*p=NULL;int top=-1,k,j=0;char ch;bt=NULL;ch=strj;while(ch!='0')switch(ch)case

17、 '(': /左兒子top+;Sttop=p;k=1;break;case ')':if(k=0)top-;k=0;break;case ',': /右兒子if(k=0)k=2;break;else top+;Sttop=(BTNode *)malloc(sizeof(BTNode);Sttop=p;k=2;break;default:p=(BTNode *)malloc(sizeof(BTNode);p->data=ch;p->lchild=p->rchild=NULL;if(bt=NULL)bt=p;elseswitch(k

18、)case 1:Sttop->lchild=p;cout<<"將"<<p->data<<"掛在"<<Sttop->data<<"的兒子鏈上"<<endl; cout<<"此時構(gòu)建的樹為："<<endl;Show1(bt);break;case 2:Sttop->rchild=p;cout<<"將"<<p->data<<"掛在&

19、quot;<<Sttop->data<<"的兄弟鏈上"<<endl;cout<<"此時構(gòu)建的樹為："<<endl;Show1(bt);top-;break;j+;ch=strj;void LevelTree(BTNode *point)/樹的層次遍歷BTNode *p;BTNode *queMaxnum;/定義環(huán)狀隊列1BTNode *StMaxnum;/定義環(huán)狀隊列2int front,rear,front1,rear1;front=rear=-1;front1=rear1=-1;rea

20、r+;querear=point; /根結(jié)點指針入隊1while(front!=rear)front=(front+1)%Maxnum;p=quefront;cout<<p->data;if(p->rchild!=NULL)rear=(rear+1)%Maxnum; querear=p->rchild;if(p->lchild!=NULL)rear1=(rear1+1)%Maxnum;/左兒子入隊一 Strear1=p->lchild;if(p->rchild=NULL)if(front1!=rear1)/出對一進(jìn)隊二rear=(rear+1)%

21、Maxnum;front1=(front1+1)%Maxnum;querear=Stfront1;void Show(BTNode *tree)/樹的顯示（廣義表表示法）FILE *fp; BTNode *searchp1; BTNode *searchp30,*S30;int i=0,j=0,k=0;if(fp=fopen("樹(廣義表表示).txt","at+")=NULL)printf("Cannot open file strike any key exit!");getchar();exit(1); searchpi=tre

22、e; searchp1=tree;while(i>=0)while(searchp1!=NULL)cout<<searchp1->data;fputc(searchp1->data,fp);if(searchp1->rchild!=NULL)i+;searchpi=searchp1->rchild;if(searchp1->lchild!=NULL)cout<<"(" fputc('(',fp);j+;k+;Sj=searchp1;if(searchp1->rchild=NULL&&a

23、mp;searchp1->lchild=NULL&&k!=0)cout<<")"fputc(')',fp);while(j>1&&Sj->rchild=NULL)cout<<")"fputc(')',fp);j-;searchp1=searchp1->lchild;searchp1=searchpi;if(i!=0)cout<<","fputc(',',fp);i-;fputc('n

24、9;,fp);fclose(fp);void DispBTree(BTNode *bt)/顯示二叉樹(括號表示法)FILE *fp;if(fp=fopen("二叉樹(括號表示法).txt","at+")=NULL)printf("Cannot open file strike any key exit!");getchar();exit(1);if(bt!=NULL)cout<<bt->data;fputc(bt->data,fp);if(bt->lchild!=NULL|bt->rchild!=N

25、ULL)cout<<"("fputc('(',fp);DispBTree(bt->lchild);if(bt->rchild!=NULL)cout<<","fputc(',',fp);DispBTree(bt->rchild);cout<<")"fputc(')',fp);fputc('n',fp);fclose(fp);void DispBTree1(BTNode *bt)/凹入表示法輸出二叉樹FILE *fp;if

26、(fp=fopen("二叉樹(凹入表示法).txt","at+")=NULL)printf("Cannot open file strike any key exit!");getchar();exit(1);BTNode *StMaxnum,*p;int SMaxnum2,top=-1,n,i,width=4;char type;if(bt!=NULL)top+;Sttop=bt; /根結(jié)點入棧Stop0=width;Stop1=2; / 2表示的是根while(top>-1)p=Sttop;n=Stop0;switch(St

27、op1)case 0:type='L'break;case 1:type='R'break;case 2:type='B'break;for(i=1;i<=n;i+)/n為顯示長寬cout<<" "fputc(' ',fp);cout<<p->data<<"("<<type<<")"<<endl;fputc(p->data,fp);fputc('(',fp);fput

28、c(type,fp);fputc(')',fp);top-;if(p->rchild!=NULL)top+;Sttop=p->rchild;Stop0=n+width;Stop1=1; /1表示右子樹if(p->lchild!=NULL)top+;Sttop=p->lchild;Stop0=n+width;Stop1=0; /0表示左子樹fputc('n',fp);fclose(fp);void preorder(BTNode *point)/二叉樹的先根遍歷if(point!=NULL)cout<<point->dat

29、a; preorder(point->lchild);preorder(point->rchild);void inorder(BTNode *point)/二叉樹的中根遍歷if(point!=NULL)preorder(point->lchild);cout<<point->data;preorder(point->rchild);void postorder(BTNode *point)/二叉樹的后根遍歷if(point!=NULL)preorder(point->lchild);preorder(point->rchild);cout

30、<<point->data;void LevelOrder(BTNode *point)/二叉樹的層次遍歷BTNode *p;BTNode *queMaxnum;/定義環(huán)狀隊列int front,rear;front=rear=-1;rear+;querear=point;while(front!=rear)front=(front+1)%Maxnum;p=quefront;cout<<p->data;if(p->lchild!=NULL)rear=(rear+1)%Maxnum;querear=p->lchild;if(p->rchild

31、!=NULL)rear=(rear+1)%Maxnum;querear=p->rchild;void TreeEmpty(BTNode *tre)/判斷書是否為空if(tre=NULL)cout<<"樹為空，未創(chuàng)建！"<<endl;elsecout<<"樹已創(chuàng)建！為："<<endl;Show(tre);bool Destroy(BTNode * & pTree)if(pTree!=NULL)Destroy(pTree->lchild);Destroy(pTree->rchild);

32、delete pTree;pTree=NULL;return true;void main()int choice;char s="a(b,c(d(e,f(g),h),i),j)"BTNode *tre=NULL;while(1)Menu();cout<<"請選擇："<<endl;cin>>choice;if(!choice)break;switch(choice)case 1:cout<<endl<<endl;cout<<"=>>=>>=>&

33、gt;=>>=>>=>>=>>=>>=>>=>>=>>=>>="<<endl; cout<<" <<程>>=<<序>>=<<相>>=<<關(guān)>>=<<信>>=<<息>> "<<endl; cout<<""<<endl; cout<&l

34、t;"樹的生成"<<endl; cout<<" "<<endl;cout<<"1: 內(nèi)部預(yù)置 "<<endl; cout<<"2: 鍵盤輸入 "<<endl;cout<<"3: 文件讀入 "<<endl<<endl;cout<<"=>>=>>=>>=>>=>>=>>=>>=

35、>>="<<endl; cout<<endl<<endl;int ch;docin>>ch;while(ch<1|ch>3);switch(ch)case 1:cout<<"內(nèi)部預(yù)置的樹為："<<s<<endl;CreateBTree(tre,s);break;case 2:char s230;cout<<"請輸入樹表示成的廣義表（字符串）形如：a(b,c(d,e),f)"<<endl; cin>>s2

36、;CreateBTree(tre,s2);break;case 3:FILE *fp;char s330;if(fp=fopen ("樹.txt","r")=NULL)printf("打開錯誤！");while(!feof(fp)fgets(s3,100,fp);cout<<"文件讀入的樹為："<<s3<<endl;fclose(fp);CreateBTree(tre,s3);break;break;case 2:if(tre=NULL)cout<<"樹未創(chuàng)

37、建！請創(chuàng)建樹"<<endl;elseShow(tre);break;case 3:if(tre=NULL)cout<<"樹未創(chuàng)建！請創(chuàng)建樹"<<endl;elseShow1(tre);break;case 4:if(tre=NULL)cout<<"樹未創(chuàng)建！請創(chuàng)建樹"<<endl;elseLevelTree(tre);break;case 5:if(tre=NULL)cout<<"樹未創(chuàng)建！請創(chuàng)建樹"<<endl;elseDispBTree1(tre);break;case 6:if(tre=NULL)cout<<"樹未創(chuàng)建！請創(chuàng)建樹"<<endl;elseDispBTree(tre);break;case 7:if(tre=NULL)cout<<"樹未創(chuàng)建！請創(chuàng)建樹"<<endl;elsepreorder(tre);break;case 8:if(tre=NULL)cout<<&q