数据结构实验报告六-BST(二叉查找树)实现动态查找表

1、BST（二叉査找树）实现动态査找表问题描述：利用二叉查找树（BST）实现一个动态查找表。一、需求分析：1、本程序是利用二叉査找树（BST）來实现；二叉树使用链式结构（二叉链表）实现；本程序要实现BST的构建，查找两个功能。2、输入输出格式：输入格式：在字符界面上输入一个数字表示节点（数据）的个数。请输入数据个数：输入一个数字/回车结束请输入查找数据：/输入要查找的总的数据，回车表示结束输出格式：每当输入一个暑假，就输出查找成功或不成功，并且后面有数字表示查找的次数，例如：34查找34,输出：査找成功1表示查找时比较的次数。3、测试用例输入：8/BST的节点个数请输入数据：34,76,45,1&

2、26,54,92,65/8个数据请输入查找数：45/查找45输出：查找成功3返回成功和查找时比较的次数请输入查找数:34/查找34输出：查找成功1返回成功和查找时比较的次数请输入查找数:100/查找100输出：查找不成功3/返回成功和查找时比较的次数注：当输入字符型数据时，程序会终止。二、概要设计:抽象数据类型BST,二叉査找树，先定义一个二叉树节点，然后实现二叉査找树的功能。算法的基本思想根据题目要求，要利用二义查找树（BST）來实现，所以先使用链式结构（二叉链表）实现二叉查找树，然后再进行调用。算法的基本思想是:先定义一个二叉树节点，然后实现二叉查找树的功能。程序的流程程序由三个模块组成：

3、（1）输入模块：输入一个数据表示数据的个数，然后输入一组数据即是二叉树节点处的数据。（2）计算模块：利用二叉查找链表來计算，二叉树来存储。（3）输出模块：屏幕上显示输入要查找的数据，然后输出查找是否成功并且要输出查找次数。三、详细设计物理数据类型本程序先定义二叉树的节点：classNode/二叉树结点public:Node*pLeftChild;Node*pRightChild;mtdata;NodeQpLeftCluld=NULL;pRightChild=NULL;data=O;然后在结点subroot中査找data,实现二叉査找树的功能:boolseaichTree(Node*subroo

4、tjntdata)/在结点subroot中查找数据data,二叉查找树if(subroot!=NULL)i+;if(datadata)returnsearchTree(subroot-pLeftChild,data);elseif(datasubroot-data)returnsearchTree(subroot-pRightCluld,data);elseif(data=subroot-data)coutH查找成功f,iendl;elsecoutH查找不成功Hiendl;returnfalse;boolcreatTree(Node*subroot,iiitdata)if(*subroot?=

5、NULL)if(datadata)creatTree(&(*subroot)-pLeftCliild),data);elseif(data(*subroot)-data)creatTree(&(*subroot)-pRiglitChild),data);else*subroot=newNode;(*subroot)-data=data;returntine;算法的时空分析此算法利用二叉查找树來实现，故次算法的的时间复杂度为0(N)o输入和输出的格式输入格式：在字符界面上输入一个数字表示节点(数据)的个数。请输入数据个数：输入一个数字/回车结束请输入查找数据：/输入要查找的总的数据，回车表示结束

6、输出格式：每当输入一个暑假，就输出查找成功或不成功，并且后面有数字表示查找的次数，例如：34/查找34,输出：查找成功1/表示查找时比较的次数。调试分析略。五、测试结果本实验的测试结果截图如下:据1查3查据1查3查1查功查键y数45欲麥零成蛍幕入6入咸入成入不入任S刖7SAU4-ML/.-knf/丄丄彳丄te请34请查请查请查请请pr8找26的5-数:192：4565找的数;：34找的数;：100Qt3找继心R分析:当输入字符型数据时，退出査找。六、用户使用说明（可选）1、本程序的运行环境为windows操作系统，执行文件为BST.exe2、运行程序时提示输入数据个数并且输入数据本程序可以实现

7、一个动态查找表，能实现构建和查找两个功能。提示：请输入表达式：输出提示：请输入查找数据：输出：查找成功/查找不成功并且后面注有查找次数七、实验心得（可选）本次实验较上次实验简单，所以做起來还算过得去。而且在实验过程中通过与同学的讨论加深了对二叉查找树的理解，对BST（二叉查找树）算法的应用有了初步的掌握。附录（实验代码）:#iiicludeusingnamespacestd;mt1=0;classNode/二叉树结点public:Node*pLeftChild;Node*pRightChild;mtdata;NodeQpLeftCluld=NULL;pRightChild=NULL;data=

8、O;boolseaichTree(Node*subrootjntdata)/在结点subroot中查找数据data,二叉查找树if(subroot!=NULL)i+;if(datadata)returnsearchTree(subroot-pLeftChild,data);elseif(datasubroot-data)returnsearchTree(subroot-pRightCluld,data);elseif(data=subroot-data)coutH查找成功niendl;elsecoutH查找不成功niendl;returnfalse;boolcreatTree(Node*sub

9、root,iiitdata)if(*subroot?=NULL)if(datadata)creatTree(&(*subroot)-pLeftCliild),data);elseif(data(*subroot)-data)creatTree(&(*subroot)-pRightChild),data);else*subroot=newNode;(*subroot)-data=data;returntine;严voidgoTiee(Node*subioot)if(subioot!=NULL)goTiee(subioot-pLeftChild);coutsubroot-dataendl;goTiee(subioot-pRightChild);访问方式：中序遍历*/（此函数可不用）mtNode*p=newNode;coutH请输入数据个数:endl;intM.N;ciiiM;coutH请输入数据:endl;c