查找算法

实验项目：实现二叉排序、查找树，哈希查找实验目的：1、巩固二叉树的实现方法；2、理解二叉排序树的递归插入和递归查找算法思想并用代码实现3、理解哈希查找算法思想并用代码实现涉及的知识点：二叉树的表示，递归算法，二叉树的遍历，哈希查找算法实验内容：二叉排序、查找树：1、用随机函数生成10个待排序元素；2、利用二叉查找树输出升序序列；3、利用同一棵二叉查找树输出降序序列；4、写出查找的递归函数；注意：递归出口的处理要求：二叉排序树的程序填空：修改“BiSearchTree.h”文件中的myorder()函数，得到二叉排序树的降序序列，要求达到BiSearchTree.exe的执行效果。哈希查找：1、哈希表类的哈希函数采用除留余数法哈希函数；2、解决哈希冲突的函数采用开放定址法中的线性探察法。3、建立一个由10个数据元素组成的集合；4、测试哈希表长度m=13和m=11两种情况下的哈希表，并查找其中的几个元素。要求：哈希查找的程序填空：修改“HashTable.h”文件中的Find()函数；并编写测试程序。（1）//BiSearchTree.h#includeBTreeNode.htemplateclassTclassBiSearchTree{private:BTNodeT*root;voidPreOrder(BTNodeT*&t);voidInOrder(BTNodeT*&t);voidPostOrder(BTNodeT*&t);voidmyOrder(BTNodeT*&t);voidInsert(BTNodeT*&ptr,constT&item);voidDelete(BTNodeT*&ptr,constT&item);public:BiSearchTree(){root=NULL;}~BiSearchTree(){};voidPreOrder(){PreOrder(root);}voidInOrder(){InOrder(root);}voidPostOrder(){PostOrder(root);}voidmyOrder(){myOrder(root);}BTNodeT*&GetRoot(){returnroot;}BTNodeT*&LeftChild(BTNodeT*¤t){returnroot!=NULL?current-Left():NULL;}BTNodeT*&RightChild(BTNodeT*¤t){returnroot!=NULL?current-Right():NULL;}BTNodeT*&Find(constT&item);voidInsert(constT&item){Insert(GetRoot(),item);}voidDelete(constT&item){Delete(GetRoot(),item);}friendistream&operator(istream&in,BiSearchTreeT*&tree);};templateclassTvoidBiSearchTreeT::PreOrder(BTNodeT*&t){if(t!=NULL){Visit(t);PreOrder(t-lc);PreOrder(t-rc);}}templateclassTvoidBiSearchTreeT::InOrder(BTNodeT*&t){if(t!=NULL){InOrder(t-lc);Visit(t);InOrder(t-rc);}}templateclassTvoidBiSearchTreeT::PostOrder(BTNodeT*&t){if(t!=NULL){PostOrder(t-lc);PostOrder(t-rc);Visit(t);}}templateclassTvoidBiSearchTreeT::myOrder(BTNodeT*&t){//输入您自己编写的语句if(t!=NULL){myOrder(t-rc);Visit(t);myOrder(t-lc);}}//查找的非递归算法templateclassTBTNodeT*&BiSearchTreeT::Find(constT&item){if(root!=NULL){BTNodeT*temp=root;while(temp!=NULL){if(temp-element==item)returntemp;if(temp-elementitem)temp=temp-Right();elsetemp=temp-Left();}}returnNULL;}templateclassTvoidBiSearchTreeT::Insert(BTNodeT*&ptr,constT&item){if(ptr==NULL){ptr=newBTNodeT(item);if(ptr==NULL){cerr空间不足！endl;exit(1);}}elseif(itemptr-element)Insert(ptr-Left(),item);elseif(itemptr-element)Insert(ptr-Right(),item);//否则就是item已在二叉排序树中，不做任何事}templateclassTvoidBiSearchTreeT::Delete(BTNodeT*&ptr,constT&item){BTNodeT*temp;if(ptr!=NULL){if(itemptr-element)Delete(ptr-Left(),item);elseif(itemptr-element)Delete(ptr-Right(),item);elseif(ptr-Left()!=NULL&&ptr-Right()!=NULL){BTNodeT*min;min=ptr-Right();while(min-Left()!=NULL)min=min-Left();ptr-element=min-element;Delete(ptr-Right(),min-element);}else{temp=ptr;if(ptr-Left()==NULL)ptr=ptr-Right();elseif(ptr-Right()==NULL)ptr=ptr-Left();deletetemp;}}}//查找的递归算法templateclassTintmyFind(BTNodeT*&ptr,constT&item){if(ptr!=NULL){if(ptr-element==item)return1;if(ptr-elementitem)returnmyFind(ptr-Right(),item);elsereturnmyFind(ptr-Left(),item);}elsereturn0;}//BTreeNode.h#includeiostream.h#includestdlib.htemplateclassTclassBiSearchTree;templateclassTclassBTNode{friendclassBiSearchTreeT;friendintmyFind(BTNodeT*&ptr,constT&item);friendvoidVisit(BTNodeT*p);friendBTNodeT*Find(BTNodeT*&root,Titem);friendBTNodeT*copytree(BTNodeT*oldroot);private:Telement;BTNodeT*lc,*rc;public:BTNode(){lc=rc=NULL;}BTNode(constTe){element=e;lc=rc=NULL;}BTNode(constTe,BTNodeT*l,BTNodeT*r){element=e;lc=l;rc=r;}BTNode(constBTNodeT&a)//拷贝构造函数{element=a-element;lc=a-lc;rc=a-rc;}BTNodeT*&Left(void){returnlc;}BTNodeT*&Right(void){returnrc;}};templateclassTvoidVisit(BTNodeT*p){coutp-element;}//BiSearchTree.cpp:Definestheentrypointfortheconsoleapplication.#includeBiSearchTree.h#includestdlib.h#includetime.htypedefintDatatype;#defineMax10voidmain(void){BiSearchTreeintsearchTree;time_tt;srand((unsigned)time(&t));for(inti=0;i10;i++)searchTree.Insert(rand()%100);cout升序序列为:endl;searchTree.InOrder();coutendl;cout降序序列为:endl;searchTree.myOrder();coutendl;}（2）//HashTable.henumKindOfItem{Empty,Active,Deleted};structHashItem{DataTypedata;KindOfIteminfo;HashItem(KindOfItemi=Empty):info(i){}HashItem(constDataType&D,KindOfItemi=Empty):data(D),info(i){}intoperator==(HashItem&a){returndata==a.data;}intoperator!=(HashItem&a){returndata!=a.data;}};classHashTable{private:HashItem*ht;//哈希表数组intTableSize;//哈希表的长度（即m）intcurrentSize;//当前的表项个数public:HashTable(intm);//构造函数~HashTable(void)//析构函数{delete[]ht;}intFind(constDataType&x)const;//查找intInsert(constDataType&x);//插入intDelete(constDataType&x);//删除intIsIn(constDataType&x)//是否已存在{inti=Find(x);returni=0?1:0;}DataTypeGetValue(inti)const//取数据元素{returnht[i].data;}};//哈希表类实现HashTable::HashTable(intm)//构造函数{TableSize=m;//置哈希表长度ht=newHashItem[TableSize];//申请动态数组空间currentSize=0;//置初始的当前表项个数}intHashTable::Find(constDataType&x)const//查找{//输入你自己编写的程序inti=x.key%TableSize;//哈希函数intj=i;while(ht[j].info==Active&&ht[j].data!=x)//说明存在冲突{j=(j+1)%TableSize;//用哈希冲突方法继续查找if(j==i)//说明已遍历整个哈希表未找到且表已满return-TableSize;}if(ht[j].