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

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

2、ee()操作建立二叉排序樹。 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ù)組和二叉排序樹的查找效率進行比較比較。

3、2.2創(chuàng)建二叉排序樹CreatTree模塊從鍵盤中輸入關(guān)鍵字及記錄，并同時調(diào)用插入函數(shù)并不斷進行插入。最后，返回根節(jié)點T。2.3刪除模塊：二叉排序樹上刪除一個階段相當(dāng)于刪去有序系列中的一個記錄，只要在刪除某個節(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)通常不是一次生成的，而是在查找的過程中，當(dāng)樹中不存在關(guān)鍵字等于給定值得節(jié)點時在進行插入。新插入的節(jié)點一定是一個新添加的葉子節(jié)點，并且是查找不成功時查找路徑上訪問的最后一個節(jié)點的左孩子或右孩

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

6、關(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二叉排序樹的遍歷先序遍歷也叫做 HYPERLINK /view/2872148.htm t _blank 先根遍歷。首先訪問根結(jié)點然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結(jié)點，然后遍

7、歷左子樹，最后遍歷右子樹，如果二叉樹為空則返回。其實過程為：先遍歷左子樹root-left-left-left.-null，由于是先序遍歷，因此一遇到節(jié)點，便需要立即訪問；由于一直走到最左邊后，需要逐步返回到父節(jié)點訪問右節(jié)點，因此必須有一個措施能夠?qū)?jié)點序列回溯。其一可以用棧記憶在訪問途中將依次遇到的節(jié)點保存下來。根據(jù)棧的先進后出、后進先出的特點特點。則可以用棧保存。每次都將遇到的節(jié)點壓入棧，當(dāng)左子樹遍歷完畢后從棧中彈出最后一個訪問的節(jié)點，然后訪問其右子樹。基本算法思想：1.先訪問根節(jié)點，將根節(jié)點入棧2.重復(fù)執(zhí)行兩大步驟：如果該節(jié)點左孩子存在，則訪問該左孩子節(jié)點，并將其指針入棧。重復(fù)以上操作，

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

9、數(shù)為void z_print(Tree 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#include#include#include#include using namespace

10、 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 stacksize;Sqstack;int InitStack (Sqstack &s) /建立一個空棧s.base=(bs

11、tree*)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;/非遞歸歷遍并輸出結(jié)點信息/*-先序非遞歸遍歷-*/void x_print(node *t)Sqstack s;InitStack(s);bstnode

12、*p;p=t;while(p|!(s.top=s.base)if(p) Push(s,p);coutkeytsetw(20);coutnametsetw(20);coutgradetlchild;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);coutkeytsetw(20);coutnametsetw(20);coutgr

13、adetrchild;/*-非遞歸后序遍歷-*/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; coutkeytsetw(20);coutnametsetw(20);coutgradetrchild;q=NULL; /遞歸查找二叉樹/ /*-歸查找，若找到就返回指向該結(jié)點的指針，否則返回空-*/bstn

14、ode *SearchBST(bstree t,keytype key) if(t=NULL|key=t-key)return t;if(keykey)return SearchBST(t-lchild ,key);else return SearchBST(t-rchild ,key);/-給定學(xué)生信息插入到二叉樹中-/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-gr

15、ade=grade;t-lchild=t-rchild=NULL;elsep=t;while(p) /樹已存在，按照二叉排序樹的特性查找q=p;if(p-keykey)p=q-lchild;else if(p-keyrchild;elsecoutendl;cout樹中已有該節(jié)點:keyendl;coutkey=key;p-name=name;p-grade=grade;p-lchild=p-rchild=NULL;if(q-keykey)q-lchild=p;elseq-rchild=p;return t;/-二叉樹排序樹的構(gòu)建-/bstree CreatTree() /不斷輸入學(xué)生信息以插入

16、到二叉樹中bstree t=NULL;keytype key;nametype name;double grade;cout請輸入-學(xué)號-姓名-成績-（輸入0時結(jié)束）:key;if(key=0)return t;cinname;cingrade;while(key) /key=0時退出t=InsertBST(t,key,name,grade);cout請輸入-學(xué)號-姓名-成績-（輸入0時結(jié)束）:key;if(key=0)break;cinname; cingrade;return t;/-刪除樹中的結(jié)點-/void Delete(bstree &p) /刪除結(jié)點的函數(shù)bstree q,s;if

17、(!p-rchild)q=p;p=q-lchild ;delete q;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)coutkey;DeleteData(t,key);elseif(t-key=key)Delete(t); /若找

18、到結(jié)點直接刪除cout刪除成功！keykey)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 start,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;/c

19、out（輸入0時結(jié)束）endl;cout請輸入-學(xué)號-姓名-成績-（輸入0時結(jié)束）:key;if(key=0) return ;cinname;cingrade;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請輸入-學(xué)號-姓名-成績-（輸入0時結(jié)束）:key;if(key=0)break;cinname;cingrade;num+;coutendl; coutd;

20、while(d!=NULL) switch(d) case 0: cout返回選擇界面endl;break; case 1:cout數(shù)組查詢！endl;cout請輸入查詢的成績：key;start=clock();while(a=10000000) /循環(huán)模擬數(shù)組查找while(b=100)cout數(shù)組查詢：無查詢信息，花費時間: end-start 毫秒endl;elsecout數(shù)組查詢：查到信息，花費時間: end-start 毫秒endl;int key1=atoi(key.c_str(); /同上轉(zhuǎn)化start1=clock();while(c=10000000) /用循環(huán)來模擬樹中查

21、找p=SearchBST(t,key1);c+;end1=clock();if(p=NULL)cout樹查詢：無查詢信息，花費時間: end1-start1 毫秒endl;else cout樹查詢：查到信息，花費時間: end1-start1 毫秒endl;a=0;b=0;c=0;break; coutd;/二叉樹的深度int TreeDepth(bstree t)int left,right,max;if(t!=NULL)left=TreeDepth(t-lchild);right=TreeDepth(t-rchild);max=leftright?left:right;return max

22、+1;elsereturn 0;/樹狀輸出二叉樹void PrintTree(bstree t,int layer)int k;if(t=NULL)return ;PrintTree(t-rchild,layer+1);for(k=0;klayer;k+)cout ;coutkeylchild,layer+1);/-主函數(shù)測試-/int main()int d; keytype key;bstree t=NULL; t=CreatTree();d=TreeDepth(t);cout二叉排序樹的樹形表示如下endl; PrintTree(t,d);char choose;nametype nam

23、e;bstree p;double grade; cout endl;cout-請輸入你要選擇的操作-endl;cout |-|endl;cout |-|endl;cout | a 插入信息 |endl;cout | b 刪除信息 |endl;cout | c 查詢信息 |endl;cout | d 修改信息 |endl;cout | 0 退出 |endl;cout | e 對二叉排序樹進行非遞歸遍歷 |endl;cout | f 進行數(shù)組和二叉樹查找效率實驗|endl;cout |-|endl;cout |-|endl;coutendl;coutchoose;coutendl;while(c

24、hoose)switch(choose)case a:/cout輸入學(xué)生信息信息（學(xué)號為0時結(jié)束）.endl;cout請輸入-學(xué)號-姓名-成績-（輸入0時結(jié)束）:key;if(key=0) /*PrintTree(t,d);break;*/cinname;cingrade;while(key) t=InsertBST(t,key,name,grade);cout請輸入-學(xué)號-姓名-成績-:key;if(key=0)break;cinname; cingrade;break;case b:cout請輸入要刪除信息學(xué)生的成績：key;DeleteData(t,key); d=TreeDepth(t

25、); cout刪除結(jié)點后二叉樹的樹形顯示如下endl; PrintTree(t,d);break;case c:cout請輸入要查詢的成績：key;p=SearchBST(t,key);if(p=NULL)cout無查詢的關(guān)鍵字：keyendl;elsecout成績tsetw(20)姓名tsetw(20)學(xué)號endl; coutkeytsetw(20);coutnametsetw(20); coutgradeendl;break;case d:cout請輸入要修改的學(xué)號：key;p=SearchBST(t,key);if(p=NULL)cout無你所要修改的關(guān)鍵字：keyendl;elsecoutname;coutgrade;p-name=name;p-grade=grade;break;case e:if(!t)cout沒有任何信息，請先輸入信息！;elsecout學(xué)號tsetw(20)姓名tsetw(20)成績endl;cout-非遞歸先序遍歷-endl;coutendl;x_print(t);cout-非遞歸中序遍歷-endl;coutendl;z_print(t);cout-非遞歸后序