数据结构实验-二叉排序树应用实验报告

实 验 报 告

实验课程：数 据 结 构

实验项目：实验四二叉排序树应用

专 业：计算机科学与技术

班 级：

姓 名：

学 号：

指导教师：

目 录

一、问题定义及需求分析

（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)模块间的调用关系:

创建二叉排序树

功能函数

查找 插入 删除

选择

结束

三、详细设计

采用二叉链表存储结构的二叉排序树的定义如下：

typedef struct BiTNode

{

ElemType data[30]; //定义数据域类型为字符数组

struct BiTNode *lchild, *rchild; //定义左右孩子节点指针

}BiTNode, *BiTree;

模块1-查找树中是否有待插入节点

算法如下：

int SearchBST(BiTree T, char *key, BiTree f, BiTree *p)

{

if (!T) /* 查找不成功 */

{

*p = f;

return 0;

}

else if(strcmp(key,T->data)==0) /* 查找成功 */

{

*p = T;

return 1;

}

else if (strcmp(key,T->data)<0)

return SearchBST(T->lchild, key, T, p); /* 若该节点小于当前节点，则在左子树中继续查找 */

else

return SearchBST(T->rchild, key, T, p); /* 否则在右子树中继续查找 */

}

模块2-插入节点

算法如下：

int InsertBST(BiTree *T, char *key)

{

BiTree p,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为新的根结点 */

else if (strcmp(key,p->data)<0)

p->lchild = s; /* 插入s为左孩子 */ else

p->rchild = s; /* 插入s为右孩子 */

return 1;

}

else

return 0; /* 树中已有关键字相同的结点，不再插入 */

}

模块3-删除节点

算法如下：

int Delete(BiTree *p)

{

BiTree q,s;

if((*p)->rchild==NULL) /* 右子树空则只需重接它的左子树（待删结点是叶子也走此分支)

*/

{

q=*p;

*p=(*p)->lchild;

free(q);

}

else if((*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);

}

return 1;

} 模块4-查找待删除节点的位置

算法如下：

int DeleteBST(BiTree *T,char *key)

{

if(!*T) /* 不存在关键字等于key的数据元素 */

return 0;

else

{

if (strcmp(key,(*T)->data)==0) /* 找到关键字等于key的数据元素 */

return Delete(T);

else if (strcmp(key,(*T)->data)<0)

return DeleteBST(&(*T)->lchild,key);/* 若待删除节点大于当前节点，则递归访问其左子树 */

else

return DeleteBST(&(*T)->rchild,key);/* 否则访问右子树 */

}

}

模块5-功能函数包括查找、插入和删除

算法如下:

void Gongneng(BiTNode *A)

{// 执行操作需将此树的根节点传入到此函数里面

int k;

char a[30],c[30],d[30];

printf("请选择你的操作：\n");

printf("1-查找\n");

printf("2-删除\n");

printf("3-插入\n");

printf("输入：");

scanf("%d",&k);

switch(k)

{//通过switch语句执行不同的操作

case 1 :

system("cls");

printf("请输入你要查找的节点：");

scanf("%s",c);

Search(A, c); //调用查找函数

break;

case 2:

system("cls");

printf("请输入你要删除的节点：");

scanf("%s",a);

if(!DeleteBST(&A,a)) printf("\n不存在此节点！\n");

else

{printf("\n删除节点成功！\n\n删除后树的中序遍历结果如下：\n");

InOrder(A);}

break;

case 3:

system("cls");

printf("请输入要插入的节点：");

scanf("%s",d);

if(!InsertBST(&A,d))

printf("插入失败!要插入的节点已存在!\n");

else

{

printf("\n插入成功!\n\n插入后树的中序遍历结果如下：\n");

InOrder(A);

}

break;

default : printf("输入数值错误!\n");

}

}

四、调试分析

问题及解决方法：

在编写功能函数时，在参数的传递上出现了问题；无法正确的将根节点传入到功能函数里，导致功能函数无法正常运行；解决方法为：void Gongneng(BiTNode *A)；

时空分析：

由于采用二叉链表的存储结构，所以在插入和删除算法的时间复杂度较低；而对于较多的数据元素形成的树时，查找算法在时间复杂度上不算简便；而存储方面，二叉链表构成的二叉排序树存储较为方便且空间利用率高；

经验体会:

二叉链表存储结构的存储密度较高，使用起来较为方便；而且在处理数据方面，二叉链表存储结构的处理性比较好，尤其是对插入和删除算法；

五、使用说明

第一步：点击运行按钮；

第二步: 输入待输入的域名个数k；

第三步：依次输入k个域名；

第四步：回车，程序跳转至功能界面，根据提示输入想要执行的功能选项序号；

第五步：回车后，针对各功能项有提示药查找、插入或者删除的节点；

第六步： 执行功能后，选择结束运行还是继续操作；

第七步：若选择继续操作，则程序进入功能界面，可继续选择执行的功能；

第八步：循环执行第四到七步；