数据结构bst的构建与查找实验报告Word格式.docx
《数据结构bst的构建与查找实验报告Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构bst的构建与查找实验报告Word格式.docx（15页珍藏版）》请在冰点文库上搜索。
查找成功，比较次数为3
2.请输入节点个数：
678
查找失败，比较次数为3
3．请输入节点个数：
c
输入有误请重新输入
4.请输入节点个数：
12,4,35,78,56,&
89.3,A
输入有误，请重新输入
二．概要设计
抽象数据类型
1.在本程序中，需要对插入的节点进行检索，而BST的插入和检索的速率都是很高的，所以我们选用构建BST的方法来解决这项问题；
2.由用户输入的节点个数及节点数据均为正整数，可使用整型数据进行存储，并构建一个BST存储这些节点数据；
3.为了节约空间，使用二叉链表实现BST；
4.为了能查询表中数据，定义一个二叉树节点类，其ADT设计如下：
数据类型：
整型数据
数据关系：
二叉树所对应的数据关系
基本操作：
intval（）;
//返回结点的数值
voidsetLeft（Node*）;
//设置左结点
voidsetRight（Node*）;
//设置右结点
Node*left（）const;
//返回左结点
Node*right（）const;
//返回右结点
4.为了存储这些数据，构建一个二叉查找树，其ADT设计如下：
数据关系:
voidclear（）;
//初始化操作
boolinsert（constElem&
）;
//插入元素的操作
boolfind（constElem&
）const;
//查找元素的操作
算法基本思想
该算法主要包括表的构建和查询两项：
1在表的构建上，通过用户输入的数据，将第一个输入的节点数据存入根节点中，从第二个节点元素开始，与根节点数据进行比较，如果该元素大于根节点的值，则与根节点的右子节点相比较，若右子节点为空，则将该元素存入这个节点，若不为空，则将该右子节点视为根节点，重复上述步骤。
而若该元素小于根节点的值，则与根节点左子节点相比较，若左子节点为空，则将该元素存入这个节点，若不为空，则将该左子节点视为根节点，重复上述步骤。
直到所有的输入的元素都存进表中为止；
2在表的查询上，通过用户输入的查询的数值，将该数据与已建好的表的根节点相比较，比较次数+1，当两个数相等时，输出查找成功，比较次数为1。
当该数小于根节点的数时，若左子节点不为空，则视根节点的左子节点为根节点，将该数据与新的根节点相比较，比较次数加1，重复上述步骤，直到左子节点为空。
当该数大于根节点的数时，若右子节点不为空，则视根节点的右子节点为根节点，将该数据与新的根节点相比较，比较次数加1，重复上述步骤，直到两个数相等或者直到子节点为空时结束循环。
若找到相等的元素，则输出查找成功以及相应的比较次数，若子节点为空时仍然没有查找到该元素，则输出未查找到该元素以及相对应的查找次数；
程序基本流程
本程序主要包括输入、构建BST、查询和输出四个模块，其流程图如下：
三．详细设计
物理数据类型
1.用户输入的节点个数使用int型数据进行存储，用户输入的节点的数据通过构建一个Node类进行存储，Node类详细ADT设计如下：
classNode
{
private:
intdata;
//节点数据
Node*p1;
//指向左子节点的指针
Node*p2;
//指向右子节点的指针
public:
intval（）{returndata;
};
//返回结点的数值
voidsetLeft（Node*it）{p1=it;
voidsetRight（Node*it）{p2=it};
Node*left（）const{returnp1;
};
Node*right（）const{returnp2;
}
2.采用二叉链表实现BST，二叉链表ADT设计如下：
classBST
private:
Node*root;
//根节点
public:
BST（）{root=NULL;
}//构造函数
~BST（）{deleteroop;
}//析构函数
voidclear（）
{root=NULL;
}//初始化操作
boolinsert（constint&
it）//插入操作
{
Node*subroot1=root;
Node*subroot2=root;
if（root==NULL）{root=newNode（it）;
}//传给根节点值
while（subroot1!
=NULL）
subroot2=subroot1;
if（it<
subroot1.val（））
subroot1=subroot1.Left（）;
else
subroot1=subroot1.Right（）;
if（subroot2.val（）>
it）
subroot2.setLeft（newNode（it））;
//设置左子节点
else
subroot2.setRight（newNode（it））;
//设置右子节点
returntrue;
boolfind（int&
it）//查找操作
Node*subroot=root;
intcount=0;
//
while（subroot!
if（it==subroot.val（））
{count++;
}//查找成功
elseif（it<
subroot.val（））
{subroot=subroot.Left（）;
count++;
//在左子节点进行查找
elseif（it>
{subroot=subroot.Right（）;
//在右子节点进行查找
returnfalse;
//查找失败
算法具体步骤
本算法主要包括以下几个模块：
1.输入模块：
cin>
>
n;
for（inti=0;
i<
i++）
cin>
num;
FindNum;
2.构建BST模块：
Tree.insert（num）;
3.查找模块：
使用find函数查询该BST中是否有节点的数据为FindNum
4.输出模块：
if（Tree.find（FindNum）==true）
cout<
<
”查找成功,比较次数为“<
count<
”次”；
if（Tree.find（FindNum）==false）
”查找失败,比较次数为“<
函数关系调用
建表for（inti=0;
算法
true输出“查找成功“及比较次数
查找Tree.find（FindNum）
false输出“查找失败“及比较次数
算法时空分析
n个元素的BST高度约为log2n,而该算法的插入的最坏情况是在BST最底端进行插入，所以插入的时间复杂度为Θ（logn），当用户输入规模为n个时，插入的算法时间复杂度为Θ（nlogn）。
查找的时间复杂度最坏情况也是在最底端找到或者查找失败，时间复杂度为Θ（logn），
所以算法总时间复杂度为Θ（nlogn）。
输入输出格式
输入：
13584219224410065
42
13
12
输出：
查找成功，比较次数为1
源代码：
#include<
iostream>
usingnamespacestd;
doubledata;
Node（doubleit）{data=it;
p1=NULL;
p2=NULL;
};
~Node（）{delete[]p1;
delete[]p2;
voidsetLeft（Node*item）{p1=item;
voidsetRight（Node*item）{p2=item;
Node*Left（）const{returnp1;
//返回左结点
Node*Right（）const{returnp2;
doubleval（）
{
returndata;
intcount;
BST（）{root=NULL;
count=0;
}//构造函数
//~BST（）{delete[]root;
}//析构函数
root=NULL;
}//初始化操作
voidinsert（constdouble&
if（root==NULL）{root=newNode（it）;
}//传给根节点值
Node*subroot1=root;
Node*subroot2=root;
while（subroot1!
=NULL）
{
subroot2=subroot1;
if（it<
subroot1->
val（））
subroot1=subroot1->
Left（）;
else
Right（）;
}
if（subroot2->
val（）>
subroot2->
setLeft（newNode（it））;
//设置左子节点
else
setRight（newNode（it））;
//设置右子节点
}
intfind（double&
count=0;
Node*subroot=root;
while（subroot!
if（it==subroot->
{
count++;
return1;
}//查找成功
elseif（it<
subroot->
subroot=subroot->
count++;
}
//在左子节点进行查找
elseif（it>
//在右子节点进行查找
return0;
intjudge（）
//对输入的合法性进行判断并返回有效的输入
inttemp;
cin.sync（）;
//清空输入流缓冲区
cin>
temp;
while
（1）
if（cin.fail（）||cin.bad（）||cin.get（）!
='
\n'
）//验证输入是否合法，其中cin.fail（）和cin.bad（）解决输入字符串和溢出的问题
cout<
"
输入有误，请重新输入:
\n"
;
//cin.get（）检查输入流中是否还有字符（如果有就表示输入的是形如123r或12.3的错误
elsebreak;
//输入合法则跳出循环
cin.clear（）;
//清空输入流缓冲区标志位，以免影响下次输入
cin.sync（）;
cin>
returntemp;
intmain（）
BSTTree;
Tree.count=0;
intn;
doublenum;
doubleFindNum;
cout<
n=judge（）;
if（n==-1）
return0;
请输入个节点的数据：
for（inti=0;
i<
n;
i++）
cin>
num;
Tree.insert（num）;
请输入要查询的节点：
if（Tree.find（FindNum）==1）
查找成功，比较次数为"
<
Tree.count<
次\n\n"
elseif（Tree.find（FindNum）==0）
查找失败,比较次数为"
system（"
pause>
NUL"
升级会员 