實驗十 查找技術(shù)驗證實驗報告

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