数据结构实验报告

1、数据结构实验报告（五）实验目的：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.设计出在二叉排序树中插入结点的算法，在此基础上实现构建二叉排序树的算法，并给出其中序遍历序列。实验测试数据：构建二叉排序树

2、的输入序列如下：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,

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<<"输出查找的顺序为："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<<"

5、输出查找的顺序为："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,2

6、4,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<<"查无此数！"<

7、;<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.#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在这个排序树中"<<endl;else cout<<"未找到这个数！"<<endl;if(q.Search(70)!=NULL)cout<<"70在这个排序树中"<<endl;else cout<<"未找到这个数！"<<endl;if(q.Search(160)!=

13、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在这个排序树中&