數(shù)據結構課程設計--二叉排序樹的實現(xiàn)

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：docx 頁數(shù)：21 大小：223.24KB 人氣指數(shù)：12 舉報 版權申訴

已閱讀1頁，還剩20頁未讀，繼續(xù)免費閱讀

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、　　課程設計　　課程名稱數(shù)據結構課程設計 　　題目名稱二叉排序樹的實現(xiàn) 　　學院應用數(shù)學學院 　　專業(yè)班級

2、　學號 　　學生姓名 　　指導教師 　　2013 年 12 月 26 日　　1.設計任務　　實現(xiàn)二叉排序樹，包

3、括生成、插入，刪除；　　對二叉排序樹進行先根、中根、和后根非遞歸遍歷；　　每次對樹的修改操作和遍歷操作的顯示結果都需要在屏幕上　　用樹的形狀表示出來。　　分別用二叉排序樹和數(shù)組去存儲一個班(50人以上)的成員信 <

4、;p>　　息(至少包括學號、姓名、成績3項),對比查找效率，并說明 　　為什么二叉排序樹效率高（或者低）。　　2. 函數(shù)模塊：　　2.1.主函數(shù)main模塊功能　　1.通過bstree CreatTree()操作建立二叉排

5、序樹。 　　2.在二叉排序樹t中通過操作bstree InsertBST(bstree t,int 　　key,nametype name,double grade)插入一個節(jié)點。　　3. 從二叉排序樹t中通過操作void Delete(bstree &p)刪除任意節(jié)點。<

6、;p>　　4. 在二叉排序樹t中通過操作bstnode *SearchBST(bstree t,keytype key)查找節(jié)點。　　5. 在二叉排序樹t中通過操作p=SearchBST(t,key)查詢，并修改節(jié)點信息　　6. 非遞歸遍歷二叉排序樹。　　7. 定義函數(shù)void compare()對數(shù)組和二

7、叉排序樹的查找效率進行比較比較。　　2.2創(chuàng)建二叉排序樹CreatTree模塊　　從鍵盤中輸入關鍵字及記錄，并同時調用插入函數(shù)并不斷進行插入。最后，返回根節(jié)點T。　　2.3刪除模塊：　　二叉排序樹上刪除一個階段相當于刪去有序系列中的一

8、個記錄，只要在刪除某個節(jié)點之后依舊保持二叉排序樹的性質即可。假設二叉排序樹上刪除節(jié)點為*p（指向節(jié)點的指針為p），其雙親節(jié)點為*f（節(jié)點指針為f）。若*p節(jié)點為葉子節(jié)點，則即左右均為空樹，由于刪去葉子節(jié)點不破壞整棵樹的結構，則只需修改其雙親節(jié)點的指針即可；若*p節(jié)點只有左子樹或只有右子樹，此時只要令左子樹或右子樹直接成為其雙親節(jié)點*f的左子樹即可；若*p節(jié)點的左子樹和右子樹均不為空，其一可以令*p的左子樹為*f的左子樹，而*p的右子樹為

9、*s的右子樹，其二可以令*p的直接前驅（或直接后繼）替代*p，然后再從二叉排序樹中刪去它的直接前驅（或直接后繼）。在二叉排序樹中刪除一個節(jié)點的算法為　　void DeleteData(bstree &t,keytype key)　　若二叉排序樹t中存在關鍵字等于key的數(shù)據元素，則刪除該數(shù)據元素節(jié)點，并返回TRUE，否則返回FALSE。</

10、p>　　2.4插入模塊　　二叉排序樹是一種動態(tài)樹表，其特點是樹的結構通常不是一次生成的，而是在查找的過程中，當樹中不存在關鍵字等于給定值得節(jié)點時在進行插入。新插入的節(jié)點一定是一個新添加的葉子節(jié)點，并且是查找不成功時查找路徑上訪問的最后一個節(jié)點的左孩子或右孩子的節(jié)點。一個無序系列可以通過構造一棵二叉排序樹而變成一個有序系列，構造樹的

11、過程即為對無序系列進行排序的過程，并且每次插入的節(jié)點都是二叉排序樹上新的葉子節(jié)點，則在進行插入操作時，不必移動其他節(jié)點，僅需改變某個節(jié)點的指針由空變?yōu)榉强占纯伞６媾判驑涞牟迦胨惴?lt;/p>　　bstree InsertBST(bstree t,int key,nametype name,double grade)　　若二叉排序樹中不存在關鍵字等于key的數(shù)據

12、元素時，插入元素并返回TRUE。　　2.5查找模塊　　二叉排序樹又稱二叉查找樹，當二叉排序樹不為空時，首先將給定的值和根節(jié)點的關鍵字比較，若相等則查找成功，否則將依據給定的值和根節(jié)點關鍵字之間的大小關系，分別在左子樹或右子樹上繼續(xù)進行查找。為此定義一個二叉排序樹的查找算法為

13、　bstnode *SearchBST(bstree t,keytype key) 　　在根指針t所指向的二叉排序樹中查找關鍵字等于key的數(shù)據元素，如成功，返回指向該元素節(jié)點的指針，否則返回空指針。　　2.6效率比較compare模塊　　void compare()對數(shù)組和二叉排序樹的查找效率進行比較比較。

14、　　2.7二叉排序樹的遍歷　　先序遍歷也叫做先根遍歷。首先訪問根結點然后遍歷左子樹，最后遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然后遍歷左子樹，最后遍歷右子樹，如果二叉樹為空則返回。其實過程為：先遍歷左子樹root->left->left->left...->null，由于是先序遍歷，因此一遇到節(jié)點，便需要立即訪問；由于

15、一直走到最左邊后，需要逐步返回到父節(jié)點訪問右節(jié)點，因此必須有一個措施能夠對節(jié)點序列回溯。其一可以用棧記憶在訪問途中將依次遇到的節(jié)點保存下來。根據棧的先進后出、后進先出的特點特點。則可以用棧保存。每次都將遇到的節(jié)點壓入棧，當左子樹遍歷完畢后從棧中彈出最后一個訪問的節(jié)點，然后訪問其右子樹。　　基本算法思想：　　1.先訪問

16、根節(jié)點，將根節(jié)點入棧　　2.重復執(zhí)行兩大步驟：如果該節(jié)點左孩子存在，則訪問該左孩子節(jié)點，并將其指針入棧。重復以上操作，直到節(jié)點的左孩子不存在。將棧頂?shù)脑?，即其指針出棧，回到父?jié)點，如果該指針節(jié)點的右孩子存在，則將該指針指向的右孩子節(jié)點重復執(zhí)行以上步驟，直到桟為空為止。　　操作函數(shù)為void x_print(Tree T)<

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

18、>　　操作函數(shù)為void z_print(Tree T )。　　后序遍歷：先后序遍歷左子樹，在后序遍歷右子樹，最后訪問根節(jié)點。先將根節(jié)點入棧，如果該節(jié)點左孩子節(jié)點存在，將該節(jié)點左孩子節(jié)點入棧。重復執(zhí)行此操作，直到節(jié)點左孩子節(jié)點為空。取棧頂元素，并賦值給P，如果P的右孩子為空或P的右孩子等于q（即如果p的右孩子已訪問，則訪問根節(jié)點，即p指向的節(jié)點，并用q來記錄剛剛訪問的節(jié)點的指針），若p有右

19、孩子，且右孩子沒有別訪問過，則p=p->rchild。　　操作函數(shù)為void h_print(Tree T)　　3.源代碼　　#include<stdio.h>　　#include<iostream>

20、　　#include<string>　　#include<time.h>　　#include <iomanip>　　using namespace std;　　typedef string n

21、ametype;　　typedef unsigned long keytype;　　typedef struct node //結點的結構體　　{　　keytype key;

22、　　nametype name; 　　int grade;　　struct node *lchild,*rchild;　　}bstnode;　　typedef bstnode *bstree;</

23、p>　　//棧的定義//　　typedef struct{ //棧結構　　bstree *base;　　bstree *top;　　int stacksize;

24、　　}Sqstack;　　int InitStack (Sqstack &s) //建立一個空棧　　{　　s.base=(bstree*)malloc(1000 * sizeof(int));

25、;　　s.top=s.base;　　return 1;　　};　　int Push(Sqstack &s ,node *e)//在棧頂插入元素（進棧）

26、;　　{　　*s.top=e;　　s.top=s.top+1;　　return 1;　　};

27、int Pop(Sqstack &s, bstree &e)//出棧　　{　　if(s.top==s.base)return 0;　　else s.top=s.top-1;　　e=*s.top;<

28、;/b>　　return 1;　　};　　//非遞歸歷遍并輸出結點信息//　　/*---------------先序非遞歸遍歷---------------*/<

29、;p>　　void x_print(node *t)　　{　　Sqstack s;　　InitStack(s);　　bstnode *p;　　p=t;

30、;　　while(p||!(s.top==s.base))　　{　　if(p)　　{ 　　Push(s,p);<

31、;/p>　　cout<<p->key<<"\t"<<setw(20);　　cout<<p->name<<"\t"<<setw(20);　　cout<<p->grade<<&q

32、uot;\t"<<endl;　　p=p->lchild;　　}　　else 　　{<

33、;b>　　Pop(s,p);　　p=p->rchild;　　}　　}　　}　　/*-

34、--------------中序非遞歸遍歷---------------*/　　void z_print(node *t)　　{　　Sqstack s;　　InitStack(s);　　bst

35、node *p;　　p=t;　　while(p||!(s.top==s.base))　　{　　if(p)<b&

36、gt;　　{ 　　Push(s,p);　　p=p->lchild;　　}　　else 　　{

37、;　　Pop(s,p);　　cout<<p->key<<"\t"<<setw(20);　　cout<<p->name<<"\t"<<setw(20);&

38、lt;/p>　　cout<<p->grade<<"\t"<<endl;　　p=p->rchild;　　}　　}<

39、p>　　}　　/*---------------非遞歸后序遍歷---------------*/　　void h_print(node *t)　　{　　Sqstack s;

40、;　　InitStack(s);　　node *p,*q;　　p=t;　　q=NULL;　　while(p || !(s.top==s.base))

41、　　{　　if(p){　　Push(s,p);　　p=p->lchild;　　}else&l

42、t;b>　　{　　p=*(s.top-1);　　if(p->rchild==q)　　{　　Pop(s,q);p=NULL;　　cout<<q->

43、;key<<"\t"<<setw(20);　　cout<<q->name<<"\t"<<setw(20);　　cout<<q->grade<<"\t"<<endl;

44、　　}else　　{　　p=p->rchild;q=NULL;　　}　　}

45、　　}　　}　　//遞歸查找二叉樹//　　/*---歸查找，若找到就返回指向該結點的指針，否則返回空---*/　　bstnode *SearchBST(bstree t,ke

46、ytype key) {　　if(t==NULL||key==t->key)　　return t;　　if(key<t->key)　　return SearchBST(t->lchild ,key);<

47、;/p>　　else 　　return SearchBST(t->rchild ,key);　　}　　//-------------------給定學生信息插入到二叉樹中-----------------

48、--//　　bstree InsertBST(bstree t,int key,nametype name,double grade)　　{　　bstree p,q;　　if(t==NULL) //樹初始為

49、空，新建二叉樹　　{　　t=new bstnode();　　t->key=key;　　t->name=name;　　t->grade=grade;&l

50、t;p>　　t->lchild=t->rchild=NULL;　　}　　else　　{　　p=t;&l

51、t;/p>　　while(p) //樹已存在，按照二叉排序樹的特性查找　　{　　q=p;　　if(p->key>key)　　p=q->

52、lchild;　　else if(p->key<key)　　p=q->rchild;　　else　　{　　cout<<end

53、l;　　cout<<"樹中已有該節(jié)點:"<<key<<endl;　　cout<<endl;　　return t;　　}</

54、p>　　}　　p=new bstnode(); //找不到結點就新建一個結點插入到二叉排序樹中　　p->key=key;　　p->name=name;　　p->grade=gr

55、ade;　　p->lchild=p->rchild=NULL;　　if(q->key>key)　　q->lchild=p;　　else　　q->rchild

56、=p;　　}　　return t;　　}　　//-------------------二叉樹排序樹的構建-------------------//</p

57、>　　bstree CreatTree() //不斷輸入學生信息以插入到二叉樹中　　{　　bstree t=NULL;　　keytype key;　　nametype name;</

58、p>　　double grade;　　cout<<"請輸入---學號---姓名---成績---（輸入0時結束）:"<<endl;　　cin>>key;　　if(key==0)

59、;　　return t;　　cin>>name;　　cin>>grade;　　while(key) //key==0時退出　　{<

60、/p>　　t=InsertBST(t,key,name,grade);　　cout<<"請輸入---學號---姓名---成績---（輸入0時結束）:"<<endl;　　cin>>key;　　i

61、f(key==0)　　break;　　cin>>name;　　cin>>grade;　　}　　return t;

62、　　}　　//-------------------刪除樹中的結點-------------------//　　void Delete(bstree &p) //刪除結點的函數(shù)

63、{　　bstree q,s;　　if(!p->rchild)　　{　　q=p;　　p=q->lchild ;</p&

64、gt;　　delete q;　　}　　else if(!p->lchild)　　{　　q=p;

65、;　　p=p->rchild;　　delete q;　　}　　else 　　{</b&

66、gt;　　q=p;　　s=p->lchild;　　while(s->rchild)　　{　　q=s;&l

67、t;/p>　　s=s->rchild;　　}　　p->name=s->name;　　if(q!=p)　　q->rchild=s->lchi

68、ld;　　else　　q->lchild=s->lchild;　　delete s;　　}<b&g

69、t;　　}　　void DeleteData(bstree &t,keytype key)　　{　　if(!t){　　cout<<"沒有該信息，請

70、重新輸入！";　　cin>>key;　　DeleteData(t,key);　　}　　else

71、　　{　　if(t->key==key)　　{　　Delete(t); //若找到結點直接刪除　　cout<<"刪除成功！"<<endl;

72、　　}　　else if(t->key>key)　　DeleteData(t->lchild,key); //結點數(shù)據比查找關鍵字大，繼續(xù)在其左子樹中查找　　else<

73、;/p>　　DeleteData(t->rchild,key); //結點數(shù)據比查找關鍵字小，繼續(xù)在其右子樹中查找　　}　　}　　//數(shù)組和二叉排序樹的查找效率比較//<

74、p>　　void compare()　　{　　bstree t=NULL;　　clock_t start,end,start1,end1;　　int num=0;

75、int a=0;　　int b=0;　　int c=0;　　int d=1;　　bstree p;&

76、lt;/p>　　string key,name;　　double grade;　　nametype str [100][3];　　//cout<<"（輸入0時結束）"<<endl;　　cout<

77、<"請輸入---學號---姓名---成績---（輸入0時結束）:"<<endl;　　cin>>key;　　if(key=="0")　　return ;

78、;　　cin>>name;　　cin>>grade;　　while(key!="0")　　{　　str[num][0]=key;

79、;　　str[num][1]=name;　　str[num][2]=grade;　　int key1=atoi(key.c_str()); //用庫函數(shù)將字符串轉化為關鍵字的int型　　t=InsertBST(t,key1,name,grade); //插入結點

80、cout<<"請輸入---學號---姓名---成績---（輸入0時結束）:"<<endl;　　cin>>key;　　if(key=="0")　　break;<

81、;/p>　　cin>>name;　　cin>>grade;　　num++;　　}　　cout<<endl;&

82、lt;p>　　cout<<"進行數(shù)組和二叉排序樹的查詢效率比較（比較：1 不比較：0）";　　cin>>d;　　while(d!=NULL)　　{

83、;　　switch(d)　　{　　case 0: 　　cout<<"返回選擇界面"<<endl;

84、　　break;　　case 1:　　cout<<"數(shù)組查詢！"<<endl;　　cout<<"請輸入查詢的成績："<<endl;<p&g

85、t;　　cin>>key;　　start=clock();　　while(a<=10000000) //循環(huán)模擬數(shù)組查找　　{　　while(b<=99)

86、　　{　　if(str[b][0]==key)　　{b=100;}　　else　　b++;<

87、/b>　　}　　b=0;　　a++;　　}　　end=clock();&

88、lt;/p>　　if(num>=100)　　cout<<"數(shù)組查詢：無查詢信息，花費時間: "<<end-start<<" 毫秒"<<endl;　　else<p&g

89、t;　　cout<<"數(shù)組查詢：查到信息，花費時間: "<<end-start<<" 毫秒"<<endl;　　int key1=atoi(key.c_str()); //同上轉化　　start1=clock();　　w

90、hile(c<=10000000) //用循環(huán)來模擬樹中查找　　{　　p=SearchBST(t,key1);　　c++;　　}</

91、p>　　end1=clock();　　if(p==NULL)　　cout<<"樹查詢：無查詢信息，花費時間: "<<end1-start1<<" 毫秒"<<endl;　　else

92、　　cout<<"樹查詢：查到信息，花費時間: "<<end1-start1<<" 毫秒"<<endl;　　a=0;　　b=0;

93、　　c=0;　　break;　　}　　cout<<"是否繼續(xù)進行操作（是：1 否：0）：";<p

94、>　　cin>>d;　　}　　}　　//二叉樹的深度　　int TreeDepth(bstree t)

95、　　{　　int left,right,max;　　if(t!=NULL)　　{　　left=TreeDepth(t->lchild);</p

96、>　　right=TreeDepth(t->rchild);　　max=left>right?left:right;　　return max+1;　　}else　　{</

97、b>　　return 0;　　}　　}　　//樹狀輸出二叉樹　　void

98、 PrintTree(bstree t,int layer)　　{　　int k;　　if(t==NULL)　　return ;<

99、;p>　　PrintTree(t->rchild,layer+1);　　for(k=0;k<layer;k++)　　cout<<" ";　　cout<<t->key<<"\n";<

100、;p>　　PrintTree(t->lchild,layer+1);　　}　　//-------------------主函數(shù)測試-------------------//　　int main()　　{&

101、lt;/b>　　int d;　　keytype key;　　bstree t=NULL;　　t=CreatTree();　　d=TreeDepth(t);<

102、p>　　cout<<"二叉排序樹的樹形表示如下"<<endl;　　PrintTree(t,d);　　char choose;　　nametype name;　　bstree p;<

103、;/p>　　double grade;　　cout<<" "<<endl;　　cout<<"-----------------------------請輸入你要選擇的操作-------------------------------"<<e

104、ndl;　　cout<<" |-------------------------------------|"<<endl;　　cout<<" ||----------------------------------

105、-||"<<endl;　　cout<<" || a 插入信息 ||"<<endl;　　cout<<" || b 刪除信息

106、 ||"<<endl;　　cout<<" || c 查詢信息 ||"<<endl;　　cout<<" || d

107、修改信息 ||"<<endl;　　cout<<" || 0 退出 ||"<<endl;　　cout<<"

108、|| e 對二叉排序樹進行非遞歸遍歷 ||"<<endl;　　cout<<" || f 進行數(shù)組和二叉樹查找效率實驗||"<<endl;　　cout<<" ||-------

109、----------------------------||"<<endl;　　cout<<" |-------------------------------------|"<<endl;　　cout<<endl;

110、　　cout<<"需要選擇的操作為：";　　cin>>choose;　　cout<<endl;　　while(choose)　　{<

111、;p>　　switch(choose)　　{　　case 'a':　　//cout<<"輸入學生信息信息（學號為0時結束）."<<endl;<

112、p>　　cout<<"請輸入---學號---姓名---成績---（輸入0時結束）:"<<endl;　　cin>>key;　　if(key==0) /*{　　PrintTree(t,d);&l

113、t;p>　　break;}*/　　cin>>name;　　cin>>grade;　　while(key) 　　{

114、　　t=InsertBST(t,key,name,grade);　　cout<<"請輸入---學號---姓名---成績---:"<<endl;　　cin>>key;　　if(key==0)<

115、p>　　break;　　cin>>name;　　cin>>grade;　　}　　break;<p&

116、gt;　　case 'b':　　cout<<"請輸入要刪除信息學生的成績："<<endl;　　cin>>key;　　DeleteData(t,key);</p&

117、gt;　　d=TreeDepth(t);　　cout<<"刪除結點后二叉樹的樹形顯示如下"<<endl;　　PrintTree(t,d);　　break;<b&g

118、t;　　case 'c':　　cout<<"請輸入要查詢的成績："<<endl;　　cin>>key;　　p=SearchBST(t,key);

119、;　　if(p==NULL)　　cout<<"無查詢的關鍵字："<<key<<endl;　　else　　cout<<"成績"<<"\t"<<se

120、tw(20)<<"姓名"<<"\t"<<setw(20)<<"學號"<<endl;　　cout<<p->key<<"\t"<<setw(20);　　cout<<p

121、->name<<"\t"<<setw(20);　　cout<<p->grade<<endl;　　break;　　case 'd':</p

122、>　　cout<<"請輸入要修改的學號："<<endl;　　cin>>key;　　p=SearchBST(t,key);　　if(p==NULL)

123、cout<<"無你所要修改的關鍵字："<<key<<endl;　　else　　{　　cout<<"請輸入修改的姓名：";<

124、;p>　　cin>>name;　　cout<<"請輸入修改的成績：";　　cin>>grade;　　p->name=name;　　p->grade=grade;<p&g

125、t;　　}　　break;　　case 'e':　　if(!t)　　cout<<"

126、沒有任何信息，請先輸入信息！";　　else　　{　　cout<<"學號"<<"\t"<<setw(20)<<"姓名"&

127、lt;<"\t"<<setw(20)<<"成績"<<endl;　　cout<<"------------------非遞歸先序遍歷----------------"<<endl;　　cout<<endl;</p&

128、gt;　　x_print(t);　　cout<<"------------------非遞歸中序遍歷-----------------"<<endl;　　cout<<endl;　　z_print(t);<p

129、>　　cout<<"------------------非遞歸后序遍歷-----------------"<<endl;　　cout<<endl;　　h_print(t);　　}<p&

130、gt;　　break;　　case 'f':　　cout<<"***此實驗為獨立實驗，實驗數(shù)據獨立于外部數(shù)據***"<<endl;　　cout<<"***請

131、重新輸入相關信息***"<<endl;　　compare();　　break;　　default:　　cout<<"選擇錯誤！";</p

132、>　　break;　　}　　cout<<endl;　　cout<<endl;　　cout<<" "<<

133、;endl;　　cout<<"-----------------------------請輸入你要選擇的操作-------------------------------"<<endl;　　cout<<" |----------------------

134、---------------|"<<endl;　　cout<<" ||-----------------------------------||"<<endl;　　cout<<" ||

135、 a 插入信息 ||"<<endl;　　cout<<" || b 刪除信息 ||"<<endl;　　cout<<"

136、 || c 查詢信息 ||"<<endl;　　cout<<" || d 修改信息 ||"<<endl;　　cout<<"

137、 || 0 退出 ||"<<endl;　　cout<<" || e 對二叉排序樹進行非遞歸遍歷 ||"<<endl;　　cout<<"

138、 || f 進行數(shù)組和二叉樹查找效率實驗||"<<endl;　　cout<<" ||-----------------------------------||"<<endl;　　cout<<&quo

139、t; |-------------------------------------|"<<endl;　　cout<<endl;　　cout<<"選擇的操作位：";　　cin>>choose;<

140、/p>　　cout<<endl;　　}　　return 0;　　}　　4.運行結果及截圖</b

141、>　　從鍵盤讀入數(shù)據　　以0作為結束標志可得二叉排序樹樹狀表示　　主菜單選擇模塊　　需要在樹種添加節(jié)點則執(zhí)行操作a　　需要在書中刪除節(jié)點執(zhí)行操作b&

142、lt;/p>　　需要查詢節(jié)點信息執(zhí)行操作c　　修改某一節(jié)點信息執(zhí)行操作d　　執(zhí)行操作0退出程序執(zhí)行　　執(zhí)行操作e對樹進行先序遍歷、后序遍歷、中序遍歷運行結果如下圖　　需要對樹和數(shù)組的查詢效率比較執(zhí)行操作f

143、;　　4.實驗結論 　　棧是僅表尾進行插入和刪除的線性表，棧的順序存儲結構是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據元素，并同時附設指針top指示棧頂元素在順序棧中的位置。　　從數(shù)組查詢和樹查詢的時間可得出，樹的查詢比數(shù)組的查詢時間快得多。但是二叉樹的平均查找長度和樹的形態(tài)有關，當先后插入的關鍵字是有序樹時，構造的二叉樹蛻變?yōu)閱芜厴?/p>

眾賞文庫> 全部分類> 畢業(yè)設計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據結構課程設計--二叉排序樹的實現(xiàn)

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據結構課程設計--二叉排序樹的實現(xiàn)

文檔簡介

溫馨提示

最新文檔

評論

免費下載