数据结构实验报告5
数据结构实验报告(五)实验目的:1. 掌握顺序表的查找方法,尤其是二分查找方法。2. 掌握二叉排序树的建立及查找。实验任务:1. 对下列数据表,分别采用二分查找算法实现查找,给出查找过程依次所比较的元素(的下标),并以二分查找的判定树来解释。实验测试数据:数据表为 (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.设计出在二叉排序树中插入结点的算法,在此基础上实现构建二叉排序树的算法,并给出其中序遍历序列。实验测试数据:构建二叉排序树的输入序列如下:100,150,120,50,70,60,80,170,180,160,110,30,40,35,1753. 设计算法在二叉排序树中查找指定值的结点。 在任务2所建立的二叉排序树中分别查找下列元素: 150,70,160,190,10,55,175 4. 设计算法在二叉排序树中删除特定值的结点。(选做) 在任务2所建立的二叉排序树中依次删除下列元素: 30,150,100,并给出中序遍历结果。程序清单:1.#include<iostream>using namespace std;int key_lib=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;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);else return mid;void main()cout<<"输出查找的顺序为:"if(halfsearch(key_lib,0,24,2)=-1)cout<<"查无此数!"<<endl;elsecout<<endl;cout<<"输出查找的顺序为:"if(halfsearch(key_lib,0,24,8)=-1)cout<<"查无此数!"<<endl;elsecout<<endl;cout<<"输出查找的顺序为:"if(halfsearch(key_lib,0,24,20)=-1)cout<<"查无此数!"<<endl;elsecout<<endl;cout<<"输出查找的顺序为:"if(halfsearch(key_lib,0,24,30)=-1)cout<<"查无此数!"<<endl;elsecout<<endl;cout<<"输出查找的顺序为:"if(halfsearch(key_lib,0,24,50)=-1)cout<<"查无此数!"<<endl;elsecout<<endl;cout<<"输出查找的顺序为:"if(halfsearch(key_lib,0,24,5)=-1)cout<<"查无此数!"<<endl;elsecout<<endl;cout<<"输出查找的顺序为:"if(halfsearch(key_lib,0,24,15)=-1)cout<<"查无此数!"<<endl;elsecout<<endl;cout<<"输出查找的顺序为:"if(halfsearch(key_lib,0,24,33)=-1)cout<<"查无此数!"<<endl;elsecout<<endl;cout<<"输出查找的顺序为:"if(halfsearch(key_lib,0,24,110)=-1)cout<<"查无此数!"<<endl;elsecout<<endl;2.3.#include<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(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->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 searchtree: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,30,40,35,175;searchtree q(lib,15);q.travel();if(q.Search(150)!=NULL)cout<<"150在这个排序树中"<<endl;else cout<<"未找到这个数!"<<endl;if(q.Search(70)!=NULL)cout<<"70在这个排序树中"<<endl;else cout<<"未找到这个数!"<<endl;if(q.Search(160)!=NULL)cout<<"160在这个排序树中"<<endl;else cout<<"未找到这个数!"<<endl;if(q.Search(190)!=NULL)cout<<"190在这个排序树中"<<endl;else cout<<"未找到这个数!"<<endl;if(q.Search(10)!=NULL)cout<<"10在这个排序树中"<<endl;else cout<<"未找到这个数!"<<endl;if(q.Search(55)!=NULL)cout<<"55在这个排序树中"<<endl;else cout<<"未找到这个数!"<<endl;if(q.Search(175)!=NULL)cout<<"175在这个排序树中"<<endl;else cout<<"未找到这个数!"<<endl;运行结果:1.2.