第九組數據結構課程設計(二叉排序樹實現(xiàn))

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

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

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

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

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

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

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

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

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

10、后序遍歷右子樹，最后訪問根節(jié)點。先將根節(jié)點入棧，如果該節(jié)點左孩子節(jié)點存在，將該節(jié)點左孩子節(jié)點入棧。重復執(zhí)行此操作，直到節(jié)點左孩子節(jié)點為空。取棧頂元素，并賦值給P，如果P的右孩子為空或P的右孩子等于q（即如果p的右孩子已訪問，則訪問根節(jié)點，即p指向的節(jié)點，并用q來記錄剛剛訪問的節(jié)點的指針），若p有右孩子，且右孩子沒有別訪問過，則p=p->rchild。操作函數為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 /結點的結構體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;/非遞歸歷遍并輸出結點信息/*-先序非遞歸遍歷-*/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; /遞歸查找二叉樹/ /*-歸查找，若找到就返回指向該結點的指針，否則返回空-*/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);/-給定學生信息插入到二叉樹中-/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<<"樹中已有該節(jié)點:"<<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;/-二叉樹排序樹的構建-/bstreeCreatTree() bstree t=NULL;keytype key;nametype name;double grade;printf("n*本系統(tǒng)由二胡科技所有成員公同組建！*nnn");printf("請輸入-學號-姓名-成績-（輸入0時結束）:n");cin>>key;if(key=0)return t;

20、cin>>name;cin>>grade;while(key) t=InsertBST(t,key,name,grade);printf("請輸入-學號-姓名-成績-（輸入0時結束）:n");cin>>key;if(key=0)break;cin>>name;cin>>grade;return t;/-刪除樹中的結點-/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("沒有該信息，請重新輸入！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); /二叉樹的深度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;/樹狀輸出二叉樹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);/-主函數測試-/int main()int d;/system("cls");system(&quo

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

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

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

27、grade);printf("請輸入-學號-姓名-成績-（輸入0時結束）:n");cin>>key;if(key=0)printf("插入信息結束！");break;cin>>name;cin>>grade;break;case 'b':printf("請輸入要刪除信息學生的學號：n");cin>>key;DeleteData(t,key); d=TreeDepth(t);printf("刪除結點后二叉樹的樹形顯示如下n");PrintTree(t,d

28、);break;case 'c':cout<<"請輸入要查詢學生的學號："<<endl;cin>>key;p=SearchBST(t,key);if(p=NULL)cout<<"無查詢的關鍵字："<<key<<endl;elsecout<<"成績"<<"t"<<setw(20)<<"姓名"<<"t"<<setw(20)

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

30、lt;"無你所要修改的關鍵字："<<key<<endl;elseprintf("n請輸入修改的姓名：");cin>>name;printf("n請輸入修改的成績：");cin>>grade;p->name=name;p->grade=grade;printf("n修改成功！n");break;case 'e':if(!t)printf("沒有任何信息，請先輸入信息！");elsecout<<"學號"<<"t"<<setw(20)<<"姓名"&