《数据结构实验报告5.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告5.docx（6页珍藏版）》请在三一文库上搜索。
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.#includeusing namespace std;int key_lib=1,2,3,4,6,7,8,9,10,11,12,13,17,18,19,20,24,25,2
3、6,30,35,40,45,50,100;int halfsearch(int *lib,int low,int high,int key)static int mid;if(lowhigh)return -1;elsemid=(low+high)/2;coutmid ;if(keylibmid)return halfsearch(lib,mid+1,high,key);else return mid;void main()cout输出查找的顺序为：;if(halfsearch(key_lib,0,24,2)=-1)cout查无此数！endl;elsecoutendl;cout输出查找的顺序为
4、：;if(halfsearch(key_lib,0,24,8)=-1)cout查无此数！endl;elsecoutendl;cout输出查找的顺序为：;if(halfsearch(key_lib,0,24,20)=-1)cout查无此数！endl;elsecoutendl;cout输出查找的顺序为：;if(halfsearch(key_lib,0,24,30)=-1)cout查无此数！endl;elsecoutendl;cout输出查找的顺序为：;if(halfsearch(key_lib,0,24,50)=-1)cout查无此数！endl;elsecoutendl;cout输出查找的顺序为：
5、;if(halfsearch(key_lib,0,24,5)=-1)cout查无此数！endl;elsecoutendl;cout输出查找的顺序为：;if(halfsearch(key_lib,0,24,15)=-1)cout查无此数！endl;elsecoutendl;cout输出查找的顺序为：;if(halfsearch(key_lib,0,24,33)=-1)cout查无此数！endl;elsecoutendl;cout输出查找的顺序为：;if(halfsearch(key_lib,0,24,110)=-1)cout查无此数！endl;elsecoutendl;2.3.#includeu
6、sing 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_tre
7、e(node *t);node *Search(node *snode,int k);searchtree:searchtree(int *r,int n)node *s;root=NULL;for(int i=0;idata=ri;s-lchild=s-rchild=NULL;Insert(root,s);void searchtree:Insert(node *&innode,node *s)if(innode=NULL) innode=s;else if(s-datadata) Insert(innode-lchild,s);else Insert(innode-rchild,s);no
8、de * searchtree:Search(node *snode,int k)if(snode=NULL)return NULL;if(snode-data=k) return snode;else if(snode-datak) return Search(snode-lchild,k);else return Search(snode-rchild,k);void searchtree:travel(node *p)if(p=NULL) return;travel(p-lchild);coutdatarchild);void searchtree:delete_tree(node *t
9、)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)cout150在这个排序树中endl;else cout未找到这个数！endl;if(q.Search(70)!=NULL)cout70在这个排序树中endl;else cout未找到这个数！endl;
10、if(q.Search(160)!=NULL)cout160在这个排序树中endl;else cout未找到这个数！endl;if(q.Search(190)!=NULL)cout190在这个排序树中endl;else cout未找到这个数！endl;if(q.Search(10)!=NULL)cout10在这个排序树中endl;else cout未找到这个数！endl;if(q.Search(55)!=NULL)cout55在这个排序树中endl;else cout未找到这个数！endl;if(q.Search(175)!=NULL)cout175在这个排序树中endl;else cout未找到这个数！endl;运行结果：1.2. （注：可编辑下载，若有不当之处，请指正，谢谢!）