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

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

2、作建立二叉排序樹。 2.在二叉排序樹t中通過操作bstree InsertBST(bstree t,int key,nametype name,double grade)插入一個節(jié)點。3. 從二叉排序樹t中通過操作void Delete(bstree &p)刪除任意節(jié)點。4. 在二叉排序樹t中通過操作bstnode *SearchBST(bstree t,keytype key)查找節(jié)點。5. 在二叉排序樹t中通過操作p=SearchBST(t,key)查詢，并修改節(jié)點信息6. 非遞歸遍歷二叉排序樹。7. 定義函數(shù)void compare()對數(shù)組和二叉排序樹的查找效率進行比較比較。2

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

4、左子樹，而*p的右子樹為*s的右子樹，其二可以令*p的直接前驅(qū)（或直接后繼）替代*p，然后再從二叉排序樹中刪去它的直接前驅(qū)（或直接后繼）。在二叉排序樹中刪除一個節(jié)點的算法為void DeleteData(bstree &t,keytype key)若二叉排序樹t中存在關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素節(jié)點，并返回TRUE，否則返回FALSE。2.4插入模塊二叉排序樹是一種動態(tài)樹表，其特點是樹的結(jié)構(gòu)通常不是一次生成的，而是在查找的過程中，當樹中不存在關(guān)鍵字等于給定值得節(jié)點時在進行插入。新插入的節(jié)點一定是一個新添加的葉子節(jié)點，并且是查找不成功時查找路徑上訪問的最后一個節(jié)點的左孩子

5、或右孩子的節(jié)點。一個無序系列可以通過構(gòu)造一棵二叉排序樹而變成一個有序系列，構(gòu)造樹的過程即為對無序系列進行排序的過程， 并且每次插入的節(jié)點都是二叉排序樹上新的葉子節(jié)點，則在進行插入操作時，不必移動其他節(jié)點，僅需改變某個節(jié)點的指針由空變?yōu)榉强占纯?。二叉排序樹的插入算法為bstree InsertBST(bstree t,int key,nametype name,double grade) 若二叉排序樹中不存在關(guān)鍵字等于key的數(shù)據(jù)元素時，插入元素并返回TRUE。2.5查找模塊二叉排序樹又稱二叉查找樹，當二叉排序樹不為空時，首先將給定的值和根節(jié)點的關(guān)鍵字比較，若相等則查找成功，否則將依據(jù)給定的值和

6、根節(jié)點關(guān)鍵字之間的大小關(guān)系，分別在左子樹或右子樹上繼續(xù)進行查找。為此定義一個二叉排序樹的查找算法為bstnode *SearchBST(bstree t,keytype key) 在根指針t所指向的二叉排序樹中查找關(guān)鍵字等于key的數(shù)據(jù)元素，如成功，返回指向該元素節(jié)點的指針，否則返回空指針。2.6效率比較compare模塊void compare()對數(shù)組和二叉排序樹的查找效率進行比較比較。2.7二叉排序樹的遍歷先序遍歷也叫做先根遍歷。首先訪問根結(jié)點然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍歷左子樹，最后遍歷右子樹，如果二叉樹為空則返回。其實過程為：先遍歷左子

7、樹root->left->left->left.->null，由于是先序遍歷，因此一遇到節(jié)點，便需要立即訪問；由于一直走到最左邊后，需要逐步返回到父節(jié)點訪問右節(jié)點，因此必須有一個措施能夠?qū)?jié)點序列回溯。其一可以用棧記憶在訪問途中將依次遇到的節(jié)點保存下來。根據(jù)棧的先進后出、后進先出的特點特點。則可以用棧保存。每次都將遇到的節(jié)點壓入棧，當左子樹遍歷完畢后從棧中彈出最后一個訪問的節(jié)點，然后訪問其右子樹?；舅惴ㄋ枷耄?.先訪問根節(jié)點，將根節(jié)點入棧2.重復(fù)執(zhí)行兩大步驟：如果該節(jié)點左孩子存在，則訪問該左孩子節(jié)點，并將其指針入棧。重復(fù)以上操作，直到節(jié)點的左孩子不存在。將棧頂?shù)脑兀?/p>

8、即其指針出棧，回到父節(jié)點，如果該指針節(jié)點的右孩子存在，則將該指針指向的右孩子節(jié)點重復(fù)執(zhí)行以上步驟，直到桟為空為止。操作函數(shù)為void x_print(Tree T)中序遍歷：中序遍歷和先序遍歷訪問的順序不同。中序遍歷訪問順序為中序遍歷左子數(shù)，在訪問根節(jié)點，最后中序遍歷右子樹。先序遍歷是先訪問,再入棧；而中序遍歷則是先入棧，彈棧后再訪問。將二叉樹的根節(jié)點入棧，如果該節(jié)點有左孩子，將左孩子直接入棧，重復(fù)該操作，直到該節(jié)點無左孩子；在將棧頂元素出棧，并訪問該節(jié)點指向的節(jié)點，如果該指針指向的右孩子存在，則將當前指針指向右孩子節(jié)點。重復(fù)執(zhí)行步驟直到棧為空為止。操作函數(shù)為void z_print(Tree

9、 T )。后序遍歷：先后序遍歷左子樹，在后序遍歷右子樹，最后訪問根節(jié)點。先將根節(jié)點入棧，如果該節(jié)點左孩子節(jié)點存在，將該節(jié)點左孩子節(jié)點入棧。重復(fù)執(zhí)行此操作，直到節(jié)點左孩子節(jié)點為空。取棧頂元素，并賦值給P，如果P的右孩子為空或P的右孩子等于q（即如果p的右孩子已訪問，則訪問根節(jié)點，即p指向的節(jié)點，并用q來記錄剛剛訪問的節(jié)點的指針），若p有右孩子，且右孩子沒有別訪問過，則p=p->rchild。操作函數(shù)為void h_print(Tree T)3.源代碼#include<stdio.h>#include<iostream>#include<string>#i

10、nclude<time.h>#include <iomanip>using namespace std;typedef string nametype;typedef unsigned long keytype;typedef struct node /結(jié)點的結(jié)構(gòu)體keytype key; nametype name; int grade;struct node *lchild,*rchild;bstnode;typedef bstnode *bstree;/棧的定義/typedef struct /棧結(jié)構(gòu)bstree *base;bstree *top;int sta

11、cksize;Sqstack;int InitStack (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 &s, bstree &e)/出棧if(s.top=s.base)return 0;else s.top=s.top-1;e=*s.top;return 1;/非遞

12、歸歷遍并輸出結(jié)點信息/*-先序非遞歸遍歷-*/void x_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"<<setw(20);cout<<p->grade<<"t"<<endl;p=p

13、->lchild;else Pop(s,p);p=p->rchild;/*-中序非遞歸遍歷-*/void z_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;else Pop(s,p);cout<<p->key<<"t"<<setw(20);cout<<p->name<<"t"<<setw(20);

14、cout<<p->grade<<"t"<<endl;p=p->rchild;/*-非遞歸后序遍歷-*/void h_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); if(p->rchild=q) Pop(s,q);p=NULL; cout<<q->key<<"

15、t"<<setw(20);cout<<q->name<<"t"<<setw(20);cout<<q->grade<<"t"<<endl; else p=p->rchild;q=NULL; /遞歸查找二叉樹/ /*-歸查找，若找到就返回指向該結(jié)點的指針，否則返回空-*/bstnode *SearchBST(bstree t,keytype key) if(t=NULL|key=t->key)return t;if(key<t->

16、key)return SearchBST(t->lchild ,key);else return SearchBST(t->rchild ,key);/-給定學生信息插入到二叉樹中-/bstree InsertBST(bstree t,int key,nametype name,double grade)bstree p,q;if(t=NULL) /樹初始為空，新建二叉樹t=new bstnode();t->key=key; t->name=name;t->grade=grade;t->lchild=t->rchild=NULL;elsep=t;whi

17、le(p) /樹已存在，按照二叉排序樹的特性查找q=p;if(p->key>key)p=q->lchild;else if(p->key<key)p=q->rchild;elsecout<<endl;cout<<"樹中已有該節(jié)點:"<<key<<endl;cout<<endl;return t;p=new bstnode(); /找不到結(jié)點就新建一個結(jié)點插入到二叉排序樹中p->key=key;p->name=name;p->grade=grade;p->l

18、child=p->rchild=NULL;if(q->key>key)q->lchild=p;elseq->rchild=p;return t;/-二叉樹排序樹的構(gòu)建-/bstree CreatTree() /不斷輸入學生信息以插入到二叉樹中bstree t=NULL;keytype key;nametype name;double grade;cout<<"請輸入-學號-姓名-成績-（輸入0時結(jié)束）:"<<endl;cin>>key;if(key=0)return t;cin>>name;cin

19、>>grade;while(key) /key=0時退出t=InsertBST(t,key,name,grade);cout<<"請輸入-學號-姓名-成績-（輸入0時結(jié)束）:"<<endl; cin>>key;if(key=0)break;cin>>name; cin>>grade;return t;/-刪除樹中的結(jié)點-/void Delete(bstree &p) /刪除結(jié)點的函數(shù)bstree q,s;if(!p->rchild)q=p;p=q->lchild ;delete q;

20、else if(!p->lchild)q=p;p=p->rchild;delete q;else q=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;void DeleteData(bstree &t,keytype key)if(!t)cout<<"沒有該信息，請重新輸入！" cin>&

21、gt;key;DeleteData(t,key);elseif(t->key=key)Delete(t); /若找到結(jié)點直接刪除cout<<"刪除成功！"<<endl;else if(t->key>key)DeleteData(t->lchild,key); /結(jié)點數(shù)據(jù)比查找關(guān)鍵字大，繼續(xù)在其左子樹中查找elseDeleteData(t->rchild,key); /結(jié)點數(shù)據(jù)比查找關(guān)鍵字小，繼續(xù)在其右子樹中查找/數(shù)組和二叉排序樹的查找效率比較/void compare()bstree t=NULL;clock_t sta

22、rt,end,start1,end1;int num=0;int a=0;int b=0;int c=0;int d=1;bstree p;string key,name;double grade;nametype str 1003;/cout<<"（輸入0時結(jié)束）"<<endl;cout<<"請輸入-學號-姓名-成績-（輸入0時結(jié)束）:"<<endl;cin>>key;if(key="0") return ;cin>>name;cin>>grade;

23、while(key!="0")strnum0=key;strnum1=name;strnum2=grade;int key1=atoi(key.c_str(); /用庫函數(shù)將字符串轉(zhuǎn)化為關(guān)鍵字的int型t=InsertBST(t,key1,name,grade); /插入結(jié)點cout<<"請輸入-學號-姓名-成績-（輸入0時結(jié)束）:"<<endl;cin>>key;if(key="0")break;cin>>name;cin>>grade;num+;cout<<e

24、ndl; cout<<"進行數(shù)組和二叉排序樹的查詢效率比較（比較：1 不比較：0）" cin>>d;while(d!=NULL) switch(d) case 0: cout<<"返回選擇界面"<<endl;break; case 1:cout<<"數(shù)組查詢！"<<endl;cout<<"請輸入查詢的成績："<<endl;cin>>key;start=clock();while(a<=10000000)

25、 /循環(huán)模擬數(shù)組查找while(b<=99)if(strb0=key)b=100;elseb+;b=0;a+;end=clock();if(num>=100)cout<<"數(shù)組查詢：無查詢信息，花費時間: "<<end-start<<" 毫秒"<<endl;elsecout<<"數(shù)組查詢：查到信息，花費時間: "<<end-start<<" 毫秒"<<endl;int key1=atoi(key.c_str(

26、); /同上轉(zhuǎn)化start1=clock();while(c<=10000000) /用循環(huán)來模擬樹中查找p=SearchBST(t,key1);c+;end1=clock();if(p=NULL)cout<<"樹查詢：無查詢信息，花費時間: "<<end1-start1<<" 毫秒"<<endl;else cout<<"樹查詢：查到信息，花費時間: "<<end1-start1<<" 毫秒"<<endl;a=0;

27、b=0;c=0;break; cout<<"是否繼續(xù)進行操作（是：1 否：0）："cin>>d;/二叉樹的深度int TreeDepth(bstree t)int left,right,max;if(t!=NULL)left=TreeDepth(t->lchild);right=TreeDepth(t->rchild);max=left>right?left:right;return max+1;elsereturn 0;/樹狀輸出二叉樹void PrintTree(bstree t,int layer)int k;if(t=NUL

28、L)return ;PrintTree(t->rchild,layer+1);for(k=0;k<layer;k+)cout<<" "cout<<t->key<<"n"PrintTree(t->lchild,layer+1);/-主函數(shù)測試-/int main()int d; keytype key;bstree t=NULL; t=CreatTree();d=TreeDepth(t);cout<<"二叉排序樹的樹形表示如下"<<endl; Print

29、Tree(t,d);char choose;nametype name;bstree p;double grade; cout<<" "<<endl;cout<<"-請輸入你要選擇的操作-"<<endl;cout<<" |-|"<<endl;cout<<" |-|"<<endl;cout<<" | a 插入信息 |"<<endl;cout<<" | b 刪

30、除信息 |"<<endl;cout<<" | c 查詢信息 |"<<endl;cout<<" | d 修改信息 |"<<endl;cout<<" | 0 退出 |"<<endl;cout<<" | e 對二叉排序樹進行非遞歸遍歷 |"<<endl;cout<<" | f 進行數(shù)組和二叉樹查找效率實驗|"<<endl;cout<<" |

31、-|"<<endl;cout<<" |-|"<<endl;cout<<endl;cout<<"需要選擇的操作為："cin>>choose;cout<<endl;while(choose)switch(choose)case 'a':/cout<<"輸入學生信息信息（學號為0時結(jié)束）."<<endl;cout<<"請輸入-學號-姓名-成績-（輸入0時結(jié)束）:"<<

32、;endl;cin>>key;if(key=0) /*PrintTree(t,d);break;*/cin>>name;cin>>grade;while(key) t=InsertBST(t,key,name,grade);cout<<"請輸入-學號-姓名-成績-:"<<endl;cin>>key;if(key=0)break;cin>>name; cin>>grade;break;case 'b':cout<<"請輸入要刪除信息學生的成績：

33、"<<endl;cin>>key;DeleteData(t,key); d=TreeDepth(t); cout<<"刪除結(jié)點后二叉樹的樹形顯示如下"<<endl; PrintTree(t,d);break;case 'c':cout<<"請輸入要查詢的成績："<<endl;cin>>key;p=SearchBST(t,key);if(p=NULL)cout<<"無查詢的關(guān)鍵字："<<key<&l

34、t;endl;elsecout<<"成績"<<"t"<<setw(20)<<"姓名"<<"t"<<setw(20)<<"學號"<<endl; cout<<p->key<<"t"<<setw(20);cout<<p->name<<"t"<<setw(20); cout<<

35、;p->grade<<endl;break;case 'd':cout<<"請輸入要修改的學號："<<endl;cin>>key;p=SearchBST(t,key);if(p=NULL)cout<<"無你所要修改的關(guān)鍵字："<<key<<endl;elsecout<<"請輸入修改的姓名："cin>>name;cout<<"請輸入修改的成績："cin>>grade

36、;p->name=name;p->grade=grade;break;case 'e':if(!t)cout<<"沒有任何信息，請先輸入信息！"elsecout<<"學號"<<"t"<<setw(20)<<"姓名"<<"t"<<setw(20)<<"成績"<<endl;cout<<"-非遞歸先序遍歷-"<<endl;cout<<endl;x_print(t);cout<<"-非遞歸中序遍歷-"<<endl;cout<<endl;z_print(t);cout<<"-非遞歸后序遍歷-"<<endl;cout<<endl;h_print(t);break; case 'f':cout<<"*此實驗為獨立實驗，實驗數(shù)據(jù)獨立于外部數(shù)據(jù)*"<<endl; cout<<"*請重新輸入相關(guān)信息*