數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告（五）實(shí)驗(yàn)?zāi)康模?. 掌握順序表的查找方法，尤其是二分查找方法。2. 掌握二叉排序樹(shù)的建立及查找。實(shí)驗(yàn)任務(wù)：1. 對(duì)下列數(shù)據(jù)表，分別采用二分查找算法實(shí)現(xiàn)查找，給出查找過(guò)程依次所比較的元素（的下標(biāo)），并以二分查找的判定樹(shù)來(lái)解釋。實(shí)驗(yàn)測(cè)試數(shù)據(jù)：數(shù)據(jù)表為 (1,2,3,4,6,7,8,9,10,11,12,13,17,18,19,20,24,25,26,30,35,40,45,50,100)查找的元素分別為： 2，8，20, 30，50，5，15，33，1102.設(shè)計(jì)出在二叉排序樹(shù)中插入結(jié)點(diǎn)的算法，在此基礎(chǔ)上實(shí)現(xiàn)構(gòu)建二叉排序樹(shù)的算法，并給出其中序遍歷序列。實(shí)驗(yàn)測(cè)試數(shù)據(jù)：構(gòu)建二叉排序樹(shù)

2、的輸入序列如下：100，150，120，50，70，60，80，170，180，160，110，30，40，35，1753. 設(shè)計(jì)算法在二叉排序樹(shù)中查找指定值的結(jié)點(diǎn)。 在任務(wù)2所建立的二叉排序樹(shù)中分別查找下列元素： 150，70，160，190，10，55，175 4. 設(shè)計(jì)算法在二叉排序樹(shù)中刪除特定值的結(jié)點(diǎn)。（選做） 在任務(wù)2所建立的二叉排序樹(shù)中依次刪除下列元素： 30，150，100，并給出中序遍歷結(jié)果。程序清單：1.#include<iostream>using namespace std;int key_lib=1,2,3,4,6,7,8,9,10,11,12,13,17,

3、18,19,20,24,25,26,30,35,40,45,50,100;int halfsearch(int *lib,int low,int high,int key)static int mid;if(low>high)return -1;elsemid=(low+high)/2;cout<<mid<<" "if(key<libmid)return halfsearch(lib,low,mid-1,key);else if(key>libmid)return halfsearch(lib,mid+1,high,key);els

4、e return mid;void main()cout<<"輸出查找的順序?yàn)椋?quot;if(halfsearch(key_lib,0,24,2)=-1)cout<<"查無(wú)此數(shù)！"<<endl;elsecout<<endl;cout<<"輸出查找的順序?yàn)椋?quot;if(halfsearch(key_lib,0,24,8)=-1)cout<<"查無(wú)此數(shù)！"<<endl;elsecout<<endl;cout<<"

5、輸出查找的順序?yàn)椋?quot;if(halfsearch(key_lib,0,24,20)=-1)cout<<"查無(wú)此數(shù)！"<<endl;elsecout<<endl;cout<<"輸出查找的順序?yàn)椋?quot;if(halfsearch(key_lib,0,24,30)=-1)cout<<"查無(wú)此數(shù)！"<<endl;elsecout<<endl;cout<<"輸出查找的順序?yàn)椋?quot;if(halfsearch(key_lib,0,2

6、4,50)=-1)cout<<"查無(wú)此數(shù)！"<<endl;elsecout<<endl;cout<<"輸出查找的順序?yàn)椋?quot;if(halfsearch(key_lib,0,24,5)=-1)cout<<"查無(wú)此數(shù)！"<<endl;elsecout<<endl;cout<<"輸出查找的順序?yàn)椋?quot;if(halfsearch(key_lib,0,24,15)=-1)cout<<"查無(wú)此數(shù)！"<

7、;<endl;elsecout<<endl;cout<<"輸出查找的順序?yàn)椋?quot;if(halfsearch(key_lib,0,24,33)=-1)cout<<"查無(wú)此數(shù)！"<<endl;elsecout<<endl;cout<<"輸出查找的順序?yàn)椋?quot;if(halfsearch(key_lib,0,24,110)=-1)cout<<"查無(wú)此數(shù)！"<<endl;elsecout<<endl;2.3.#inc

8、lude<iostream>using namespace std;struct nodenode *lchild;node *rchild;int data;class searchtreepublic:searchtree(int *r,int n);searchtree()delete_tree(root);void Insert(node *&innode,node *s);node *Search(int k)return Search(root,k);void travel()travel(root);private:node *root;void travel

9、(node *p);void delete_tree(node *t);node *Search(node *snode,int k);searchtree:searchtree(int *r,int n)node *s;root=NULL;for(int i=0;i<n;i+)s=new node;s->data=ri;s->lchild=s->rchild=NULL;Insert(root,s);void searchtree:Insert(node *&innode,node *s)if(innode=NULL) innode=s;else if(s-&g

10、t;data<innode->data) Insert(innode->lchild,s);else Insert(innode->rchild,s);node * searchtree:Search(node *snode,int k)if(snode=NULL)return NULL;if(snode->data=k) return snode;else if(snode->data>k) return Search(snode->lchild,k);else return Search(snode->rchild,k);void se

11、archtree:travel(node *p)if(p=NULL) return;travel(p->lchild);cout<<p->data<<" "travel(p->rchild);void searchtree:delete_tree(node *t)if(t=NULL) return;delete_tree(t->lchild);delete_tree(t->rchild);delete t;void main()int lib=100,150,120,50,70,60,80,170,180,160,110

12、,30,40,35,175;searchtree q(lib,15);();if(q.Search(150)!=NULL)cout<<"150在這個(gè)排序樹(shù)中"<<endl;else cout<<"未找到這個(gè)數(shù)！"<<endl;if(q.Search(70)!=NULL)cout<<"70在這個(gè)排序樹(shù)中"<<endl;else cout<<"未找到這個(gè)數(shù)！"<<endl;if(q.Search(160)!=

13、NULL)cout<<"160在這個(gè)排序樹(shù)中"<<endl;else cout<<"未找到這個(gè)數(shù)！"<<endl;if(q.Search(190)!=NULL)cout<<"190在這個(gè)排序樹(shù)中"<<endl;else cout<<"未找到這個(gè)數(shù)！"<<endl;if(q.Search(10)!=NULL)cout<<"10在這個(gè)排序樹(shù)中"<<endl;else cout<<"未找到這個(gè)數(shù)！"<<endl;if(q.Search(55)!=NULL)cout<<"55在這個(gè)排序樹(shù)中&