數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--二叉排序樹的實(shí)現(xiàn)

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

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

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

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

文檔簡(jiǎn)介

1、　　課程設(shè) 計(jì)　　課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 　　題目名稱二叉排序樹的實(shí)現(xiàn) 　　學(xué) 院應(yīng)用數(shù)學(xué)學(xué)院 　　專業(yè)班級(jí)

2、　學(xué) 號(hào) 　　學(xué)生姓名 　　指導(dǎo)教師 　　2013 年 12 月 26 日　　1.設(shè)計(jì)任務(wù)　　實(shí)現(xiàn)二叉排序樹，包

3、括生成、插入，刪除；　　對(duì)二叉排序樹進(jìn)行先根、中根、和后根非遞歸遍歷；　　每次對(duì)樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上　　用樹的形狀表示出來(lái)。　　分別用二叉排序樹和數(shù)組去存儲(chǔ)一個(gè)班(50人以上)的成員信 <

4、;p>　　息(至少包括學(xué)號(hào)、姓名、成績(jī)3項(xiàng)),對(duì)比查找效率，并說(shuō)明 　　為什么二叉排序樹效率高（或者低）。　　2. 函數(shù)模塊：　　2.1.主函數(shù)main模塊功能　　1.通過(guò)bstree CreatTree()操作建立二叉排

5、序樹。 　　2.在二叉排序樹t中通過(guò)操作bstree InsertBST(bstree t,int 　　key,nametype name,double grade)插入一個(gè)節(jié)點(diǎn)。　　3. 從二叉排序樹t中通過(guò)操作void Delete(bstree &p)刪除任意節(jié)點(diǎn)。<

6、;p>　　4. 在二叉排序樹t中通過(guò)操作bstnode *SearchBST(bstree t,keytype key)查找節(jié)點(diǎn)。　　5. 在二叉排序樹t中通過(guò)操作p=SearchBST(t,key)查詢，并修改節(jié)點(diǎn)信息　　6. 非遞歸遍歷二叉排序樹。　　7. 定義函數(shù)void compare()對(duì)數(shù)組和二

7、叉排序樹的查找效率進(jìn)行比較比較。　　2.2創(chuàng)建二叉排序樹CreatTree模塊　　從鍵盤中輸入關(guān)鍵字及記錄，并同時(shí)調(diào)用插入函數(shù)并不斷進(jìn)行插入。最后，返回根節(jié)點(diǎn)T。　　2.3刪除模塊：　　二叉排序樹上刪除一個(gè)階段相當(dāng)于刪去有序系列中的一

8、個(gè)記錄，只要在刪除某個(gè)節(jié)點(diǎn)之后依舊保持二叉排序樹的性質(zhì)即可。假設(shè)二叉排序樹上刪除節(jié)點(diǎn)為*p（指向節(jié)點(diǎn)的指針為p），其雙親節(jié)點(diǎn)為*f（節(jié)點(diǎn)指針為f）。若*p節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則即左右均為空樹，由于刪去葉子節(jié)點(diǎn)不破壞整棵樹的結(jié)構(gòu)，則只需修改其雙親節(jié)點(diǎn)的指針即可；若*p節(jié)點(diǎn)只有左子樹或只有右子樹，此時(shí)只要令左子樹或右子樹直接成為其雙親節(jié)點(diǎn)*f的左子樹即可；若*p節(jié)點(diǎn)的左子樹和右子樹均不為空，其一可以令*p的左子樹為*f的左子樹，而*p的右子樹為

9、*s的右子樹，其二可以令*p的直接前驅(qū)（或直接后繼）替代*p，然后再?gòu)亩媾判驑渲袆h去它的直接前驅(qū)（或直接后繼）。在二叉排序樹中刪除一個(gè)節(jié)點(diǎn)的算法為　　void DeleteData(bstree &t,keytype key)　　若二叉排序樹t中存在關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素節(jié)點(diǎn)，并返回TRUE，否則返回FALSE。</

10、p>　　2.4插入模塊　　二叉排序樹是一種動(dòng)態(tài)樹表，其特點(diǎn)是樹的結(jié)構(gòu)通常不是一次生成的，而是在查找的過(guò)程中，當(dāng)樹中不存在關(guān)鍵字等于給定值得節(jié)點(diǎn)時(shí)在進(jìn)行插入。新插入的節(jié)點(diǎn)一定是一個(gè)新添加的葉子節(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問(wèn)的最后一個(gè)節(jié)點(diǎn)的左孩子或右孩子的節(jié)點(diǎn)。一個(gè)無(wú)序系列可以通過(guò)構(gòu)造一棵二叉排序樹而變成一個(gè)有序系列，構(gòu)造樹的

11、過(guò)程即為對(duì)無(wú)序系列進(jìn)行排序的過(guò)程，并且每次插入的節(jié)點(diǎn)都是二叉排序樹上新的葉子節(jié)點(diǎn)，則在進(jìn)行插入操作時(shí)，不必移動(dòng)其他節(jié)點(diǎn)，僅需改變某個(gè)節(jié)點(diǎn)的指針由空變?yōu)榉强占纯?。二叉排序樹的插入算法?lt;/p>　　bstree InsertBST(bstree t,int key,nametype name,double grade)　　若二叉排序樹中不存在關(guān)鍵字等于key的數(shù)據(jù)

12、元素時(shí)，插入元素并返回TRUE。　　2.5查找模塊　　二叉排序樹又稱二叉查找樹，當(dāng)二叉排序樹不為空時(shí)，首先將給定的值和根節(jié)點(diǎn)的關(guān)鍵字比較，若相等則查找成功，否則將依據(jù)給定的值和根節(jié)點(diǎn)關(guān)鍵字之間的大小關(guān)系，分別在左子樹或右子樹上繼續(xù)進(jìn)行查找。為此定義一個(gè)二叉排序樹的查找算法為

13、　bstnode *SearchBST(bstree t,keytype key) 　　在根指針t所指向的二叉排序樹中查找關(guān)鍵字等于key的數(shù)據(jù)元素，如成功，返回指向該元素節(jié)點(diǎn)的指針，否則返回空指針。　　2.6效率比較compare模塊　　void compare()對(duì)數(shù)組和二叉排序樹的查找效率進(jìn)行比較比較。

14、　　2.7二叉排序樹的遍歷　　先序遍歷也叫做先根遍歷。首先訪問(wèn)根結(jié)點(diǎn)然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹，如果二叉樹為空則返回。其實(shí)過(guò)程為：先遍歷左子樹root->left->left->left...->null，由于是先序遍歷，因此一遇到節(jié)點(diǎn)，便需要立即訪問(wèn)；由于

15、一直走到最左邊后，需要逐步返回到父節(jié)點(diǎn)訪問(wèn)右節(jié)點(diǎn)，因此必須有一個(gè)措施能夠?qū)?jié)點(diǎn)序列回溯。其一可以用棧記憶在訪問(wèn)途中將依次遇到的節(jié)點(diǎn)保存下來(lái)。根據(jù)棧的先進(jìn)后出、后進(jìn)先出的特點(diǎn)特點(diǎn)。則可以用棧保存。每次都將遇到的節(jié)點(diǎn)壓入棧，當(dāng)左子樹遍歷完畢后從棧中彈出最后一個(gè)訪問(wèn)的節(jié)點(diǎn)，然后訪問(wèn)其右子樹。　　基本算法思想：　　1.先訪問(wèn)

16、根節(jié)點(diǎn)，將根節(jié)點(diǎn)入棧　　2.重復(fù)執(zhí)行兩大步驟：如果該節(jié)點(diǎn)左孩子存在，則訪問(wèn)該左孩子節(jié)點(diǎn)，并將其指針入棧。重復(fù)以上操作，直到節(jié)點(diǎn)的左孩子不存在。將棧頂?shù)脑?，即其指針出棧，回到父?jié)點(diǎn)，如果該指針節(jié)點(diǎn)的右孩子存在，則將該指針指向的右孩子節(jié)點(diǎn)重復(fù)執(zhí)行以上步驟，直到桟為空為止。　　操作函數(shù)為void x_print(Tree T)<

17、p>　　中序遍歷：中序遍歷和先序遍歷訪問(wèn)的順序不同。中序遍歷訪問(wèn)順序?yàn)橹行虮闅v左子數(shù)，在訪問(wèn)根節(jié)點(diǎn)，最后中序遍歷右子樹。先序遍歷是先訪問(wèn),再入棧；而中序遍歷則是先入棧，彈棧后再訪問(wèn)。將二叉樹的根節(jié)點(diǎn)入棧，如果該節(jié)點(diǎn)有左孩子，將左孩子直接入棧，重復(fù)該操作，直到該節(jié)點(diǎn)無(wú)左孩子；在將棧頂元素出棧，并訪問(wèn)該節(jié)點(diǎn)指向的節(jié)點(diǎn)，如果該指針指向的右孩子存在，則將當(dāng)前指針指向右孩子節(jié)點(diǎn)。重復(fù)執(zhí)行步驟直到棧為空為止。<p

18、>　　操作函數(shù)為void z_print(Tree T )。　　后序遍歷：先后序遍歷左子樹，在后序遍歷右子樹，最后訪問(wèn)根節(jié)點(diǎn)。先將根節(jié)點(diǎn)入棧，如果該節(jié)點(diǎn)左孩子節(jié)點(diǎn)存在，將該節(jié)點(diǎn)左孩子節(jié)點(diǎn)入棧。重復(fù)執(zhí)行此操作，直到節(jié)點(diǎn)左孩子節(jié)點(diǎn)為空。取棧頂元素，并賦值給P，如果P的右孩子為空或P的右孩子等于q（即如果p的右孩子已訪問(wèn)，則訪問(wèn)根節(jié)點(diǎn)，即p指向的節(jié)點(diǎn)，并用q來(lái)記錄剛剛訪問(wèn)的節(jié)點(diǎn)的指針），若p有右

19、孩子，且右孩子沒(méi)有別訪問(wèn)過(guò)，則p=p->rchild。　　操作函數(shù)為void h_print(Tree T)　　3.源代碼　　#include<stdio.h>　　#include<iostream>

20、　　#include<string>　　#include<time.h>　　#include <iomanip>　　using namespace std;　　typedef string n

21、ametype;　　typedef unsigned long keytype;　　typedef struct node //結(jié)點(diǎn)的結(jié)構(gòu)體　　{　　keytype key;

22、　　nametype name; 　　int grade;　　struct node *lchild,*rchild;　　}bstnode;　　typedef bstnode *bstree;</

23、p>　　//棧的定義//　　typedef struct{ //棧結(jié)構(gòu)　　bstree *base;　　bstree *top;　　int stacksize;

24、　　}Sqstack;　　int InitStack (Sqstack &s) //建立一個(gè)空棧　　{　　s.base=(bstree*)malloc(1000 * sizeof(int));

25、;　　s.top=s.base;　　return 1;　　};　　int Push(Sqstack &s ,node *e)//在棧頂插入元素（進(jìn)棧）

26、;　　{　　*s.top=e;　　s.top=s.top+1;　　return 1;　　};

27、int Pop(Sqstack &s, bstree &e)//出棧　　{　　if(s.top==s.base)return 0;　　else s.top=s.top-1;　　e=*s.top;<

28、;/b>　　return 1;　　};　　//非遞歸歷遍并輸出結(jié)點(diǎn)信息//　　/*---------------先序非遞歸遍歷---------------*/<

29、;p>　　void x_print(node *t)　　{　　Sqstack s;　　InitStack(s);　　bstnode *p;　　p=t;

30、;　　while(p||!(s.top==s.base))　　{　　if(p)　　{ 　　Push(s,p);<

31、;/p>　　cout<<p->key<<"\t"<<setw(20);　　cout<<p->name<<"\t"<<setw(20);　　cout<<p->grade<<&q

32、uot;\t"<<endl;　　p=p->lchild;　　}　　else 　　{<

33、;b>　　Pop(s,p);　　p=p->rchild;　　}　　}　　}　　/*-

34、--------------中序非遞歸遍歷---------------*/　　void z_print(node *t)　　{　　Sqstack s;　　InitStack(s);　　bst

35、node *p;　　p=t;　　while(p||!(s.top==s.base))　　{　　if(p)<b&

36、gt;　　{ 　　Push(s,p);　　p=p->lchild;　　}　　else 　　{

37、;　　Pop(s,p);　　cout<<p->key<<"\t"<<setw(20);　　cout<<p->name<<"\t"<<setw(20);&

38、lt;/p>　　cout<<p->grade<<"\t"<<endl;　　p=p->rchild;　　}　　}<

39、p>　　}　　/*---------------非遞歸后序遍歷---------------*/　　void h_print(node *t)　　{　　Sqstack s;

40、;　　InitStack(s);　　node *p,*q;　　p=t;　　q=NULL;　　while(p || !(s.top==s.base))

41、　　{　　if(p){　　Push(s,p);　　p=p->lchild;　　}else&l

42、t;b>　　{　　p=*(s.top-1);　　if(p->rchild==q)　　{　　Pop(s,q);p=NULL;　　cout<<q->

43、;key<<"\t"<<setw(20);　　cout<<q->name<<"\t"<<setw(20);　　cout<<q->grade<<"\t"<<endl;

44、　　}else　　{　　p=p->rchild;q=NULL;　　}　　}

45、　　}　　}　　//遞歸查找二叉樹//　　/*---歸查找，若找到就返回指向該結(jié)點(diǎn)的指針，否則返回空---*/　　bstnode *SearchBST(bstree t,ke

46、ytype key) {　　if(t==NULL||key==t->key)　　return t;　　if(key<t->key)　　return SearchBST(t->lchild ,key);<

47、;/p>　　else 　　return SearchBST(t->rchild ,key);　　}　　//-------------------給定學(xué)生信息插入到二叉樹中-----------------

48、--//　　bstree InsertBST(bstree t,int key,nametype name,double grade)　　{　　bstree p,q;　　if(t==NULL) //樹初始為

49、空，新建二叉樹　　{　　t=new bstnode();　　t->key=key;　　t->name=name;　　t->grade=grade;&l

50、t;p>　　t->lchild=t->rchild=NULL;　　}　　else　　{　　p=t;&l

51、t;/p>　　while(p) //樹已存在，按照二叉排序樹的特性查找　　{　　q=p;　　if(p->key>key)　　p=q->

52、lchild;　　else if(p->key<key)　　p=q->rchild;　　else　　{　　cout<<end

53、l;　　cout<<"樹中已有該節(jié)點(diǎn):"<<key<<endl;　　cout<<endl;　　return t;　　}</

54、p>　　}　　p=new bstnode(); //找不到結(jié)點(diǎn)就新建一個(gè)結(jié)點(diǎn)插入到二叉排序樹中　　p->key=key;　　p->name=name;　　p->grade=gr

55、ade;　　p->lchild=p->rchild=NULL;　　if(q->key>key)　　q->lchild=p;　　else　　q->rchild

56、=p;　　}　　return t;　　}　　//-------------------二叉樹排序樹的構(gòu)建-------------------//</p

57、>　　bstree CreatTree() //不斷輸入學(xué)生信息以插入到二叉樹中　　{　　bstree t=NULL;　　keytype key;　　nametype name;</

58、p>　　double grade;　　cout<<"請(qǐng)輸入---學(xué)號(hào)---姓名---成績(jī)---（輸入0時(shí)結(jié)束）:"<<endl;　　cin>>key;　　if(key==0)

59、;　　return t;　　cin>>name;　　cin>>grade;　　while(key) //key==0時(shí)退出　　{<

60、/p>　　t=InsertBST(t,key,name,grade);　　cout<<"請(qǐng)輸入---學(xué)號(hào)---姓名---成績(jī)---（輸入0時(shí)結(jié)束）:"<<endl;　　cin>>key;　　i

61、f(key==0)　　break;　　cin>>name;　　cin>>grade;　　}　　return t;

62、　　}　　//-------------------刪除樹中的結(jié)點(diǎn)-------------------//　　void Delete(bstree &p) //刪除結(jié)點(diǎn)的函數(shù)

63、{　　bstree q,s;　　if(!p->rchild)　　{　　q=p;　　p=q->lchild ;</p&

64、gt;　　delete q;　　}　　else if(!p->lchild)　　{　　q=p;

65、;　　p=p->rchild;　　delete q;　　}　　else 　　{</b&

66、gt;　　q=p;　　s=p->lchild;　　while(s->rchild)　　{　　q=s;&l

67、t;/p>　　s=s->rchild;　　}　　p->name=s->name;　　if(q!=p)　　q->rchild=s->lchi

68、ld;　　else　　q->lchild=s->lchild;　　delete s;　　}<b&g

69、t;　　}　　void DeleteData(bstree &t,keytype key)　　{　　if(!t){　　cout<<"沒(méi)有該信息，請(qǐng)

70、重新輸入！";　　cin>>key;　　DeleteData(t,key);　　}　　else

71、　　{　　if(t->key==key)　　{　　Delete(t); //若找到結(jié)點(diǎn)直接刪除　　cout<<"刪除成功！"<<endl;

72、　　}　　else if(t->key>key)　　DeleteData(t->lchild,key); //結(jié)點(diǎn)數(shù)據(jù)比查找關(guān)鍵字大，繼續(xù)在其左子樹中查找　　else<

73、;/p>　　DeleteData(t->rchild,key); //結(jié)點(diǎn)數(shù)據(jù)比查找關(guān)鍵字小，繼續(xù)在其右子樹中查找　　}　　}　　//數(shù)組和二叉排序樹的查找效率比較//<

74、p>　　void compare()　　{　　bstree t=NULL;　　clock_t start,end,start1,end1;　　int num=0;

75、int a=0;　　int b=0;　　int c=0;　　int d=1;　　bstree p;&

76、lt;/p>　　string key,name;　　double grade;　　nametype str [100][3];　　//cout<<"（輸入0時(shí)結(jié)束）"<<endl;　　cout<

77、<"請(qǐng)輸入---學(xué)號(hào)---姓名---成績(jī)---（輸入0時(shí)結(jié)束）:"<<endl;　　cin>>key;　　if(key=="0")　　return ;

78、;　　cin>>name;　　cin>>grade;　　while(key!="0")　　{　　str[num][0]=key;

79、;　　str[num][1]=name;　　str[num][2]=grade;　　int key1=atoi(key.c_str()); //用庫(kù)函數(shù)將字符串轉(zhuǎn)化為關(guān)鍵字的int型　　t=InsertBST(t,key1,name,grade); //插入結(jié)點(diǎn)

80、cout<<"請(qǐng)輸入---學(xué)號(hào)---姓名---成績(jī)---（輸入0時(shí)結(jié)束）:"<<endl;　　cin>>key;　　if(key=="0")　　break;<

81、;/p>　　cin>>name;　　cin>>grade;　　num++;　　}　　cout<<endl;&

82、lt;p>　　cout<<"進(jìn)行數(shù)組和二叉排序樹的查詢效率比較（比較：1 不比較：0）";　　cin>>d;　　while(d!=NULL)　　{

83、;　　switch(d)　　{　　case 0: 　　cout<<"返回選擇界面"<<endl;

84、　　break;　　case 1:　　cout<<"數(shù)組查詢！"<<endl;　　cout<<"請(qǐng)輸入查詢的成績(jī)："<<endl;<p&g

85、t;　　cin>>key;　　start=clock();　　while(a<=10000000) //循環(huán)模擬數(shù)組查找　　{　　while(b<=99)

86、　　{　　if(str[b][0]==key)　　{b=100;}　　else　　b++;<

87、/b>　　}　　b=0;　　a++;　　}　　end=clock();&

88、lt;/p>　　if(num>=100)　　cout<<"數(shù)組查詢：無(wú)查詢信息，花費(fèi)時(shí)間: "<<end-start<<" 毫秒"<<endl;　　else<p&g

89、t;　　cout<<"數(shù)組查詢：查到信息，花費(fèi)時(shí)間: "<<end-start<<" 毫秒"<<endl;　　int key1=atoi(key.c_str()); //同上轉(zhuǎn)化　　start1=clock();　　w

90、hile(c<=10000000) //用循環(huán)來(lái)模擬樹中查找　　{　　p=SearchBST(t,key1);　　c++;　　}</

91、p>　　end1=clock();　　if(p==NULL)　　cout<<"樹查詢：無(wú)查詢信息，花費(fèi)時(shí)間: "<<end1-start1<<" 毫秒"<<endl;　　else

92、　　cout<<"樹查詢：查到信息，花費(fèi)時(shí)間: "<<end1-start1<<" 毫秒"<<endl;　　a=0;　　b=0;

93、　　c=0;　　break;　　}　　cout<<"是否繼續(xù)進(jìn)行操作（是：1 否：0）：";<p

94、>　　cin>>d;　　}　　}　　//二叉樹的深度　　int TreeDepth(bstree t)

95、　　{　　int left,right,max;　　if(t!=NULL)　　{　　left=TreeDepth(t->lchild);</p

96、>　　right=TreeDepth(t->rchild);　　max=left>right?left:right;　　return max+1;　　}else　　{</

97、b>　　return 0;　　}　　}　　//樹狀輸出二叉樹　　void

98、 PrintTree(bstree t,int layer)　　{　　int k;　　if(t==NULL)　　return ;<

99、;p>　　PrintTree(t->rchild,layer+1);　　for(k=0;k<layer;k++)　　cout<<" ";　　cout<<t->key<<"\n";<

100、;p>　　PrintTree(t->lchild,layer+1);　　}　　//-------------------主函數(shù)測(cè)試-------------------//　　int main()　　{&

101、lt;/b>　　int d;　　keytype key;　　bstree t=NULL;　　t=CreatTree();　　d=TreeDepth(t);<

102、p>　　cout<<"二叉排序樹的樹形表示如下"<<endl;　　PrintTree(t,d);　　char choose;　　nametype name;　　bstree p;<

103、;/p>　　double grade;　　cout<<" "<<endl;　　cout<<"-----------------------------請(qǐng)輸入你要選擇的操作-------------------------------"<<e

104、ndl;　　cout<<" |-------------------------------------|"<<endl;　　cout<<" ||----------------------------------

105、-||"<<endl;　　cout<<" || a 插入信息 ||"<<endl;　　cout<<" || b 刪除信息

106、 ||"<<endl;　　cout<<" || c 查詢信息 ||"<<endl;　　cout<<" || d

107、修改信息 ||"<<endl;　　cout<<" || 0 退出 ||"<<endl;　　cout<<"

108、|| e 對(duì)二叉排序樹進(jìn)行非遞歸遍歷 ||"<<endl;　　cout<<" || f 進(jìn)行數(shù)組和二叉樹查找效率實(shí)驗(yàn)||"<<endl;　　cout<<" ||-------

109、----------------------------||"<<endl;　　cout<<" |-------------------------------------|"<<endl;　　cout<<endl;

110、　　cout<<"需要選擇的操作為：";　　cin>>choose;　　cout<<endl;　　while(choose)　　{<

111、;p>　　switch(choose)　　{　　case 'a':　　//cout<<"輸入學(xué)生信息信息（學(xué)號(hào)為0時(shí)結(jié)束）."<<endl;<

112、p>　　cout<<"請(qǐng)輸入---學(xué)號(hào)---姓名---成績(jī)---（輸入0時(shí)結(jié)束）:"<<endl;　　cin>>key;　　if(key==0) /*{　　PrintTree(t,d);&l

113、t;p>　　break;}*/　　cin>>name;　　cin>>grade;　　while(key) 　　{

114、　　t=InsertBST(t,key,name,grade);　　cout<<"請(qǐng)輸入---學(xué)號(hào)---姓名---成績(jī)---:"<<endl;　　cin>>key;　　if(key==0)<

115、p>　　break;　　cin>>name;　　cin>>grade;　　}　　break;<p&

116、gt;　　case 'b':　　cout<<"請(qǐng)輸入要?jiǎng)h除信息學(xué)生的成績(jī)："<<endl;　　cin>>key;　　DeleteData(t,key);</p&

117、gt;　　d=TreeDepth(t);　　cout<<"刪除結(jié)點(diǎn)后二叉樹的樹形顯示如下"<<endl;　　PrintTree(t,d);　　break;<b&g

118、t;　　case 'c':　　cout<<"請(qǐng)輸入要查詢的成績(jī)："<<endl;　　cin>>key;　　p=SearchBST(t,key);

119、;　　if(p==NULL)　　cout<<"無(wú)查詢的關(guān)鍵字："<<key<<endl;　　else　　cout<<"成績(jī)"<<"\t"<<se

120、tw(20)<<"姓名"<<"\t"<<setw(20)<<"學(xué)號(hào)"<<endl;　　cout<<p->key<<"\t"<<setw(20);　　cout<<p

121、->name<<"\t"<<setw(20);　　cout<<p->grade<<endl;　　break;　　case 'd':</p

122、>　　cout<<"請(qǐng)輸入要修改的學(xué)號(hào)："<<endl;　　cin>>key;　　p=SearchBST(t,key);　　if(p==NULL)

123、cout<<"無(wú)你所要修改的關(guān)鍵字："<<key<<endl;　　else　　{　　cout<<"請(qǐng)輸入修改的姓名：";<

124、;p>　　cin>>name;　　cout<<"請(qǐng)輸入修改的成績(jī)：";　　cin>>grade;　　p->name=name;　　p->grade=grade;<p&g

125、t;　　}　　break;　　case 'e':　　if(!t)　　cout<<"

126、沒(méi)有任何信息，請(qǐng)先輸入信息！";　　else　　{　　cout<<"學(xué)號(hào)"<<"\t"<<setw(20)<<"姓名"&

127、lt;<"\t"<<setw(20)<<"成績(jī)"<<endl;　　cout<<"------------------非遞歸先序遍歷----------------"<<endl;　　cout<<endl;</p&

128、gt;　　x_print(t);　　cout<<"------------------非遞歸中序遍歷-----------------"<<endl;　　cout<<endl;　　z_print(t);<p

129、>　　cout<<"------------------非遞歸后序遍歷-----------------"<<endl;　　cout<<endl;　　h_print(t);　　}<p&

130、gt;　　break;　　case 'f':　　cout<<"***此實(shí)驗(yàn)為獨(dú)立實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)獨(dú)立于外部數(shù)據(jù)***"<<endl;　　cout<<"***請(qǐng)

131、重新輸入相關(guān)信息***"<<endl;　　compare();　　break;　　default:　　cout<<"選擇錯(cuò)誤！";</p

132、>　　break;　　}　　cout<<endl;　　cout<<endl;　　cout<<" "<<

133、;endl;　　cout<<"-----------------------------請(qǐng)輸入你要選擇的操作-------------------------------"<<endl;　　cout<<" |----------------------

134、---------------|"<<endl;　　cout<<" ||-----------------------------------||"<<endl;　　cout<<" ||

135、 a 插入信息 ||"<<endl;　　cout<<" || b 刪除信息 ||"<<endl;　　cout<<"

136、 || c 查詢信息 ||"<<endl;　　cout<<" || d 修改信息 ||"<<endl;　　cout<<"

137、 || 0 退出 ||"<<endl;　　cout<<" || e 對(duì)二叉排序樹進(jìn)行非遞歸遍歷 ||"<<endl;　　cout<<"

138、 || f 進(jìn)行數(shù)組和二叉樹查找效率實(shí)驗(yàn)||"<<endl;　　cout<<" ||-----------------------------------||"<<endl;　　cout<<&quo

139、t; |-------------------------------------|"<<endl;　　cout<<endl;　　cout<<"選擇的操作位：";　　cin>>choose;<

140、/p>　　cout<<endl;　　}　　return 0;　　}　　4.運(yùn)行結(jié)果及截圖</b

141、>　　從鍵盤讀入數(shù)據(jù)　　以0作為結(jié)束標(biāo)志可得二叉排序樹樹狀表示　　主菜單選擇模塊　　需要在樹種添加節(jié)點(diǎn)則執(zhí)行操作a　　需要在書中刪除節(jié)點(diǎn)執(zhí)行操作b&

142、lt;/p>　　需要查詢節(jié)點(diǎn)信息執(zhí)行操作c　　修改某一節(jié)點(diǎn)信息執(zhí)行操作d　　執(zhí)行操作0退出程序執(zhí)行　　執(zhí)行操作e對(duì)樹進(jìn)行先序遍歷、后序遍歷、中序遍歷運(yùn)行結(jié)果如下圖　　需要對(duì)樹和數(shù)組的查詢效率比較執(zhí)行操作f

143、;　　4.實(shí)驗(yàn)結(jié)論 　　棧是僅表尾進(jìn)行插入和刪除的線性表，棧的順序存儲(chǔ)結(jié)構(gòu)是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，并同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的位置。　　從數(shù)組查詢和樹查詢的時(shí)間可得出，樹的查詢比數(shù)組的查詢時(shí)間快得多。但是二叉樹的平均查找長(zhǎng)度和樹的形態(tài)有關(guān)，當(dāng)先后插入的關(guān)鍵字是有序樹時(shí)，構(gòu)造的二叉樹蛻變?yōu)閱芜厴?/p>

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

溫馨提示

1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
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ì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--二叉排序樹的實(shí)現(xiàn)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--二叉排序樹的實(shí)現(xiàn)

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載