数据结构实验二叉排序树应用实验报告.docx
《数据结构实验二叉排序树应用实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构实验二叉排序树应用实验报告.docx（22页珍藏版）》请在冰点文库上搜索。
数据结构实验二叉排序树应用实验报告
实验报告
实验课程：
数据结构
实验项目：
实验四二叉排序树应用
专业：
计算机科学与技术
班级：
姓名：
学号：
指导教师：
一、问题定义及需求分析
（1）问题描述
（2）实验任务
（3）需求分析
二、概要设计：
（1）抽象数据类型定义
（2）主程序流程
（3）模块关系
三、详细设计
（1）数据类型及存储结构
（2）模块设计
四、调试分析
（1）调试分析
（2）算法时空分析
（3）经验体会
五、使用说明
（1）程序使用说明
六、测试结果
（1）运行测试结果截图
七、附录
（1）源代码
一、问题定义及需求分析
（1）实验目的
二叉排序树应用
问题描述
互联网域名系统是一个典型的树形层次结构。
从根节点往下的第一层是顶层域，如cn、com等，最底层（第四层）是叶子结点，如www等。
因此，域名搜索可以构造树的结构完成；
（2）实验任务
设计基于二叉排序树的搜索互联网域名的程序。
（3）需求分析：
1）采用二叉树的二叉链表存储结构。
2）完成二叉排序树的创建、插入、删除、查询操作。
3）可以考虑两棵二叉排序树的合并。
二、概要设计：
（1）抽象数据类型定义：
程序中定义了二叉排序树的节点类型；由数据域和左右孩子指针构成；指针类型为该节点类型，指向该类型的节点形成二叉排序树；数据域是由字符数组构成，用于存储节点数据信息。
（2）主程序流程：
（3）
输入域名拆分域名并完成二叉排序树的创建调用功能函数进入功能菜单选择执行不同的操作（查找、插入、删除）操作完毕后可选择返回功能函数继续执行操作或者结束程序
（4）模块间的调用关系:
创建二叉排序树
功能函数
查找插入删除
选择
结束
三、详细设计
采用二叉链表存储结构的二叉排序树的定义如下：
typedefstructBiTNode
{
ElemTypedata[30];//定义数据域类型为字符数组
structBiTNode*lchild,*rchild;//定义左右孩子节点指针
}BiTNode,*BiTree;
模块1-查找树中是否有待插入节点
算法如下：
intSearchBST（BiTreeT,char*key,BiTreef,BiTree*p）
{
if（!
T）/*查找不成功*/
{
*p=f;
return0;
}
elseif（strcmp（key,T->data）==0）/*查找成功*/
{
*p=T;
return1;
}
elseif（strcmp（key,T->data）<0）
returnSearchBST（T->lchild,key,T,p）;/*若该节点小于当前节点，则在左子树中继续查找*/
else
returnSearchBST（T->rchild,key,T,p）;/*否则在右子树中继续查找*/
}
模块2-插入节点
算法如下：
intInsertBST（BiTree*T,char*key）
{
BiTreep,s;
if（!
SearchBST（*T,key,NULL,&p））/*查找不成功*/
{
s=（BiTNode*）malloc（sizeof（BiTNode））;
strcpy（s->data,key）;
s->lchild=s->rchild=NULL;
if（!
p）
*T=s;/*插入s为新的根结点*/
elseif（strcmp（key,p->data）<0）
p->lchild=s;/*插入s为左孩子*/
else
p->rchild=s;/*插入s为右孩子*/
return1;
}
else
return0;/*树中已有关键字相同的结点，不再插入*/
}
模块3-删除节点
算法如下：
intDelete（BiTree*p）
{
BiTreeq,s;
if（（*p）->rchild==NULL）/*右子树空则只需重接它的左子树（待删结点是叶子也走此分支）*/
{
q=*p;
*p=（*p）->lchild;
free（q）;
}
elseif（（*p）->lchild==NULL）/*只需重接它的右子树*/
{
q=*p;
*p=（*p）->rchild;
free（q）;
}
else/*左右子树均不空*/
{
q=*p;
s=（*p）->lchild;
while（s->rchild）/*转左，然后向右到尽头（找待删结点的前驱）*/
{
q=s;
s=s->rchild;
}
strcpy（（*p）->data,s->data）;/*s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值）*/
if（q!
=*p）
q->rchild=s->lchild;/*重接q的右子树*/
else
q->lchild=s->lchild;/*重接q的左子树*/
free（s）;
}
return1;
}
模块4-查找待删除节点的位置
算法如下：
intDeleteBST（BiTree*T,char*key）
{
if（!
*T）/*不存在关键字等于key的数据元素*/
return0;
else
{
if（strcmp（key,（*T）->data）==0）/*找到关键字等于key的数据元素*/
returnDelete（T）;
elseif（strcmp（key,（*T）->data）<0）
returnDeleteBST（&（*T）->lchild,key）;/*若待删除节点大于当前节点，则递归访问其左子树*/
else
returnDeleteBST（&（*T）->rchild,key）;/*否则访问右子树*/
}
}
模块5-功能函数包括查找、插入和删除
算法如下:
voidGongneng（BiTNode*A）
{//执行操作需将此树的根节点传入到此函数里面
intk;
chara[30],c[30],d[30];
printf（"请选择你的操作：
\n"）;
printf（"1-查找\n"）;
printf（"2-删除\n"）;
printf（"3-插入\n"）;
printf（"输入：
"）;
scanf（"%d",&k）;
switch（k）
{//通过switch语句执行不同的操作
case1:
system（"cls"）;
printf（"请输入你要查找的节点：
"）;
scanf（"%s",c）;
Search（A,c）;//调用查找函数
break;
case2:
system（"cls"）;
printf（"请输入你要删除的节点：
"）;
scanf（"%s",a）;
if（!
DeleteBST（&A,a））
printf（"\n不存在此节点！
\n"）;
else
{printf（"\n删除节点成功！
\n\n删除后树的中序遍历结果如下：
\n"）;
InOrder（A）;}
break;
case3:
system（"cls"）;
printf（"请输入要插入的节点：
"）;
scanf（"%s",d）;
if（!
InsertBST（&A,d））
printf（"插入失败!
要插入的节点已存在!
\n"）;
else
{
printf（"\n插入成功!
\n\n插入后树的中序遍历结果如下：
\n"）;
InOrder（A）;
}
break;
default:
printf（"输入数值错误!
\n"）;
}
}
四、调试分析
问题及解决方法：
在编写功能函数时，在参数的传递上出现了问题；无法正确的将根节点传入到功能函数里，导致功能函数无法正常运行；解决方法为：
voidGongneng（BiTNode*A）；
时空分析：
由于采用二叉链表的存储结构，所以在插入和删除算法的时间复杂度较低；而对于较多的数据元素形成的树时，查找算法在时间复杂度上不算简便；而存储方面，二叉链表构成的二叉排序树存储较为方便且空间利用率高；
经验体会:
二叉链表存储结构的存储密度较高，使用起来较为方便；而且在处理数据方面，二叉链表存储结构的处理性比较好，尤其是对插入和删除算法；
五、使用说明
第一步：
点击运行按钮；
第二步:
输入待输入的域名个数k；
第三步：
依次输入k个域名；
第四步：
回车，程序跳转至功能界面，根据提示输入想要执行的功能选项序号；
第五步：
回车后，针对各功能项有提示药查找、插入或者删除的节点；
第六步：
执行功能后，选择结束运行还是继续操作；
第七步：
若选择继续操作，则程序进入功能界面，可继续选择执行的功能；
第八步：
循环执行第四到七步；
第九步：
可在第六步选择退出程序；
六、测试结果
七、附录
源代码：
#include
#include
#include
#defineElemTypechar
typedefstructBiTNode
{
ElemTypedata[30];//定义数据域类型为字符数组
structBiTNode*lchild,*rchild;//定义左右孩子节点指针
}BiTNode,*BiTree;
intSearchBST（BiTreeT,char*key,BiTreef,BiTree*p）
{
if（!
T）//树为空，查找不成功
{
*p=f;
return0;
}
elseif（strcmp（key,T->data）==0）//查找成功
{
*p=T;//p指向查找到的节点
return1;
}
elseif（strcmp（key,T->data）<0）
returnSearchBST（T->lchild,key,T,p）;//在左子树中继续查找
else
returnSearchBST（T->rchild,key,T,p）;//在右子树中继续查找
}
intInsertBST（BiTree*T,char*key）
{
BiTreep,s;
if（!
SearchBST（*T,key,NULL,&p））//查找不成功
{
s=（BiTNode*）malloc（sizeof（BiTNode））;//s作为插入节点
strcpy（s->data,key）;
s->lchild=s->rchild=NULL;
if（!
p）
*T=s;//插入s为新的根结点
elseif（strcmp（key,p->data）<0）
p->lchild=s;//插入s为左孩子
else
p->rchild=s;//插入s为右孩子
return1;
}
else
return0;//树中已有关键字相同的结点，不再插入
}
intSearch（BiTNode*N,char*key）
{//查找树中是否存在要插入的节点
BiTNode*M;
M=N;
while（M!
=NULL&&strcmp（M->data,key）!
=0）
{//查找终止条件为树为空或者查找的节点数据与待查找的数据相同
if（strcmp（M->data,key）<0）
M=M->rchild;//继续查找左子树
else
M=M->lchild;//继续查找右子树
}
if（!
M）
printf（"查找失败！
\n"）;
else
printf（"查找成功！
\n"）;
}
/*从二叉排序树中删除结点p，并重接它的左或右子树。
*/
intDelete（BiTree*p）
{
BiTreeq,s;
if（（*p）->rchild==NULL）//右子树空则只需重接它的左子树（待删结点是叶子也走此分支）
{
q=*p;
*p=（*p）->lchild;
free（q）;//释放该节点
}
elseif（（*p）->lchild==NULL）//只需重接它的右子树
{
q=*p;
*p=（*p）->rchild;
free（q）;//释放该节点
}
else//左右子树均不空
{
q=*p;
s=（*p）->lchild;
while（s->rchild）//转左，然后向右到尽头（找待删结点的前驱）
{
q=s;
s=s->rchild;
}
strcpy（（*p）->data,s->data）;//s指向被删结点的直接前驱（将被删结点前驱的值取代被删结点的值）
if（q!
=*p）
q->rchild=s->lchild;//重接q的右子树
else
q->lchild=s->lchild;//重接q的左子树
free（s）;
}
return1;
}
intDeleteBST（BiTree*T,char*key）
{
if（!
*T）//不存在关键字等于key的数据元素
return0;
else
{
if（strcmp（key,（*T）->data）==0）//找到关键字等于key的数据元素
returnDelete（T）;//调用Delete函数删除该节点
elseif（strcmp（key,（*T）->data）<0）
returnDeleteBST（&（*T）->lchild,key）;//继续访问左子树
else
returnDeleteBST（&（*T）->rchild,key）;//继续访问右子树
}
}
voidInOrder（BiTNode*root）{//中序遍历该二叉排序树
if（!
root）return;//递归结束条件
InOrder（root->lchild）;//递归访问左子树
printf（"%s\n",root->data）;//访问根节点信息
InOrder（root->rchild）;//递归访问右子树
}
voidGongneng（BiTNode*A）
{
intk;
chara[30],c[30],d[30];
printf（"请选择你的操作：
\n"）;
printf（"1-查找\n"）;
printf（"2-删除\n"）;
printf（"3-插入\n"）;
printf（"输入：
"）;
scanf（"%d",&k）;
switch（k）
{
case1:
system（"cls"）;
printf（"请输入你要查找的节点：
"）;
scanf（"%s",c）;
Search（A,c）;//调用查找函数
break;
case2:
system（"cls"）;
printf（"请输入你要删除的节点：
"）;
scanf（"%s",a）;
if（!
DeleteBST（&A,a））
printf（"\n不存在此节点！
\n"）;
else
{printf（"\n删除节点成功！
\n\n删除后树的中序遍历结果如下：
\n"）;
InOrder（A）;}//删除后，进行一次遍历检查删除后的二叉排序树
break;
case3:
system（"cls"）;
printf（"请输入要插入的节点：
"）;
scanf（"%s",d）;
if（!
InsertBST（&A,d））
printf（"插入失败!
要插入的节点已存在!
\n"）;
else
{
printf（"\n插入成功!
\n\n插入后树的中序遍历结果如下：
\n"）;
InOrder（A）;//插入成功后，中序遍历该树
}
break;
default:
printf（"输入数值错误!
\n"）;
}
}
intmain（）
{
BiTNode*A;
A=（BiTNode*）malloc（sizeof（BiTNode））;//A为根节点
A->lchild=A->rchild=NULL;
A->data[0]='';
intj,k,m=1;
charb[30];
char*s,*t;
printf（"请首先创建一棵树并输入要输入的域名个数：
"）;
scanf（"%d",&k）;
for（j=0;j{
BiTNode*X;
char*str;
inti;
charZhongZhuan[15];//定义中转数组
X=A;
printf（"请输入网址%d：
",j+1）;
scanf（"%s",b）;
s=b;//s指向数组b
_strrev（s）;//将该字符数组反转
for（;s!
='\0';）
{
str=strchr（s,'.'）;//str为字符串s里面首次出现‘.’的位置
if（str）
{
i=str-s;
ZhongZhuan[i+1]='\0';
for（;i>=0;i--,s++）
{
ZhongZhuan[i]=s[0];//采用倒叙插入，将字符串插入到中转数组里面
}
}
else
{//剩余字符串不含’.’，则中转数组的实际大小为剩余字符串的长度
_strrev（s）;
i=strlen（s）;
ZhongZhuan[i+1]='\0';
for（;i>=0;i--）
{
ZhongZhuan[i]=s[i];//同样采用倒叙插入的方法为中转数组赋值
}
s='\0';
}
InsertBST（&A,ZhongZhuan）;//将中转数组的信息插入到树中
}
}
printf（"中序遍历结果为：
\n"）;
while（m）
{
system（"cls"）;
Gongneng（A）;//调用功能函数
printf（"是否继续操作？
\t是-请输入1；否-请输入0\n"）;
printf（"输入:
"）;
scanf（"%d",&m）;
}
system（"cls"）;
printf（"谢谢使用!
"）;
}
升级会员 