资源描述：
《二分法和二叉排序树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验五：用二分法以及二叉排序树进行查找班级：10级数学班学号：201008101127姓名：裴志威一、实验目的二分查找法的实现，二叉排序树的创建及其基本操作，对n个随机整数构造二叉排序树并实现查找、删除算法并求树的实际高度。这里n=100，整数值范围1~1000，可以重复二、实验环境：VisualC++。三、实验要求：（1）实现二分法、二叉排序树的查找和输出（2）对二叉排序树进行插入、删除、创建等基本操作四、实验步骤（1）数据结构的定义与实现用二分法进行查找的结点定义如下：typedefstru
2、ct{KeyTypekey;//存放关键字，KeyType为关键字类型ElemTypedata;//其他数据，ElemType为其他数据的类型}LineList;用二叉排序树进行查找的结点定义如下：typedefstructtnode{KeyTypekey;//存放结点关键字ElemTypedata;//存放结点数据structtnode*lchild,*rchild;//存放左右孩子结点指针}BSTNode;//二叉排序树的结点类型（2）基本操作定义及实现intBinSearch(LineLi
3、stR[],intn,KeyTypek)//二分查找法来实现查找BSTNode*BSTSearch(BSTNode*bt,KeyTypek)//二叉排序树的结点查找intBSTInsert(BSTNode*&bt,KeyTypek)//在二叉排序树中插入结点voidCreateBST(BSTNode*&bt,KeyTypestr[],intn)//创建二叉排序树，调用二叉排序树的结点插入voidDispBST(BSTNode*bt)//采用括号表示法输出二叉排序树intBSTDelete(BST
4、Node*&bt,KeyTypek)//删除二叉排序树的结点(3)主程序流程LineListR[10]={{2,0},{4,0},{7,0},{9,0},{10,0},{14,0},{18,0},{26,0},{32,0},{40,0}}//定义一个二分法查找的顺序排列数组k=BinSearch(R,10,9);//进行二分查找，若k=-1则查找失败，k=0则查找成功BSTNode*BT,*m;intstr[10]={5,2,6,1,4,7,3,8,11,16},j;//定义二叉排序树的指针以及
5、排序关键字CreateBST(BT,str,10);//二叉排序的创建DispBST(BT);//用括号表示法输出二叉排序树m=BSTSearch(BT,7);//在二叉排序树中查找结点7，若成功则返回其指针m=BSTSearch(BT,0);//在二叉排序树中查找结点0，若失败则返回NULLj=BSTInsert(BT,0);//在二叉排序树中插入0这个结点，若成功则返回1，若失败则返回0j=BSTDelete(BT,0);//删除刚插入的结点0，若成功则返回1，若失败则返回0j=BSTDel
6、ete(BT,2);//接着删除结点2，若成功则返回1，若失败则返回0(4)数据测试及结果分析在C++里运行程序，并看二分查找法是否查找正确。注意对照二叉排序树的输出和逻辑图是否一致，并看其查找以及基本操作是否正确。由程序运行可知,程序是正确的.结果图如下图：
