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

1、 黃淮學(xué)院“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計(jì)報(bào)告系 （院）： 信息工程學(xué)院 設(shè)計(jì)題目： 二叉排序樹(shù)的實(shí)現(xiàn) 專業(yè)班級(jí)： 軟件工程15級(jí) 小組成員： 唐二虎、趙夢(mèng)娟、賈月 指導(dǎo)教師： 汪洋 完成時(shí)間： 2016.12.27 17二叉排序樹(shù)的實(shí)現(xiàn)1.設(shè)計(jì)任務(wù)1） 實(shí)現(xiàn)二叉排序樹(shù)，包括生成、插入，刪除；2） 對(duì)二叉排序樹(shù)進(jìn)行先根、中根、和后根非遞歸遍歷；3） 每次對(duì)樹(shù)的修改操作和遍歷操作的顯示結(jié)果都需要在用樹(shù)的形狀表示出來(lái)。4） 分別用二叉排序樹(shù)和數(shù)組去存儲(chǔ)一個(gè)班(50人以上)的成員信息(至少包括學(xué)號(hào)、姓名、成績(jī)3項(xiàng)),對(duì)比查找效率，并說(shuō)明為什么二叉排序樹(shù)效率高（或者低）。2.程序設(shè)計(jì)流程圖（設(shè)計(jì)思想）無(wú)結(jié)點(diǎn)x存在

2、含x的結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)，并作中序遍歷找到該節(jié)點(diǎn)x輸入元素x，查找二叉排序樹(shù)T對(duì)二叉排序樹(shù)T作中序遍歷,并輸出結(jié)果二叉鏈表作存儲(chǔ)結(jié)構(gòu)和順序表作存儲(chǔ)結(jié)構(gòu)輸入數(shù)列L， 以回車(n)為輸入結(jié)束標(biāo)志生成二叉排序樹(shù)T；詳細(xì)設(shè)計(jì)思想：建立二叉排序樹(shù)采用邊查找邊插入的方式。查找函數(shù)采用遞歸的方式進(jìn)行查找。如果查找到相等的則插入其左子樹(shù)。然后利用插入函數(shù)將該元素插入原樹(shù)。對(duì)二叉樹(shù)進(jìn)行中序遍歷采用遞歸函數(shù)的方式。在根結(jié)點(diǎn)不為空的情況下，先訪問(wèn)左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)。刪除結(jié)點(diǎn)函數(shù)，采用邊查找邊刪除的方式。如果沒(méi)有查找到，進(jìn)行提示；如果查找到結(jié)點(diǎn)則將其左子樹(shù)最右邊的節(jié)點(diǎn)的數(shù)據(jù)傳給它，然后刪除其左子樹(shù)最

3、右邊的節(jié)點(diǎn)。3.函數(shù)模塊：3.1.主函數(shù)main模塊功能1.通過(guò)bstreeCreatTree()操作建立二叉排序樹(shù)。2.在二叉排序樹(shù)t中通過(guò)操作bstreeInsertBST(bstreet,intkey,nametypename,double grade)插入一個(gè)節(jié)點(diǎn)。3. 從二叉排序樹(shù)t中通過(guò)操作void Delete(bstree&p)刪除任意節(jié)點(diǎn)。4.在二叉排序樹(shù)t中通過(guò)操作bstnode *SearchBST(bstreet,keytype key)查找節(jié)點(diǎn)。5.在二叉排序樹(shù)t中通過(guò)操作p=SearchBST(t,key)查詢，并修改節(jié)點(diǎn)信息6.非遞歸遍歷二叉排序樹(shù)。7.定

4、義函數(shù)void compare()對(duì)數(shù)組和二叉排序樹(shù)的查找效率進(jìn)行比較比較。3.2創(chuàng)建二叉排序樹(shù)CreatTree模塊從鍵盤(pán)中輸入關(guān)鍵字及記錄，并同時(shí)調(diào)用插入函數(shù)并不斷進(jìn)行插入。最后，返回根節(jié)點(diǎn)T。3.3刪除模塊：二叉排序樹(shù)上刪除一個(gè)階段相當(dāng)于刪去有序系列中的一個(gè)記錄，只要在刪除某個(gè)節(jié)點(diǎn)之后依舊保持二叉排序樹(shù)的性質(zhì)即可。假設(shè)二叉排序樹(shù)上刪除節(jié)點(diǎn)為*p（指向節(jié)點(diǎn)的指針為p），其雙親節(jié)點(diǎn)為*f（節(jié)點(diǎn)指針為f）。若*p節(jié)點(diǎn)為葉子節(jié)點(diǎn)，則即左右均為空樹(shù)，由于刪去葉子節(jié)點(diǎn)不破壞整棵樹(shù)的結(jié)構(gòu)，則只需修改其雙親節(jié)點(diǎn)的指針即可；若*p節(jié)點(diǎn)只有左子樹(shù)或只有右子樹(shù)，此時(shí)只要令左子樹(shù)或右子樹(shù)直接成為其雙親節(jié)點(diǎn)*f的

5、左子樹(shù)即可；若*p節(jié)點(diǎn)的左子樹(shù)和右子樹(shù)均不為空，其一可以令*p的左子樹(shù)為*f的左子樹(shù)，而*p的右子樹(shù)為*s的右子樹(shù)，其二可以令*p的直接前驅(qū)（或直接后繼）替代*p，然后再?gòu)亩媾判驑?shù)中刪去它的直接前驅(qū)（或直接后繼）。在二叉排序樹(shù)中刪除一個(gè)節(jié)點(diǎn)的算法為voidDeleteData(bstree&t,keytype key)若二叉排序樹(shù)t中存在關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素節(jié)點(diǎn)，并返回TRUE，否則返回FALSE。3.4插入模塊二叉排序樹(shù)是一種動(dòng)態(tài)樹(shù)表，其特點(diǎn)是樹(shù)的結(jié)構(gòu)通常不是一次生成的，而是在查找的過(guò)程中，當(dāng)樹(shù)中不存在關(guān)鍵字等于給定值得節(jié)點(diǎn)時(shí)在進(jìn)行插入。新插入的節(jié)點(diǎn)一定是一

6、個(gè)新添加的葉子節(jié)點(diǎn)，并且是查找不成功時(shí)查找路徑上訪問(wèn)的最后一個(gè)節(jié)點(diǎn)的左孩子或右孩子的節(jié)點(diǎn)。一個(gè)無(wú)序系列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序系列，構(gòu)造樹(shù)的過(guò)程即為對(duì)無(wú)序系列進(jìn)行排序的過(guò)程， 并且每次插入的節(jié)點(diǎn)都是二叉排序樹(shù)上新的葉子節(jié)點(diǎn)，則在進(jìn)行插入操作時(shí)，不必移動(dòng)其他節(jié)點(diǎn)，僅需改變某個(gè)節(jié)點(diǎn)的指針由空變?yōu)榉强占纯伞６媾判驑?shù)的插入算法為bstreeInsertBST(bstreet,intkey,nametypename,double grade)若二叉排序樹(shù)中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時(shí)，插入元素并返回TRUE。3.5查找模塊二叉排序樹(shù)又稱二叉查找樹(shù)，當(dāng)二叉排序樹(shù)不為空時(shí)，首先將給定

7、的值和根節(jié)點(diǎn)的關(guān)鍵字比較，若相等則查找成功，否則將依據(jù)給定的值和根節(jié)點(diǎn)關(guān)鍵字之間的大小關(guān)系，分別在左子樹(shù)或右子樹(shù)上繼續(xù)進(jìn)行查找。為此定義一個(gè)二叉排序樹(shù)的查找算法為bstnode *SearchBST(bstreet,keytype key) 在根指針t所指向的二叉排序樹(shù)中查找關(guān)鍵字等于key的數(shù)據(jù)元素，如成功，返回指向該元素節(jié)點(diǎn)的指針，否則返回空指針。3.6二叉排序樹(shù)的遍歷先序遍歷也叫做先根遍歷。首先訪問(wèn)根結(jié)點(diǎn)然后遍歷左子樹(shù)，最后遍歷右子樹(shù)。在遍歷左、右子樹(shù)時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹(shù)，最后遍歷右子樹(shù)，如果二叉樹(shù)為空則返回。其實(shí)過(guò)程為：先遍歷左子樹(shù)root->left->l

8、eft->left.->null，由于是先序遍歷，因此一遇到節(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)左子樹(shù)遍歷完畢后從棧中彈出最后一個(gè)訪問(wèn)的節(jié)點(diǎn)，然后訪問(wèn)其右子樹(shù)?；舅惴ㄋ枷耄?.先訪問(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)

9、的右孩子存在，則將該指針指向的右孩子節(jié)點(diǎn)重復(fù)執(zhí)行以上步驟，直到桟為空為止。操作函數(shù)為void x_print(Tree T)中序遍歷：中序遍歷和先序遍歷訪問(wèn)的順序不同。中序遍歷訪問(wèn)順序?yàn)橹行虮闅v左子數(shù)，在訪問(wèn)根節(jié)點(diǎn)，最后中序遍歷右子樹(shù)。先序遍歷是先訪問(wèn),再入棧；而中序遍歷則是先入棧，彈棧后再訪問(wèn)。將二叉樹(shù)的根節(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ù)為void z_print(Tree T )。后序遍歷：先后序遍歷左子樹(shù)，在

10、后序遍歷右子樹(shù)，最后訪問(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有右孩子，且右孩子沒(méi)有別訪問(wèn)過(guò)，則p=p->rchild。操作函數(shù)為void h_print(Tree T)4.源代碼#include <iostream>/* run this program using the console pauser or add your own getch

11、, system("pause") or input loop */#include<stdio.h>#include<iostream>#include<string>#include<time.h>#include <iomanip>using namespace std;typedef stringnametype;typedef unsigned long keytype;typedefstruct node /結(jié)點(diǎn)的結(jié)構(gòu)體keytype key; nametype name; int grade;stru

12、ct node *lchild,*rchild;bstnode;typedefbstnode *bstree;/棧的定義/typedefstruct bstree *base;bstree *top;intstacksize;Sqstack;intInitStack (Sqstack&s) /s.base=(bstree*)malloc(1000 * sizeof(int);s.top=s.base;return 1;int Push(Sqstack&s ,node *e) *s.top=e;s.top=s.top+1;return 1;int Pop(Sqstack&

13、s, bstree&e) if(s.top=s.base)return 0;elses.top=s.top-1;e=*s.top;return 1;/非遞歸歷遍并輸出結(jié)點(diǎn)信息/*-先序非遞歸遍歷-*/voidx_print(node *t)Sqstack s;InitStack(s);bstnode *p;p=t;while(p|!(s.top=s.base)if(p) Push(s,p);cout<<p->key<<"t"<<setw(20);cout<<p->name<<"t&qu

14、ot;<<setw(20);cout<<p->grade<<"t"<<endl;p=p->lchild;elsePop(s,p);p=p->rchild;/*-中序非遞歸遍歷-*/voidz_print(node *t)Sqstack s;InitStack(s);bstnode *p;p=t;while(p|!(s.top=s.base)if(p) Push(s,p);p=p->lchild;elsePop(s,p);cout<<p->key<<"t"

15、<<setw(20);cout<<p->name<<"t"<<setw(20);cout<<p->grade<<"t"<<endl;p=p->rchild;/*-非遞歸后序遍歷-*/voidh_print(node *t)Sqstack s;InitStack(s);node *p,*q;p=t;q=NULL;while(p | !(s.top=s.base)if(p)Push(s,p); p=p->lchild;else p=*(s.top-1)

16、;if(p->rchild=q) Pop(s,q);p=NULL;cout<<q->key<<"t"<<setw(20);cout<<q->name<<"t"<<setw(20);cout<<q->grade<<"t"<<endl;else p=p->rchild;q=NULL; /遞歸查找二叉樹(shù)/ /*-歸查找，若找到就返回指向該結(jié)點(diǎn)的指針，否則返回空-*/bstnode *SearchBST(b

17、street,keytype key) if(t=NULL|key=t->key)return t;if(key<t->key)returnSearchBST(t->lchild ,key);elsereturnSearchBST(t->rchild ,key);/-給定學(xué)生信息插入到二叉樹(shù)中-/bstreeInsertBST(bstreet,intkey,nametypename,double grade)bstreep,q;if(t=NULL) t=new bstnode();t->key=key;t->name=name;t->grade=

18、grade;t->lchild=t->rchild=NULL;elsep=t;while(p) q=p;if(p->key>key)p=q->lchild;else if(p->key<key)p=q->rchild;elsecout<<endl;cout<<"樹(shù)中已有該節(jié)點(diǎn):"<<key<<endl;cout<<endl;return t;p=new bstnode(); p->key=key;p->name=name;p->grade=grade

19、;p->lchild=p->rchild=NULL;if(q->key>key)q->lchild=p;elseq->rchild=p;return t;/-二叉樹(shù)排序樹(shù)的構(gòu)建-/bstreeCreatTree() bstree t=NULL;keytype key;nametype name;double grade;printf("n*本系統(tǒng)由二胡科技所有成員公同組建！*nnn");printf("請(qǐng)輸入-學(xué)號(hào)-姓名-成績(jī)-（輸入0時(shí)結(jié)束）:n");cin>>key;if(key=0)return t;

20、cin>>name;cin>>grade;while(key) t=InsertBST(t,key,name,grade);printf("請(qǐng)輸入-學(xué)號(hào)-姓名-成績(jī)-（輸入0時(shí)結(jié)束）:n");cin>>key;if(key=0)break;cin>>name;cin>>grade;return t;/-刪除樹(shù)中的結(jié)點(diǎn)-/void Delete(bstree&p) bstreeq,s;if(!p->rchild)q=p;p=q->lchild ;delete q;else if(!p->lc

21、hild)q=p;p=p->rchild;delete q;elseq=p;s=p->lchild;while(s->rchild)q=s;s=s->rchild;p->name=s->name;if(q!=p)q->rchild=s->lchild;elseq->lchild=s->lchild;delete s;voidDeleteData(bstree&t,keytype key)if(!t)printf("沒(méi)有該信息，請(qǐng)重新輸入！n");cin>>key;DeleteData(t,key

22、);elseif(t->key=key)Delete(t); printf("刪除成功！n");else if(t->key>key)DeleteData(t->lchild,key); elseDeleteData(t->rchild,key); /二叉樹(shù)的深度intTreeDepth(bstree t)intleft,right,max;if(t!=NULL)left=TreeDepth(t->lchild);right=TreeDepth(t->rchild);max=left>right?left:right;retu

23、rn max+1;elsereturn 0;/樹(shù)狀輸出二叉樹(shù)voidPrintTree(bstreet,int layer)int k;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è)試-/int main()int d;/system("cls");system(&quo

24、t;Color 2f");keytype key;bstree t=NULL; t=CreatTree();d=TreeDepth(t);printf("二叉排序樹(shù)的樹(shù)形表示如下n");PrintTree(t,d);char choose;nametype name;bstree p;double grade;printf(" n");printf("-請(qǐng)輸入你要選擇的操作-n");printf(" |-|n");printf(" |-|n");printf(" | a 插入

25、信息 |n");printf(" | b 刪除信息 |n");printf(" | c 查詢信息 |n");printf(" | d 修改信息 |n");printf(" | 0 退出 |n");printf(" | e 對(duì)二叉排序樹(shù)進(jìn)行非遞歸遍歷 |n");printf(" |-|n");printf(" |-|n");printf("n");printf("需要選擇的操作為：");cin>>

26、choose;cout<<endl;while(choose)switch(choose)case 'a':printf("輸入需要插入的學(xué)生信息信息（學(xué)號(hào)為0時(shí)結(jié)束）.n");printf("請(qǐng)輸入-學(xué)號(hào)-姓名-成績(jī)-（輸入0時(shí)結(jié)束）:n");cin>>key;if(key=0) PrintTree(t,d);printf("n*插入信息結(jié)束！");break;cin>>name;cin>>grade;while(key) t=InsertBST(t,key,name,

27、grade);printf("請(qǐng)輸入-學(xué)號(hào)-姓名-成績(jī)-（輸入0時(shí)結(jié)束）:n");cin>>key;if(key=0)printf("插入信息結(jié)束！");break;cin>>name;cin>>grade;break;case 'b':printf("請(qǐng)輸入要?jiǎng)h除信息學(xué)生的學(xué)號(hào)：n");cin>>key;DeleteData(t,key); d=TreeDepth(t);printf("刪除結(jié)點(diǎn)后二叉樹(shù)的樹(shù)形顯示如下n");PrintTree(t,d

28、);break;case 'c':cout<<"請(qǐng)輸入要查詢學(xué)生的學(xué)號(hào)："<<endl;cin>>key;p=SearchBST(t,key);if(p=NULL)cout<<"無(wú)查詢的關(guān)鍵字："<<key<<endl;elsecout<<"成績(jī)"<<"t"<<setw(20)<<"姓名"<<"t"<<setw(20)

29、<<"學(xué)號(hào)"<<endl;cout<<p->key<<"t"<<setw(20);cout<<p->name<<"t"<<setw(20);cout<<p->grade<<endl;break;case 'd':printf("請(qǐng)輸入要修改學(xué)生的學(xué)號(hào)：n");cin>>key;p=SearchBST(t,key);if(p=NULL)cout<&

30、lt;"無(wú)你所要修改的關(guān)鍵字："<<key<<endl;elseprintf("n請(qǐng)輸入修改的姓名：");cin>>name;printf("n請(qǐng)輸入修改的成績(jī)：");cin>>grade;p->name=name;p->grade=grade;printf("n修改成功！n");break;case 'e':if(!t)printf("沒(méi)有任何信息，請(qǐng)先輸入信息！");elsecout<<"學(xué)號(hào)"<<"t"<<setw(20)<<"姓名"&