数据结构实验报告六—BST（二叉查找树）实现动态查找表

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//查找 100

输出：查找不成功 3 //返回成功和查找时比较的次数 注：当输入字符型数据时，程序会终止。

二、概要设计 ：

抽象数据类型

BST，二叉查找树，先定义一个二叉树节点，然后实现二叉查找树的功能。

算法的基本思想

根据题目要求，要利用二叉查找树（BST）来实现，所以先使用链式结构（二叉链表）实现二叉查找树，然后再进行调用。

算法的基本思想是:先定义一个二叉树节点，然后实现二叉查找树的功能。 程序的流程

程序由三个模块组成：

（1） 输入模块：输入一个数据表示数据的个数，然后输入一组数据即是二叉树节点处的数据。

（2） 计算模块：利用二叉查找链表来计算，二叉树来存储。

（3 ） 输出模块：屏幕上显示输入要查找的数据，然后输出查找是否成功并且要输出查找次数。

三、详细设计

物理数据类型

本程序先定义二叉树的节点：

class Node // 二叉树结点 {

public:

Node* pLeftChild; Node* pRightChild; int data; Node()

{ pLeftChild=NULL; pRightChild=NULL; data=0; } };

然后在结点subroot中查找数据data ，实现二叉查找树的功能：

bool searchTree(Node* subroot,int data) //在结点subroot中查找数据data ，二叉查找树 { if(subroot!=NULL) {i++;

if(datadata)

{return searchTree(subroot->pLeftChild,data);} else if(data>subroot->data)

{return searchTree(subroot->pRightChild,data);} else if(data=subroot->data)

{cout<<\查找成功 \ } else

{cout<<\查找不成功 \

return false;} }

bool creatTree(Node** subroot,int data) { if(*subroot!=NULL)

{if(data<(*subroot)->data)

creatTree(&((*subroot)->pLeftChild),data); else if(data>(*subroot)->data)

creatTree(&((*subroot)->pRightChild),data);} else{*subroot=new Node; (*subroot)->data=data;} return true;}

算法的时空分析

此算法利用二叉查找树来实现，故次算法的的时间复杂度为O（N）。 输入和输出的格式

输入格式：在字符界面上输入一个数字表示节点（数据）的个数。

请输入数据个数：输入一个数字 //回车结束

请输入查找数据：//输入要查找的总的数据，回车表示结束

输出格式：每当输入一个暑假，就输出查找成功或不成功，并且后面有

数字表示查找的次数，例如：34//查找34，输出：查找成功 1//表示查找时比较的次数。

四、调试分析

略。

五、测试结果

本实验的测试结果截图如下：

分析:当输入字符型数据时，退出查找。

六、用户使用说明（可选）

1、本程序的运行环境为windows 操作系统，执行文件为 BST.exe 2 、运行程序时

提示输入数据个数 并且输入数据

本程序可以实现一个动态查找表，能实现构建和查找两个功能。 提示：请输入表达式： 输出

提示：请输入查找数据：

输出：查找成功/查找不成功 并且后面注有查找次数

七、实验心得（可选）

本次实验较上次实验简单，所以做起来还算过得去。而且在实验过程中通过与同学的讨论加深了对二叉查找树的理解，对BST（二叉查找树）算法的应用有了初步的掌握。

附录（实验代码）：

#include using namespace std; int i=0;

class Node // 二叉树结点 {

public:

Node* pLeftChild; Node* pRightChild; int data; Node()

{ pLeftChild=NULL; pRightChild=NULL;

data=0; } };

bool searchTree(Node* subroot,int data) //在结点subroot中查找数据data ，二叉查找树 { if(subroot!=NULL) {i++;

if(datadata)

{return searchTree(subroot->pLeftChild,data);} else if(data>subroot->data)

{return searchTree(subroot->pRightChild,data);} else if(data=subroot->data)

{cout<<\查找成功 \ } else {

cout<<\查找不成功 \ return false; } }

bool creatTree(Node** subroot,int data) { if(*subroot!=NULL)

{if(data<(*subroot)->data)

creatTree(&((*subroot)->pLeftChild),data); else if(data>(*subroot)->data)

creatTree(&((*subroot)->pRightChild),data); } else{

*subroot=new Node; (*subroot)->data=data; }

return true; } /*void goTree(Node* subroot){ if(subroot!=NULL){ goTree(subroot->pLeftChild); cout<data<pRightChild); } }访问方式：中序遍历*/（此函数可不用）

int main(){

Node* p=new Node;

cout<<\请输入数据个数:\int M,N; cin>>M;

cout<<\请输入数据:\cin>>N; p->data=N; while(++i>N;

creatTree(&p,N); } //goTree(p); int x;

cout<<\请输入欲查找的数:\while(cin>>x) { i=0;

searchTree(p,x);

cout<<\请输入欲查找的数:\}

system(\return 0; }

本文来源：https://www.bwwdw.com/article/r4ld.html