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

1、最新資料推薦課程設(shè)計(jì)課程名稱數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目名稱二叉排序樹的實(shí)現(xiàn)學(xué)院應(yīng)用數(shù)學(xué)學(xué)院專業(yè)班級(jí)學(xué)號(hào)學(xué)生姓名指導(dǎo)教師2013年12月26日1. 設(shè)計(jì)任務(wù)1）實(shí)現(xiàn)二叉排序樹，包括生成、插入，刪除；2）對(duì)二叉排序樹進(jìn)行先根、中根、和后根非遞歸遍歷；3）每次對(duì)樹的修改操作和遍歷操作的顯示結(jié)果都需要在屏幕上用樹的形狀表示出來(lái)。4）分別用二叉排序樹和數(shù)組去存儲(chǔ)一個(gè)班（50人以上）的成員信息（至少包括學(xué)號(hào)、姓名、成績(jī)3項(xiàng)）,對(duì)比查找效率，并說(shuō)明為什么二叉排序樹效率高（或者低）。2. 函數(shù)模塊：2.1 .主函數(shù)main模塊功能1. 通過(guò)bstreeCreatTree（）操作建立二叉排序樹。2. 在二叉排序樹t中

2、通過(guò)操作bstreeInsertBST（bstreet,intkey,nametypename,doublegrade）插入一個(gè)節(jié)點(diǎn)。3. 從二叉排序樹t中通過(guò)操作voidDelete（bstree&p）刪除任意節(jié)點(diǎn)。4. 在二叉排序樹t中通過(guò)操作bstnode*SearchBST（bstreet,keytypekey）查找節(jié)點(diǎn)。5. 在二叉排序樹t中通過(guò)操作p=SearchBST（t,key）查詢，并修改節(jié)點(diǎn)信息6. 非遞歸遍歷二叉排序樹。7. 定義函數(shù)voidcompare（）對(duì)數(shù)組和二叉排序樹的查找效率進(jìn)行比較比較。2.2 創(chuàng)建二叉排序樹CreatTree模塊從鍵盤中輸入關(guān)鍵字及

3、記錄，并同時(shí)調(diào)用插入函數(shù)并不斷進(jìn)行插入。最后，返回根節(jié)點(diǎn)T。2.3 刪除模塊：二叉排序樹上刪除一個(gè)階段相當(dāng)于刪去有序系列中的一個(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的右子樹為*s的右子樹，其二可以令*p的直接

4、前驅(qū)（或直接后繼）替代*p，然后再?gòu)亩媾判驑渲袆h去它的直接前驅(qū)（或直接后繼）。在二叉排序樹中刪除一個(gè)節(jié)點(diǎn)的算法為voidDeleteData（bstree&t,keytypekey）若二叉排序樹t中存在關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素節(jié)點(diǎn)，并返回TRUE否則返回FALSE2.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è)有

5、序系列，構(gòu)造樹的過(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)榉强占纯?。二叉排序樹的插入算法為bstreeInsertBST(bstreet,intkey,nametypename,doublegrade)若二叉排序樹中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，插入元素并返回TRUE2.5查找模塊二叉排序樹又稱二叉查找樹，當(dāng)二叉排序樹不為空時(shí)，首先將給定的值和根節(jié)點(diǎn)的關(guān)鍵字比較，若相等則查找成功，否則將依據(jù)給定的值和根節(jié)點(diǎn)關(guān)鍵字之間的大小關(guān)系，分別在左子樹或右子樹上繼續(xù)進(jìn)行查找。為此定義一個(gè)二叉排

6、序樹的查找算法為bstnode*SearchBST(bstreet,keytypekey)在根指針t所指向的二叉排序樹中查找關(guān)鍵字等于key的數(shù)據(jù)元素，如成功，返回指向該元素節(jié)點(diǎn)的指針，否則返回空指針。2.6 效率比較compare模塊voidcompare。對(duì)數(shù)組和二叉排序樹的查找效率進(jìn)行比較比較。2.7 二叉排序樹的遍歷先序遍歷也叫做先根遍歷。首先訪問(wèn)根結(jié)點(diǎn)然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹，如果二叉樹為空則返回。其實(shí)過(guò)程為：先遍歷左子樹root->left->left->left->null,由于是

7、先序遍歷，因此一遇到節(jié)點(diǎn)，便需要立即訪問(wèn)；由于一直走到最左邊后，需要逐步返回到父節(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)根節(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í)行

8、以上步驟，直到棧為空為止。操作函數(shù)為voidx_print(TreeT)中序遍歷：中序遍廟和先序遍歷訪問(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í)行步驟直到棧為空為止。操作函數(shù)為voidz_print(TreeT)。后序遍歷：先后F遍歷左子樹，在后序遍歷右子樹，最后訪問(wèn)根節(jié)點(diǎn)。先將根節(jié)點(diǎn)入棧，如果該節(jié)點(diǎn)

9、左孩子節(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有右孩子，且右孩子沒(méi)有別訪問(wèn)過(guò)，則p=p->rchildo操作函數(shù)為voidh_print(TreeT)3 .源代碼#include<stdio.h>#include<iostream>#include<string>#include<time.h>#include<iomanip>usingna

10、mespacestd;typedefstringnametype;typedefunsignedlongkeytype;typedefstructnode/結(jié)點(diǎn)的結(jié)構(gòu)體keytypekey;nametypename;intgrade;structnode*lchild,*rchild;bstnode;typedefbstnode*bstree;/棧的定義typedefstruct/棧結(jié)構(gòu)bstree*base;bstree*top;intstacksize;Sqstack;intInitStack(Sqstack&s)/建立一個(gè)空棧s.base=(bstree*)malloc(1000

11、*sizeof(int);s.top=s.base;return1;intPush(Sqstack&s,node*e)/在棧頂插入元素(進(jìn)棧)*s.top=e;s.top=s.top+1;return1;)；intPop(Sqstack&s,bstree&e)/出棧(if(s.top=s.base)return0;elses.top=s.top-1;e=*s.top;return1;);/非遞歸歷遍并輸出結(jié)點(diǎn)信息/*先序非遞歸遍歷*/voidx_print(node*t)(Sqstacks;InitStack(s);bstnode*p;p=t;while(p|!(s.t

12、op=s.base)(if(p)(Push(s,p);cout<<p->key<<"t"<<setw(20);cout<<p->name<<"t"<<setw(20);cout<<p->grade<<"t"<<endl;p=p->lchild;)else(Pop(s,p);p=p->rchild;)/*中序非遞歸遍歷*/voidz_print(node*t)(Sqstacks;InitStack(s

13、);bstnode*p;p=t;最新資料推薦while(p|!(s.top=s.base)(if(Push(s,p);p=p->lchild;)else(Pop(s,p);cout<<p->key<<"t"<<setw(20);cout<<p->name<<"t"<<setw(20);cout<<p->grade<<"t"<<endl;p=p->rchild;)/*非遞歸后序遍歷*/voidh_pr

14、int(node*t)(Sqstacks;InitStack(s);node*p,*q;p=t;q=NULL;while(p|!(s.top=s.base)(if(p)Push(s,p);p=p->lchild;elsep=*(s.top-1);if(p->rchild=q)Pop(s,q);p=NULL;cout<<q->key<<"t"<<setw(20);cout<<q->name<<"t"<<setw(20);cout<<q->gra

15、de<<"t"<<endl;elsep=p->rchild;q=NULL;)/遞歸查找二叉樹/*-歸查找，若找到就返回指向該結(jié)點(diǎn)的指針，否則返回空-*/bstnode*SearchBST(bstreet,keytypekey)if(t=NULL|key=t->key)returnt;if(key<t->key)returnSearchBST(t->lchild,key);elsereturnSearchBST(t->rchild,key);)/給定學(xué)生信息插入到二叉樹中bstreeInsertBST(bstreet

16、,intkey,nametypename,doublegrade)bstreep,q;if(t=NULL)/樹初始為空，新建二叉樹t=newbstnode();t->key=key;t->name=name;t->grade=grade;t->lchild=t->rchild=NULL;)elsep=t;while(p)/樹已存在，按照二叉排序樹的特性查找q=p;if(p->key>key)p=q->lchild;elseif(p->key<key)p=q->rchild;elsecout<<endl;cout<

17、;<"樹中已有該節(jié)點(diǎn)："<<key<<endl;cout<<endl;returnt;最新資料推薦)p=newbstnode();/找不到結(jié)點(diǎn)就新建一個(gè)結(jié)點(diǎn)插入到二叉排序樹中p->key=key;p->name=name;p->grade=grade;p->lchild=p->rchild=NULL;if(q->key>key)q->lchild=p;elseq->rchild=p;)returnt;)/二叉樹排序樹的構(gòu)建/bstreeCreatTree()/不斷輸入學(xué)生信息以插

18、入到二叉樹中bstreet=NULL;keytypekey;nametypename;doublegrade;cout<<"請(qǐng)輸入-學(xué)號(hào)-姓名-成績(jī)-(輸入0時(shí)結(jié)束)："<<endl;cin>>key;if(key=0)returnt;cin>>name;cin>>grade;while(key)/key=0時(shí)退出t=InsertBST(t,key,name,grade);cout<<"請(qǐng)輸入-學(xué)號(hào)-姓名-成績(jī)-(輸入0時(shí)結(jié)束)："<<endl;cin>>ke

19、y;if(key=0)break;cin>>name;cin>>grade;)returnt;)/刪除樹中的結(jié)點(diǎn)/voidDelete(bstree&p)/刪除結(jié)點(diǎn)的函數(shù)bstreeq,s;if(!p->rchild)(q=p；p=q->lchild;deleteq;)elseif(!p->lchild)(q=p；p=p->rchild;deleteq;)else(q=p；s=p->lchild;while(s->rchild)(q=s;s=s->rchild;)p->name=s->name;if(q!=p

20、)q->rchild=s->lchild;elseq->lchild=s->lchild;deletes;)voidDeleteData(bstree&t,keytypekey)(if(!t)cout<<"沒(méi)有該信息，請(qǐng)重新輸入!cin>>key;DeleteData(t,key);)elseif(t->key=key)Delete(t); /若找到結(jié)點(diǎn)直接刪除cout<<"刪除成功！"<<endl;)elseif(t->key>key)DeleteData(t-&g

21、t;lchild,key);/結(jié)點(diǎn)數(shù)據(jù)比查找關(guān)鍵字大，繼續(xù)在其左子樹中查找elseDeleteData(t->rchild,key);/結(jié)點(diǎn)數(shù)據(jù)比查找關(guān)鍵字小，繼續(xù)在其右子樹中查找)/數(shù)組和二叉排序樹白查找效率比較voidcompare()bstreet=NULL;clock_tstart,end,start1,end1;intnum=0;inta=0;intb=0;intc=0;intd=1;bstreep;stringkey,name;doublegrade;nametypestr1003;/cout<<"(輸入0時(shí)結(jié)束)"<<endl;c

22、out<<"請(qǐng)輸入-學(xué)號(hào)-姓名-成績(jī)-(輸入0時(shí)結(jié)束):"<<endl;cin>>key;if(key="0")return;cin>>name;cin>>grade;while(key!="0")strnum0=key;strnum1=name;strnum2=grade;intkey1=atoi(key.c_str();/用庫(kù)函數(shù)將字符串轉(zhuǎn)化為關(guān)鍵字的int型t=InsertBST(t,key1,name,grade);/插入結(jié)點(diǎn)cout<<"請(qǐng)輸入

23、-學(xué)號(hào)-姓名-成績(jī)-(輸入0時(shí)結(jié)束):"<<endl;cin>>key;if(key="0")break;cin>>name;cin>>grade;num+;)cout<<endl;cout<<"進(jìn)行數(shù)組和二叉排序樹的查詢效率比較(比較：1不比較：0)"cin>>d;while(d!=NULL)(switch(d)(case0:cout<<"返回選擇界面"<<endl;break;case1:cout<<&

24、quot;數(shù)組查詢！"<<endl;cout<<"請(qǐng)輸入查詢的成績(jī)："<<endl;cin>>key;start=clock();while(a<=10000000)/循環(huán)模擬數(shù)組查找(while(b<=99)(if(strb0=key)b=100;elseb+;b=0;a+;end=clock();if(num>=100)cout<<"數(shù)組查詢：無(wú)查詢信息，花費(fèi)時(shí)間："<<end-start<<"毫秒"<<en

25、dl;elsecout<<"數(shù)組查詢：查到信息，花費(fèi)時(shí)間："<<end-start<<"毫秒"<<endl;intkey1=atoi(key.c_str();/同上轉(zhuǎn)化start1=clock();while(c<=10000000)/用循環(huán)來(lái)模擬樹中查找p=SearchBST(t,key1);c+;end1=clock();if(p=NULL)cout<<"樹查詢：無(wú)查詢信息，花費(fèi)時(shí)間："<<end1-start1<<"毫秒"

26、;<<endl;elsecout<<"樹查詢：查到信息，花費(fèi)時(shí)間："<<end1-start1<<"毫秒"<<endl;a=0;b=0;c=0;break;cout<<"是否繼續(xù)進(jìn)行操作(是：1否：0):"cin>>d;/二叉樹的深度intTreeDepth(bstreet)intleft,right,max;if(t!=NULL)left=TreeDepth(t->lchild);right=TreeDepth(t->rchild);ma

27、x=left>right?left:right;returnmax+1;elsereturn0;/樹狀輸出二叉樹voidPrintTree(bstreet,intlayer)intk;if(t=NULL)return;PrintTree(t->rchild,layer+1);for(k=0;k<layer;k+)cout<<""cout<<t->key<<"n"PrintTree(t->lchild,layer+1);/主函數(shù)測(cè)試/intmain()(intd;keytypekey;bst

28、reet=NULL;t=CreatTree();d=TreeDepth(t);cout<<"二叉排序樹的樹形表示如下"<<endl;PrintTree(t,d);charchoose;nametypename;bstreep;doublegrade;cout<<""<<endl;cout<<"請(qǐng)輸入你要選擇的操作"<<endl;cout<<"|"<<endl;cout<<"|"<&l

29、t;endl;cout<<"|a插入信息|"<<endl;cout<<"|b刪除信息|"<<endl;cout<<"|c查詢信息|"<<endl;cout<<"|d修改信息|"<<endl;cout<<"|0退出|"<<endl;cout<<"|e對(duì)二叉排序樹進(jìn)行非遞歸遍歷|"<<endl;cout<<"|f進(jìn)行

30、數(shù)組和二叉樹查找效率實(shí)驗(yàn)|"<<endl;cout<<"|"<<endl;cout<<"|"<<endl;cout<<endl;cout<<"需要選擇的操作為："cin>>choose;cout<<endl;while(choose)(switch(choose)(case'a':/cout<<"輸入學(xué)生信息信息(學(xué)號(hào)為0時(shí)結(jié)束)."<<endl;cout&l

31、t;<"請(qǐng)輸入-學(xué)號(hào)-姓名-成績(jī)-(輸入0時(shí)結(jié)束)："<<endl;cin>>key;if(key=0)/*PrintTree(t,d);break;*/cin>>name;cin»grade;while(key)(t=lnsertBST(t,key,name,grade);cout<<”請(qǐng)輸入字號(hào)姓名成績(jī):"<<endl;cin»key;if(key=O)break;cin»name;cin»grade;)break;case'b':cout

32、<<”請(qǐng)輸入要?jiǎng)h除信息學(xué)生的成績(jī)：口<endl;cin»key;DeleteData(t,key);d=TreeDepth(t);cout«"刪除結(jié)點(diǎn)后二叉樹的樹形顯示如下"<<endl;PrintTree(t,d);break;case'c':cout<”請(qǐng)輸入要查詢的成績(jī)："<<endl;cin»key;p=SearchBST(t,key);if(p=NULL)cout«"無(wú)查詢的關(guān)鍵字："«key«endl;else

33、cout«"成績(jī)"<<"t"«setw(20)«"姓名"<<"t"«setw(20)«"學(xué)號(hào)"«endl;cout«p->key«"t"«setw(20);cout«p->name«"t"«setw(20);cout«p->grade«endl;break;case'd

34、':cout<"請(qǐng)輸入要修改的學(xué)號(hào)："«endl;cin»key;p=SearchBST(t,key);if(p=NULL)cout«"無(wú)你所要修改的關(guān)鍵字："«key«endl;else(cout<<"請(qǐng)輸入修改的姓名：cin»name;cout<<"請(qǐng)輸入修改的成績(jī)："cin>>grade;p->name=name;p->grade=grade;break;case'e':"

35、<<endl;cout<<"沒(méi)有任何信息，請(qǐng)先輸入信息!II.elsecout<<"學(xué)號(hào)"<<"t"<<setw(20)<<"姓名"<<"t"<<setw(20)<<"cout<<""<<endl;cout<<endl;x_print(t);cout<<"-"<<endl;cout<&

36、lt;endl;z_print(t);cout<<""<<endl;cout<<endl;h_print(t);break;case'f:cout<<"*cout<<"*此實(shí)驗(yàn)為獨(dú)立實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)獨(dú)立于外部數(shù)據(jù) 請(qǐng)重新輸入相關(guān)信息*"<<endl;*"<<endl;compare();break;default:cout<<"選擇錯(cuò)誤!break;cout<<endl;cout<<endl;cout

37、<<""<<endl;cout<<"請(qǐng)輸入你要選擇的操作"<<endl;cout<<"|"<<endl;cout<<"|"<<endl;cout<<"|cout<<"|cout<<"|cout<<"|cout<<"|cout<<"|cout<<"|cout<<"|a插入信息|"<<endl;|b刪除信息|"<<endl;|c查詢信息|"<<endl;|d修改信息|"<<endl;|0退出|"<<endl;|e對(duì)二叉排序樹進(jìn)行非遞歸遍歷|"<<endl;|f進(jìn)行數(shù)組和二叉樹查找效率實(shí)驗(yàn)|"<<endl;|"<<endl;cout<<"