搜索(二叉搜索树&有序表)

重庆交通大学综合性设计性实验报告班级：软件开发专业2010级一班实验项目名称：搜索实验项目性质：设计性实验实验所属课程：数据结构实验室(中心)：6教指导教师：鲁云平实验完成时间：2012年5月28日一、实验目的应用线性结构、树形结构实现查找。二、实验内容及要求1）有序表的二分查找2）二叉排序树的查找实验要求1，建立有序表，然后进行二分查找2，建立二叉排序树，然后查找三、实验设备及软件Visualstudio2010四、设计方案㈠题目（老师给定或学生自定）二叉搜索树和有序表的搜索㈡设计的主要思路用折半的理论进行搜索功能㈢主要功能1.建立二叉搜索树2.进行搜索树的搜索教师评阅意见：签名：年月日实验成绩：3.建立有序表4.进行有序表的二分查找五、主要代码二叉搜索树头文件：tree.h#includeiostream#includestdlib.husingnamespacestd;templateclassTstructBinTreeNode{Tdata;//数据域BinTreeNodeT*leftChild,*rightChild;//左右子女BinTreeNode():leftChild(NULL),rightChild(NULL){}//初始化左右子女BinTreeNode(Tx,BinTreeNodeT*l=NULL,BinTreeNodeT*r=NULL):data(x),leftChild(l),rightChild(r){}};templateclassTclassBinaryTree{public:BinTreeNodeT*root;//二叉树的根指针BinTreeNodeT*current;BinaryTree():root(NULL){}//构造函数BinaryTree(Tvalue):RefValue(value),root(NULL){}//构造函数voidCreateBinTree();//二叉搜索树的建立boolInsert(intx,BinTreeNodeT*&subTree);//二叉搜索树的插入算法voidTraverse(BinTreeNodeT*subTree);//前序遍历输出voidsTree(intx,BinTreeNodeT*&subTree);//二叉搜索树的递归算法};templateclassTvoidBinaryTreeT::CreateBinTree(){inty=0;root=NULL;cout输入一个元素序列，建立一颗二叉搜索树：endl;while(1){ciny;if(cin.fail()){cin.clear();cout输入出错!!!!!endl;break;}Insert(y,root);cout输入#号结束endl;charc;cinc;if(c=='#')break;else{cout请继续输入:endl;continue;}}}templateclassTboolBinaryTreeT::Insert(intx,BinTreeNodeT*&subTree){if(subTree==NULL){subTree=newBinTreeNodeT(x);if(subTree==NULL){cerr空间分配错误!endl;exit(1);}returntrue;}elseif(xsubTree-data)Insert(x,subTree-leftChild);elseif(xsubTree-data)Insert(x,subTree-rightChild);elseif(x=subTree-data)cout此结点已在树中，请勿重复！endl;}templateclassTvoidBinaryTreeT::Traverse(BinTreeNodeT*subTree){if(subTree==NULL)cout#;if(subTree!=NULL){coutsubTree-data;Traverse(subTree-leftChild);Traverse(subTree-rightChild);}}templateclassTvoidBinaryTreeT::sTree(intx,BinTreeNodeT*&subTree){if(subTree==NULL)return;if(subTree-data==x){cout此数字位于根结点endl;if(subTree-leftChild!=NULL)cout此数字的左子女结点为：subTree-leftChild-dataendl;elsecout此数字没有左子女结点endl;if(subTree-rightChild!=NULL)cout此数字的右子女结点为：subTree-rightChild-dataendl;elsecout此数字没有右子女结点endl;}if(xsubTree-data&&subTree-leftChild!=NULL){if(subTree-leftChild-data==x){if(subTree!=NULL)cout此数字的父结点为：subTree-dataendl;if(subTree-leftChild-leftChild!=NULL)cout此数字的左子女结点为：subTree-leftChild-leftChild-data;elsecout此数字没有左子女结点！;if(subTree-leftChild-rightChild!=NULL)cout此数字的右子女结点为：subTree-leftChild-rightChild-data'\n'endl;elsecout此数字没有右子女结点！'\n'endl;return;}}if(xsubTree-data&&subTree-rightChild!=NULL){if(subTree-rightChild-data==x){if(subTree!=NULL)cout此数字的父结点为：subTree-dataendl;if(subTree-rightChild-leftChild!=NULL)cout此数字的左子女结点为：subTree-rightChild-leftChild-data;elsecout此数字没有左子女结点！;if(subTree-rightChild-rightChild!=NULL)cout此数字的右子女结点为：subTree-rightChild-rightChild-data'\n'endl;elsecout此数字没有右子女结点！'\n'endl;return;}}if(subTree!=NULL){if(xsubTree-data)sTree(x,subTree-leftChild);if(xsubTree-data)sTree(x,subTree-rightChild);}}有序表头文件：seqlist.h#includeiostream#includestdio.h#includestdlib.husingnamespacestd;constintdefaultSize=100;templateclassTclassseqlist{public:T*data;intnumber;intmaxSize;intlast;seqlist(intsz=defaultSize);~seqlist(){delete[]data;}voidinput();voidoutput();};templateclassTseqlistT::seqlist(intsz){if(sz0){maxSize=sz;last=0;data=newT[maxSize];if(data==NULL){cerr存储分配错误！endl;exit(1);}}}templateclassTvoidseqlistT::input(){intj,temp;j=0;number=0;cout开始建立有序顺序表，请输入数字个数：endl;while(1){cinlast;if(cin.fail()){cin.clear();cout输入出错!!!!!endl;break;}if(last=maxSize-1)break;cout存储空间分配有误，范围不能超过maxSize-1endl;}for(inti=0;i=last-1;i++){cout请输入第i+1个元素endl;cinnumber;if(cin.fail()){cin.clear();cout输入出错!!!!!endl;break;}for(intn=0;ni;n++){if(data[n]==number){cout输入数字重复，请重新输入：endl;cinnumber;break;}}data[i]=number;j=i;for(j;j=0;j--){temp=0;if(j-10)break;if(data[j]data[j-1]){temp=data[j-1];data[j-1]=data[j];data[j]=temp;}}j=i;}}templateclassTvoidseqlistT::output(){for(ints=0;s=last-1;s++){number=0;number=data[s];couts+1.numberendl;}coutendl;}六、测试结果及说明测试成功，可运行。截图如下：七、实验体会通过这次实验，我更加熟悉了原本C++的操作和编译，对于各种函数的运用更加熟练，对于二叉搜索树和有序表的数据处理方式也有了更深一步的了解。但是也有不足的地方，错误处理运用的不太好，经常会出现各种崩溃。对于各种文件流和类模板的运用更加熟练了，下次实验会更快更好的运用。这次犯下的错误在下次实验的时候会更好的解决，加深对搜索的理解。