数据结构实验报告六

BST（二叉查找树）实现动态查找表问题描述：利用二又查找树（BST）实现一个动态查找表。一、需求分析：1、 本程序是利用二又查找树（BST）来实现；二又树使用链式结构（二又链表）实现；本程序要实现BST的构建，查找两个功能。2、 输入输出格式：输入格式：在字符界面上输入一个数字表示节点（数据）的个数。请输入数据个数：输入一个数字〃回车结束请输入查找数据：〃输入要查找的总的数据，回车表示结束输出格式：每当输入一个暑假，就输出查找成功或不成功，并且后面有数字表示查找的次数，例如：34〃查找34,输出：查找成功1〃表示查找时比较的次数。3、 测试用例输入：8//BST的节点个数请输入数据：34,76,45,18,26,54,92,65〃8个数据请输入查找数：45〃查找45输出：查找成功3//返回成功和查找时比较的次数请输入查找数:34//查找34输出：查找成功1〃返回成功和查找时比较的次数请输入查找数:100//2找100输出：查找不成功3〃返回成功和查找时比较的次数注：当输入字符型数据时，程序会终止。二、概要设计:抽象数据类型BST,二叉查找树，先定义一个二叉树节点，然后实现二叉查找树的功能。算法的基本思想根据题目要求，要利用二义查找树（BST）来实现，所以先使用链式结构（二又链表）实现二又查找树，然后再进行调用。算法的基本思想是:先定义一个二又树节点，然后实现二叉查找树的功能。程序的流程程序由三个模块组成：（1） 输入模块：输入一个数据表示数据的个数，然后输入一组数据即是二又树节点处的数据。（2） 计算模块：利用二义查找链表来计算，二又树来存储。（3）输出模块：屏幕上显示输入要查找的数据，然后输出查找是否成功并且要输出查找次数。三、详细设计物理数据类型本程序先定义二叉树的节点：classNode//二叉树结点{public:Node*pLeftCluld;Node*pRightCluld;hitdata;NodeQ(pLeftCluld=NULL;pRightChild=NULL;data=O:)};然后在结点subroot中查找数据data,实现二叉查找树的功能:boolsearchTree(Node*subrootjntdata)〃在结点subroot中查找数据data,二叉查找树(if(subroot!=NULL){i++;if(data<subroot->data){returnsearchTiee(subroot->pLeftChild,data);}elseif(data>subroot->data){returnsearchTiee(subroot->pRightChild,data);}elseif(data=subroot->data){cout«H查找成功n«i«endl;}}else(cout«M查找不成功"«i«endl;

returnfalse;}}boolcreatTiee(Node**subroot,hitdata)(if(*subroot?=NULL)(if(data<(*subroot)->data)creatTree(&((*subroot)->pLeftChild),data);elseif(data>(*subroot)->data)creatTree(&((*subroot)->pRightChild),data);}else(*subroot=newNode;(*subroot)->data=data;}returntine;}算法的时空分析此算法利用二又查找树来实现，故次算法的的时间复杂度为0(N)。输入和输出的格式输入格式：在字符界面上输入一个数字表示节点(数据)的个数。请输入数据个数：输入一个数字〃回车结束请输入查找数据：〃输入要查找的总的数据，回车表示结束输出格式：每当输入一个暑假，就输出查找成功或不成功，并且后面有数字表示查找的次数，例如：34〃查找34,输出：查找成功1//表示查找时比较的次数。!1!调试分析!1!调试分析略。五、测试结果本实验的测试结果截图如下:

据i查3杳1查功查键据i查3杳1查功查键9数45欲豪欧成篁*入6入成入成入不入任S5数26的562954数的找3找继虹R00分析:当输入字符型数据时，退出查找。六、用户使用说明（可选）1、 本程序的运行环境为windows操作系统，执行文件为BST.exe2、 运行程序时提示输入数据个数并且输入数据本程序可以实现一个动态查找表，能实现构建和查找两个功能。提示：请输入表达式：输出提示：请输入查找数据：输出：查找成功/查找不成功并且后面注有查找次数七、实验心得（可选）本次实验较上次实验简单，所以做起来还算过得去。而且在实验过程中通过与同学的讨论加深了对二又查找树的理解，对BST（二兴查找树）算法的应用有了初步的掌握。附录（实验代码）:#iiiclude<iostieam>usingnamespacestd;mti=0;classNode//二叉树结点{public:Node*pLeftCluld;Node*pRightChild;hitdata;NodeQ(pLeftCluld=NULL;pRightChild=NULL;data=O;)};boolsearchTree(Node*subrootjntdata)〃在结点subroot中查找数据data,二叉查找树(if(subroot!=NULL){i++;if(data<subroot->data){returnsearchTree(subroot->pLeftChild,data);)elseif(data>subroot->data){returnsearchTree(subroot->pRightChild,data);}elseif(data=subroot->data){cout«H查找成功"«i«endl;}}else(cout«HS找不成功,,«i«endl;returnfalse;)}boolcreatTiee(Node**subroot,iiitdata)(if(*subroot?=NULL){if(data<(*subroot)->data)creatTree(&((*subroot)->pLeftCliild),data);elseif(data>(*subroot)->data)creatTree(&((*subroot)->pRightChild),data);)else(*subroot=newNode;(*subroot)->data=data;}returntrue;}/*voidgoTree(Node*subioot){iRsubioot!=NULL)(goTree(subroot->pLeftChild);cout«subroot->data«endl;goTree(subroot->pRightChild);)}访问方式：中序遍历*/(此函数可不用)mtNode*p=newNode;cout«H请输入数据个数:"«endl;intM.N;cout«n请输入数据:"«endl;cm»N;