實(shí)驗(yàn)十 查找技術(shù)驗(yàn)證實(shí)驗(yàn)報(bào)告

棧特殊線性表班級(jí)：計(jì)算機(jī)11-1學(xué)號(hào)：姓名：成績(jī)：_________實(shí)驗(yàn)十查找技術(shù)驗(yàn)證實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康?1)掌握折半查找算法的基本思想;(2)掌握折半查找算法的實(shí)現(xiàn)方法;(3)掌握折半查找算法的時(shí)間性能;(4)掌握二叉排序樹(shù)定義和特性;(5)掌握二叉排序樹(shù)的建立方法;(6)實(shí)現(xiàn)基于二叉排序樹(shù)的查找技術(shù);(7)掌握二叉排序樹(shù)的查找性能.實(shí)驗(yàn)內(nèi)容(1)對(duì)給定的有序數(shù)組（假設(shè)長(zhǎng)度為n），查找數(shù)組中與給定值k相等的元素。(2)①對(duì)給定的一組無(wú)序序列，建立一棵二叉排序樹(shù)；②對(duì)建立的二叉排序樹(shù)實(shí)現(xiàn)查找操作。設(shè)計(jì)與編碼折半查找驗(yàn)證#include<iostream>usingnamespacestd;intBinSearch1(intr[],intn,intk){intlow=1; inthigh=n; intcount=0; while(low<=high) { intmid=(low+high)/2; count++; if(k<r[mid-1]) high=mid-1; else if(k>r[mid-1])low=mid+1; else { cout<<"比較次數(shù)是："<<count; return0; } } return0;}intmain(){ intn,b,a[100];cout<<"*********************"<<endl; cout<<"請(qǐng)輸入數(shù)組的個(gè)數(shù)："; cin>>n; cout<<"請(qǐng)輸入各個(gè)數(shù)的值:"; for(inti=0;i<n;i++) cin>>a[i]; cout<<"請(qǐng)輸入你要查找的值："; cin>>b; BinSearch1(a,n,b); cout<<endl;cout<<"*********************"<<endl; return0;}㈡二叉排序樹(shù)的建立#include<iostream>usingnamespacestd;structBiNode{intdata;BiNode*lchild,*rchild;};classBiSortTree{public: voiddesplayTree(void);//顯示這個(gè)樹(shù)BiSortTree(inta[],intn);//建立查找集合a[n]的二叉排序樹(shù)~BiSortTree(){};//析構(gòu)函數(shù)，釋放二叉排序樹(shù)中所有結(jié)點(diǎn)，同二叉鏈表的析構(gòu)函數(shù)voidInsertBST(BiNode*&root,BiNode*s);//在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)sBiNode*searchTree(intk);//在樹(shù)中查找一個(gè)值private: BiNode*root;//二叉排序樹(shù)（即二叉鏈表）的根指針voidShowTree(BiNode*&root);//顯示BiNode*SearchBST(BiNode*&root,intk);//查找值為k的結(jié)點(diǎn)};//二叉排序樹(shù)插入算法voidBiSortTree::InsertBST(BiNode*&root,BiNode*s){ if(root==NULL) root=s; elseif(s->data<root->data) InsertBST(root->lchild,s); elseInsertBST(root->rchild,s);}//構(gòu)造二叉排序樹(shù)BiSortTree::BiSortTree(intr[],intn){root=NULL; for(inti=0;i<n;i++) { BiNode*s=newBiNode; s->data=r[i]; s->lchild=NULL; s->rchild=NULL; InsertBST(root,s); }}//二叉排序樹(shù)查找算法BiNode*BiSortTree::searchTree(intk){ returnSearchBST(root,k);}BiNode*BiSortTree::SearchBST(BiNode*&root,intk){if(root==NULL)returnNULL;elseif(root->data==k){returnroot;}elseif(k<root->data){returnSearchBST(root->lchild,k);}else{ returnSearchBST(root->rchild,k);}}//顯示二叉排序樹(shù)voidBiSortTree::desplayTree(void){ ShowTree(root); cout<<endl;}voidBiSortTree::ShowTree(BiNode*&root){ if(root!=NULL){ ShowTree(root->lchild);cout<<root->data<<"\t";ShowTree(root->rchild);} else return;}voidmenu(){ cout<<"查找技術(shù)驗(yàn)證實(shí)驗(yàn)"<<endl;cout<<"*********************"<<endl; cout<<"1.中序遍歷："<<endl; cout<<"2.查找元素："<<endl;cout<<"3.退出："<<endl;cout<<"*********************"<<endl;}intmain(){ intn,b,k;inta[100]; cout<<"**********************************"<<endl;cout<<"請(qǐng)輸入二叉排序樹(shù)的元素的個(gè)數(shù)：";cin>>n;cout<<"請(qǐng)輸入二叉排序樹(shù)的各個(gè)元素的值：";for(inti=0;i<n;i++) { cin>>b;a[i]=b; } BiSortTreec(a,n); menu(); intflag=1; while(flag) { inti; cout<<"請(qǐng)輸入你所需要的選項(xiàng)："; cin>>i; switch(i) { case1: { cout<<"中序遍歷為："<<endl; c.desplayTree(); break; } case2: { cout<<"請(qǐng)輸入二叉順序樹(shù)要查找的元素："; cin>>k; if(c.searchTree(k)==NULL) { cout<<"你所要查找的元素?zé)o法在樹(shù)中找到..."<<endl; } else { cout<<"你所要查找的元素已在查找到了..."<<endl; } break; } case3: { flag=0;