数据结构实验报告5.docx

《数据结构实验报告5.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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，1754.设计算法在二叉排序树中删除特定值的结点。（选做）在任务2所建立的二叉排序树中依次删除下列元素：30，150，100，并给出中序遍历结果。程序清单：1.#includeusingnamespacestd;intkey_lib[]={1,2,3,4,6,7,8,9,10,11,12,13,17,18,19,20,24,25,

3、26,30,35,40,45,50,100};inthalfsearch(int*lib,intlow,inthigh,intkey){staticintmid;if(low>high)return-1;else{mid=(low+high)/2;cout<lib[mid])returnhalfsearch(lib,mid+1,high,key);elsereturnmid;}}voidmain(){cout<<"输出查找的顺序为：";if(hal

4、fsearch(key_lib,0,24,2)==-1)cout<<"查无此数！"<

5、查无此数！"<

6、输出查找的顺序为：";if(halfsearch(key_lib,0,24,33)==-1)cout<<"查无此数！"<usingnamespacestd;structnode{node*lchild;node*rchild;intdata;};classsearchtree{public:searchtree(int*r,in

7、tn);~searchtree(){delete_tree(root);}voidInsert(node*&innode,node*s);node*Search(intk){returnSearch(root,k);}voidtravel(){travel(root);}private:node*root;voidtravel(node*p);voiddelete_tree(node*t);node*Search(nod