數(shù)據(jù)結(jié)構(gòu)課程設計-二叉排序樹的簡單應用報告

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

數(shù)據(jù)結(jié)構(gòu)課程設計-二叉排序樹的簡單應用報告_第1頁

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

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

文檔簡介

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

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

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

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

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

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

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

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

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

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

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

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

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

14、t;p>　　int key; //關(guān)鍵字項　　}ElemType;　　typedef struct BSTNode{　　ElemType data;//每個結(jié)點數(shù)據(jù)域包括關(guān)鍵字項和其他數(shù)據(jù)項　　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 //最大隊列長度　　typedef struct ElemType{　　int key;

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

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

20、t;p>　　int rear; //隊尾指針　　}SqQueue; //順序隊列的類型名　　//棧的定義　　typedef struct

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

22、gt;　　//隊列的基本操作　　Status InitQueue(SqQueue &Q) //隊列的初始化　　{　　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) //入隊函數(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) //出隊函數(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;　　}　　//　二叉排序樹的插入<p&g

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

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

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

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

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

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

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

40、t;p>　　p=T;　　EnQueue(q,p);　　while(!(q.rear==q.front))　　{ /* 當隊列不空 */　　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) //先序遍歷二叉樹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)//后序遍歷二叉樹T的遞歸算法<

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

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

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 非空根指針進棧，遍歷左子樹　　p=p->lchild;} 　　else　　{ Po

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

52、int leaf(BSTree T) //求二叉樹的葉子數(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ù)后請刪除此行　　}　　void main()　　{　　BSTree T;　　cou

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

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

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

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

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

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

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

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

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

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

數(shù)據(jù)結(jié)構(gòu)課程設計-二叉排序樹的簡單應用報告

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設計-二叉排序樹的簡單應用報告

文檔簡介

溫馨提示

最新文檔

評論

免費下載