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

实 验 报 告 实验课程：数 据 结 构 实验项目：实验四二叉排序树应用 专 业：计算机科学与技术 班 级： 姓 名： 学 号： 指导教师： 目 录1、 问题定义及需求分析 （1）问题描述 （2）实验任务 （3）需求分析二、概要设计： (1)抽象数据类型定义 (2)主程序流程 (3) 模块关系3、 详细设计 (1)数据类型及存储结构 (2)模块设计4、 调试分析 (1)调试分析 (2)算法时空分析 (3)经验体会5、 使用说明 (1)程序使用说明6、 测试结果 (1)运行测试结果截图7、 附录 (1)源代码1、 问题定义及需求分析（1）实验目的 二叉排序树应用 问题描述 互联网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如cn、com等，最底层（第四层）是叶子结点，如www等。因此，域名搜索可以构造树的结构完成；（2）实验任务 设计基于二叉排序树的搜索互联网域名的程序。（3）需求分析： 1）采用二叉树的二叉链表存储结构。 2）完成二叉排序树的创建、插入、删除、查询操作。 3）可以考虑两棵二叉排序树的合并。2、 概要设计：(1)抽象数据类型定义： 程序中定义了二叉排序树的节点类型；由数据域和左右孩子指针构成；指针类型为该节点类型，指向该类型的节点形成二叉排序树；数据域是由字符数组构成，用于存储节点数据信息。(2) 主程序流程： 输入域名 拆分域名并完成二叉排序树的创建 调用功能函数进入功能菜单 选择执行不同的操作(查找、插入、删除) 操作完毕后可选择返回功能函数继续执行操作或者结束程序 (3) 模块间的调用关系: 创建二叉排序树 功能函数 查找 插入 删除 选择 结束 三、详细设计 采用二叉链表存储结构的二叉排序树的定义如下： typedef struct BiTNodeElemType data30; /定义数据域类型为字符数组 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)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)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)lchild,key);/* 若待删除节点大于当前节点，则递归访问其左子树 */ else return DeleteBST(&(*T)-rchild,key);/* 否则访问右子树 */ 模块5-功能函数包括查找、插入和删除算法如下:void Gongneng(BiTNode *A)/ 执行操作需将此树的根节点传入到此函数里面int k;char a30,c30,d30;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);elseprintf(n删除节点成功！nn删除后树的中序遍历结果如下：n);InOrder(A); break;case 3:system(cls);printf(请输入要插入的节点：);scanf(%s,d);if(!InsertBST(&A,d)printf(插入失败!要插入的节点已存在!n);elseprintf(n插入成功!nn插入后树的中序遍历结果如下：n); InOrder(A);break; default : printf(输入数值错误!n);四、调试分析 问题及解决方法： 在编写功能函数时，在参数的传递上出现了问题；无法正确的将根节点传入到功能函数里，导致功能函数无法正常运行；解决方法为：void Gongneng(BiTNode *A)； 时空分析： 由于采用二叉链表的存储结构，所以在插入和删除算法的时间复杂度较低；而对于较多的数据元素形成的树时，查找算法在时间复杂度上不算简便；而存储方面，二叉链表构成的二叉排序树存储较为方便且空间利用率高； 经验体会: 二叉链表存储结构的存储密度较高，使用起来较为方便；而且在处理数据方面，二叉链表存储结构的处理性比较好，尤其是对插入和删除算法；五、使用说明第一步：点击运行按钮；第二步: 输入待输入的域名个数k；第三步：依次输入k个域名；第四步：回车，程序跳转至功能界面，根据提示输入想要执行的功能选项序号；第五步：回车后，针对各功能项有提示药查找、插入或者删除的节点；第六步： 执行功能后，选择结束运行还是继续操作；第七步：若选择继续操作，则程序进入功能界面，可继续选择执行的功能；第八步：循环执行第四到七步；第九步：可在第六步选择退出程序；六、测试结果七、附录源代码：#include#include#include#define ElemType chartypedef struct BiTNodeElemType data30; /定义数据域类型为字符数组 struct BiTNode *lchild, *rchild; /定义左右孩子节点指针BiTNode, *BiTree;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; /p指向查找到的节点 return 1; else if (strcmp(key,T-data)lchild, key, T, p); / 在左子树中继续查找 else return SearchBST(T-rchild, key, T, p); / 在右子树中继续查找 int InsertBST(BiTree *T, char *key) BiTree p,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为新的根结点 else if (strcmp(key,p-data)lchild = s; / 插入s为左孩子 else p-rchild = s; / 插入s为右孩子 return 1; else return 0; / 树中已有关键字相同的结点，不再插入int Search(BiTNode *N,char *key) / 查找树中是否存在要插入的节点 BiTNode *M; M=N; while(M!=NULL&strcmp(M-data,key)!=0) / 查找终止条件为树为空或者查找的节点数据与待查找的数据相同 if(strcmp(M-data,key)rchild; / 继续查找左子树 else M=M-lchild; / 继续查找右子树 if(!M) printf(查找失败！n); else printf(查找成功！n);/* 从二叉排序树中删除结点p，并重接它的左或右子树。 */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;int DeleteBST(BiTree *T,char *key) if(!*T) /不存在关键字等于key的数据元素 return 0; else if (strcmp(key,(*T)-data)=0) /找到关键字等于key的数据元素 return Delete(T); /调用Delete函数删除该节点 else if (strcmp(key,(*T)-data)lchild,key);/ 继续访问左子树 else return DeleteBST(&(*T)-rchild,key);/继续访问右子树 void InOrder (BiTNode *root) /中序遍历该二叉排序树if (!root) return ; /递归结束条件InOrder (root-lchild); /递归访问左子树printf (%sn, root-data);/访问根节点信息InOrder (root-rchild);/递归访问右子树void Gongneng(BiTNode *A)int k;char a30,c30,d30;printf(请选择你的操作：n);printf(1-查找n);printf(2-删除n);printf(3-插入n);printf(输入：);scanf(%d,&k);switch(k)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);elseprintf(n删除节点成功！nn删除后树的中序遍历结果如下：n);InOrder(A);/删除后，进行一次遍历检查删除后的二叉排序树 break;case 3:system(cls);printf(请输入要插入的节点：);scanf(%s,d);if(!InsertBST(&A,d)printf(插入失败!要插入的节点已存在!n);elseprintf(n插入成功!nn插入后树的中序遍历结果如下：n); InOrder(A);/插入成功后，中序遍历该