數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-二叉排序樹(shù)的簡(jiǎn)單應(yīng)用報(bào)告

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：15 大?。?41.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-二叉排序樹(shù)的簡(jiǎn)單應(yīng)用報(bào)告_第1頁(yè)

已閱讀1頁(yè)，還剩14頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說(shuō)明：本文檔由用戶(hù)提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)　　設(shè)計(jì)說(shuō)明書(shū)　　起止日期：2012 年 12 月 22 日至 2013 年 01 月 02日　　年月日　　目

2、錄　　一、問(wèn)題描述1　　二、測(cè)試數(shù)據(jù)1　　三、算法思想1　　四、模塊劃分1</p&g

3、t;　　五、數(shù)據(jù)結(jié)構(gòu)2　　六、源程序2　　七、測(cè)試情況7　　八、設(shè)計(jì)體會(huì)及今后的改進(jìn)意見(jiàn)8　　參考文獻(xiàn)

4、9　　一、問(wèn)題描述　　1)具體問(wèn)題描述　　輸入樹(shù)的各個(gè)結(jié)點(diǎn)，建立排序二叉樹(shù)，對(duì)建立的排序二叉樹(shù)進(jìn)行層次、先序、中序和后序遍歷并統(tǒng)計(jì)該二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目等。

5、;　　2)基本要求　　(1)用菜單實(shí)現(xiàn)　　(2)能夠輸入樹(shù)的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列和葉子結(jié)點(diǎn)的數(shù)目。　　二、測(cè)試數(shù)據(jù)　?。?）關(guān)鍵字序列為（45,24，5

6、3,12,37,93）　?。?）關(guān)鍵字序列為（44,10,50,3,33,100,22,61,90,78）　　三、算法思想　　因?yàn)槎媾判驑?shù)的操作要根據(jù)結(jié)點(diǎn)的關(guān)鍵字域來(lái)進(jìn)行，所以，首先要定義每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域類(lèi)型。二叉排序樹(shù)的遍歷算法和二叉樹(shù)類(lèi)似，利用鏈表存儲(chǔ)二叉樹(shù)，用隊(duì)列實(shí)現(xiàn)

7、層次遍歷，利用棧進(jìn)行非遞歸中序遍歷二叉樹(shù)，所以在創(chuàng)建二叉排序樹(shù)之前，定義二叉鏈表的存儲(chǔ)表示，對(duì)隊(duì)列、棧進(jìn)行定義。　　二叉排序樹(shù)的創(chuàng)建是從空的二叉排序樹(shù)開(kāi)始，每輸入一個(gè)結(jié)點(diǎn)，經(jīng)過(guò)查找操作（二叉排序樹(shù)插入的基本過(guò)程是查找），，將新的結(jié)點(diǎn)插入到當(dāng)前二叉排序樹(shù)的合適位置。首先將二叉排序樹(shù)T初始化為空樹(shù)，讀入一個(gè)關(guān)鍵字為key的結(jié)點(diǎn)，將此結(jié)點(diǎn)插入到二叉排序樹(shù)T中，重復(fù)執(zhí)行，直至讀入的關(guān)鍵字key是輸入結(jié)

8、束標(biāo)志。　　根據(jù)開(kāi)始定義好的隊(duì)列的定義、操作，用隊(duì)列實(shí)現(xiàn)層次遍歷；按先序次序輸入二叉樹(shù)中結(jié)點(diǎn)的值（一個(gè)字符），創(chuàng)建二叉鏈表表示的二叉樹(shù)T；分別輸入先序遍歷二叉樹(shù)T的遞歸算法、中序遍歷二叉樹(shù)T的遞歸算法、后序遍歷二叉樹(shù)T的遞歸算法；利用棧進(jìn)行非遞歸中序遍歷二叉樹(shù)，非空根指針進(jìn)棧，遍歷左子樹(shù)，為空根指針退棧,訪(fǎng)問(wèn)根結(jié)點(diǎn),遍歷右子樹(shù)；遞歸查找葉子數(shù)，左子樹(shù)的葉子數(shù)加上右葉子數(shù)，可以計(jì)算出二叉樹(shù)的葉子數(shù)

9、　　四、模塊劃分　?。?）二叉排序樹(shù)的操作要根據(jù)結(jié)點(diǎn)的關(guān)鍵字域來(lái)進(jìn)行，其中包括基本操作的函數(shù)有：用隊(duì)列實(shí)現(xiàn)層次遍歷操作函數(shù)、先序遍歷有序二叉樹(shù)T的遞歸算法、中序遍歷有序二叉樹(shù)T的遞歸算法、后序遍歷有序二叉樹(shù)T的遞歸算法、用棧實(shí)現(xiàn)非遞歸中序遍歷有序二叉樹(shù)T的算法、求有序二叉樹(shù)的葉子數(shù)，該抽象數(shù)據(jù)類(lèi)型文件名為BSTree

10、.h。　　（2）void InsertBST(BSTree &T,ElemType e )，其功能是向二叉樹(shù)插入新的結(jié)點(diǎn)。　?。?）void CreateBST(BSTree &T )，其功能是創(chuàng)建有序二叉樹(shù)。　?。?）void lev_traverse(BSTree T)，其功能是用隊(duì)列實(shí)現(xiàn)有序

11、二叉樹(shù)的層次遍歷。　?。?）void PreOrderTraverse(BSTree T)，其功能是實(shí)現(xiàn)有序二叉樹(shù)T的遞歸先序遍歷。　?。?）void InOrderTraverse(BSTree &T)，其功能是實(shí)現(xiàn)有序二叉樹(shù)T的遞歸中序遍歷。　　（7）void PostOrderTraverse(BS

12、Tree T)，其功能是實(shí)現(xiàn)有序二叉樹(shù)T的遞歸后序遍歷。　?。?）void InOrderTraverses(BSTree T)，其功能是實(shí)現(xiàn)有序二叉樹(shù)T的非遞歸中序遍歷。　?。?）int leaf(BSTree T)，其功能是求有序二叉樹(shù)的葉子數(shù)。　?。?0）void main()，主函數(shù)，其功能是建立二叉排序

13、樹(shù)，調(diào)用以上函數(shù)對(duì)建立的排序二叉樹(shù)進(jìn)行層次、先序、中序和后序遍歷并統(tǒng)計(jì)該二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。　　五、數(shù)據(jù)結(jié)構(gòu)　?。?）二叉排序樹(shù)的操作里每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域的類(lèi)型定義（包括關(guān)鍵字項(xiàng)和其他數(shù)據(jù)項(xiàng)）　　typedef struct ElemType{&l

14、t;p>　　int key; //關(guān)鍵字項(xiàng)　　}ElemType;　　typedef struct BSTNode{　　ElemType data;//每個(gè)結(jié)點(diǎn)數(shù)據(jù)域包括關(guān)鍵字項(xiàng)和其他數(shù)據(jù)項(xiàng)　　struct BSTNode *lchild,*rchild;

15、//左右孩子指針　　}BSTNode,*BSTree;　　六、源程序　　源程序存放在文件BSTree.h中　　文件BSTree.h：　　#include<iostream><

16、/p>　　using namespace std;　　typedef int Status;　　#define OVERFLOW -2　　#define OK 1　　#define TRUE 1

17、#define FALSE 0 　　#define ERROR 0　　#define MAXQSIZE 100 //最大隊(duì)列長(zhǎng)度　　typedef struct ElemType{　　int key;

18、;　　}ElemType;　　typedef struct BSTNode{　　ElemType data;//結(jié)點(diǎn)數(shù)據(jù)域　　struct BSTNode *lchild,*rchild;//左右孩子指針　　}BSTNode,*BSTree;&l

19、t;/p>　　//隊(duì)列定義　　typedef struct{ 　　BSTree *base; //初始化的動(dòng)態(tài)分配存儲(chǔ)空間的基礎(chǔ) 　　int front; //隊(duì)頭指針&l

20、t;p>　　int rear; //隊(duì)尾指針　　}SqQueue; //順序隊(duì)列的類(lèi)型名　　//棧的定義　　typedef struct

21、　　{ 　　BSTree *base;　　BSTree *top;　　int stacksize;　　}SqStack;<b&

22、gt;　　//隊(duì)列的基本操作　　Status InitQueue(SqQueue &Q) //隊(duì)列的初始化　　{　　Q.base=new BSTree[MAXQSIZE];　　if(!Q.base) ex

23、it(OVERFLOW);　　Q.front=Q.rear=0;　　return OK;　　}　　Status EnQueue(SqQueue &Q,BSTree p) //入隊(duì)函數(shù)&

24、lt;b>　　{　　if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR;　　Q.base[Q.rear]=p;　　Q.rear=(Q.rear+1)%MAXQSIZE;　　return OK;</

25、p>　　}　　Status DeQueue(SqQueue &Q,BSTree &p) //出隊(duì)函數(shù)　　{　　if(Q.front==Q.rear) return ERROR;</p&

26、gt;　　p=Q.base[Q.front];　　Q.front=(Q.front+1)%MAXQSIZE;　　return OK;　　}　　//棧的基本操作</p&g

27、t;　　Status InitStack(SqStack &S) //棧的初始化　　{　　S.base=new BSTree[MAXQSIZE];　　if(!S.base) exit(OVERFLOW);<p&g

28、t;　　S.top=S.base;　　S.stacksize=MAXQSIZE;　　return OK;　　}　　Status Push(SqStack &S, BSTree P) //入棧<

29、;p>　　{ 　　if (S.top-S.base==S.stacksize) return ERROR;　　*S.top++=P;　　return OK;　　}&

30、lt;p>　　Status Pop(SqStack &S , BSTree &q) //出棧　　{ 　　if (S.top==S.base) 　　return ERROR;　　q=*--S.top;<

31、;/p>　　return OK;　　}　　Status StackEmpty(SqStack &S) //判?？?lt;/p>　　{ 　　if(S.top==S.b

32、ase) 　　return TRUE;　　else　　return FALSE;　　}　　//　二叉排序樹(shù)的插入<p&g

33、t;　　void InsertBST(BSTree &T,ElemType e ) {　　//當(dāng)二叉排序樹(shù)T中不存在關(guān)鍵字等于e.key的數(shù)據(jù)元素時(shí)，則插入該元素　　if(!T) { //找到插入位置，遞歸結(jié)束　　BSTree S = new BSTNode;

34、 //生成新結(jié)點(diǎn)*S　　S->data = e; //新結(jié)點(diǎn)*S的數(shù)據(jù)域置為e 　　S->lchild = S->rchild = NULL;//新結(jié)點(diǎn)*S作為葉子結(jié)點(diǎn)　　T =S; //把新結(jié)點(diǎn)*S鏈接

35、到已找到的插入位置　　}　　else if (e.key< T->data.key) 　　InsertBST(T->lchild, e );//將*S插入左子樹(shù)　　else if (e.key> T-&g

36、t;data.key) 　　InsertBST(T->rchild, e);//將*S插入右子樹(shù)　　}// InsertBST　　//　二叉排序樹(shù)的創(chuàng)建　　void CreateBST(BSTree &T ) {

37、;　　//依次讀入一個(gè)關(guān)鍵字為key的結(jié)點(diǎn)，將此結(jié)點(diǎn)插入二叉排序樹(shù)T中　　T=NULL;　　ElemType e;　　cin>>e.key; //???　　while(e.key!='\0')

38、{ //0作為輸入結(jié)束標(biāo)志　　InsertBST(T, e); //將此結(jié)點(diǎn)插入二叉排序樹(shù)T中　　cin>>e.key;//???　　}//while 　　}//CreatBST&l

39、t;p>　　void lev_traverse(BSTree T) /* 用隊(duì)列實(shí)現(xiàn)層次遍歷 */　　{ 　　SqQueue q;　　BSTNode *p;　　InitQueue(q);&l

40、t;p>　　p=T;　　EnQueue(q,p);　　while(!(q.rear==q.front))　　{ /* 當(dāng)隊(duì)列不空 */　　DeQueue(q,p);　　printf(&q

41、uot;%d ",p->data);　　if(p->lchild!=NULL)　　EnQueue(q,p->lchild);　　if(p->rchild!=NULL)　　EnQueue(q,p->rchild);

42、　　}　　}　　void PreOrderTraverse(BSTree T) //先序遍歷二叉樹(shù)T的遞歸算法　　{ <b&

43、gt;　　if(T)　　{　　cout << T-> data.key;　　PreOrderTraverse(T->lchild);　　PreOrderTraverse(T->rchi

44、ld);　　}　　}　　//中序遞歸遍歷　　void InOrderTraverse(BSTree &T)&

45、lt;b>　　{　　if(T)　　{　　InOrderTraverse(T->lchild);　　cout<<T-> data.key;</

46、p>　　InOrderTraverse(T->rchild);　　}　　}　　void PostOrderTraverse(BSTree T)//后序遍歷二叉樹(shù)T的遞歸算法<

47、p>　　{ 　　if(T)　　{　　PostOrderTraverse(T->lchild);　　PostOrderTraverse(T->

48、;rchild);　　cout << T->data.key;　　}　　}　　void InOrderTraverses(BSTree T) //非遞歸中序遍歷二叉樹(shù)<

49、/p>　　{ SqStack S;　　BSTree p;　　BSTree q=new BSTNode;　　InitStack (S); p=T;　　while(p||!StackEmpty(S))<

50、;/p>　　{ if(p) 　　{Push(S,p);// p 非空根指針進(jìn)棧，遍歷左子樹(shù)　　p=p->lchild;} 　　else　　{ Po

51、p(S,q); //p 為空根指針退棧,訪(fǎng)問(wèn)根結(jié)點(diǎn),遍歷右子樹(shù)　　cout<<q->data.key;　　p=q->rchild;}　　}　　} // while

52、int leaf(BSTree T) //求二叉樹(shù)的葉子數(shù)　　{if (T==NULL) 　　return 0;　　else 　　{ if (T->lchild==NULL&&T->rchild==

53、NULL) 　　return 1;　　else　　return leaf(T->lchild)+leaf(T->rchild);　　}

54、return 0; //完成函數(shù)后請(qǐng)刪除此行　　}　　void main()　　{　　BSTree T;　　cou

55、t<<"請(qǐng)輸入若干字符，用回車(chē)區(qū)分，以0結(jié)束輸入"<<endl;　　CreateBST(T);　　cout<<"當(dāng)前有序二叉樹(shù)層次遍歷結(jié)果為: \n";　　lev_traverse(T);cout<<"\n"

56、;;　　cout<<"當(dāng)前有序二叉樹(shù)先序遍歷結(jié)果為: \n";　　PreOrderTraverse(T);cout<<"\n";　　cout<<"當(dāng)前有序二叉樹(shù)遞歸中序遍歷結(jié)果為: \n";&l

57、t;p>　　InOrderTraverse(T);cout<<"\n";　　cout<<"當(dāng)前有序二叉樹(shù)后序遍歷結(jié)果為: \n";　　PostOrderTraverse(T);cout<<"\n";　　cout&

58、lt;<"當(dāng)前有序二叉樹(shù)非遞歸中序遍歷：\n";　　InOrderTraverses(T);cout<<"\n";　　cout<<"二叉樹(shù)的葉子數(shù)："<<leaf(T);cout<<"\n";<

59、;p>　　cout<<endl;　　}　　七、測(cè)試情況　　測(cè)試數(shù)據(jù)（1）關(guān)鍵字序列為（45,24，53,12,37,93）的程序輸出為：　　測(cè)試數(shù)據(jù)（2）關(guān)鍵字序列為（44,10

60、,50,3,33,100,22,61,90,78）　　的程序輸出為：　　經(jīng)檢驗(yàn)，得出輸出的結(jié)果是正確的。　　八、設(shè)計(jì)體會(huì)及今后的改進(jìn)意見(jiàn)　　通過(guò)這次課程設(shè)計(jì)，我對(duì)數(shù)據(jù)結(jié)構(gòu)中二叉排序樹(shù)及二叉樹(shù)的知識(shí)掌握地更加熟練，包括如何運(yùn)用隊(duì)列實(shí)現(xiàn)二

61、叉排序樹(shù)的層次遍歷，利用棧進(jìn)行非遞歸中序遍歷二叉排序樹(shù)，對(duì)二叉排序樹(shù)的先序遍歷、中序遍歷、后序遍歷方法了解得更加深入，掌握了二叉排序樹(shù)能實(shí)現(xiàn)的一些基本操作。　　此外，在熟悉課本知識(shí)的同時(shí)，學(xué)會(huì)自主學(xué)習(xí)課外知識(shí)，課外知識(shí)與課本的知識(shí)相結(jié)合，實(shí)現(xiàn)算法的補(bǔ)充、創(chuàng)新。遇到疑問(wèn)時(shí)，老師、同學(xué)會(huì)熱心的幫我解答，備感溫暖。然而也認(rèn)識(shí)到自己對(duì)數(shù)據(jù)結(jié)構(gòu)課程的學(xué)習(xí)仍不夠深入，仍需進(jìn)一步研究。另外也發(fā)現(xiàn)了自己的許多不

62、足之處：本程序設(shè)計(jì)僅能夠?qū)崿F(xiàn)二叉排序樹(shù)的一些基本操作，算法比較簡(jiǎn)單。若想用此程序解決生活中的實(shí)際問(wèn)題，還需另外增加、修改一些程序，這個(gè)方面有待加強(qiáng)。在未來(lái)通過(guò)對(duì)數(shù)據(jù)結(jié)構(gòu)更深入地學(xué)習(xí)，提高自己的能力，靈活運(yùn)用所學(xué)知識(shí)解決生活中的實(shí)際問(wèn)題。 　　參考文獻(xiàn)　　[1]譚浩強(qiáng)，C語(yǔ)言程序設(shè)計(jì).北京：清華大學(xué)出版社，200

眾賞文庫(kù)> 全部分類(lèi)> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-二叉排序樹(shù)的簡(jiǎn)單應(yīng)用報(bào)告

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-二叉排序樹(shù)的簡(jiǎn)單應(yīng)用報(bào)告

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載