实验报告实验课程：数据结构实验项目：实验四二叉排序树应用专业：计算机科学与技术班级：姓名：学号：指导教师：目录一、问题定义及需求分析（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); /* 若该节点小于当前节点，则在左子树中继续查找*/elsereturn 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为左孩子*/elsep->rchild = s; /* 插入s为右孩子*/return 1;}elsereturn 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的右子树*/elseq->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);/* 若待删除节点大于当前节点，则递归访问其左子树*/elsereturn 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个域名；第四步：回车，程序跳转至功能界面，根据提示输入想要执行的功能选项序号；第五步：回车后，针对各功能项有提示药查找、插入或者删除的节点；第六步：执行功能后，选择结束运行还是继续操作；第七步：若选择继续操作，则程序进入功能界面，可继续选择执行的功能；第八步：循环执行第四到七步；第九步：可在第六步选择退出程序；六、测试结果七、附录源代码：#include<stdio.h>#include<stdlib.h>#include<string.h>#define ElemType chartypedef struct BiTNode{ElemType data[30]; //定义数据域类型为字符数组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)<0)return SearchBST(T->lchild, key, T, p); // 在左子树中继续查找elsereturn 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)<0)p->lchild = s; // 插入s为左孩子elsep->rchild = s; // 插入s为右孩子return 1;}elsereturn 0; // 树中已有关键字相同的结点，不再插入}int Search(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; // 继续查找左子树elseM=M->lchild; // 继续查找右子树}if(!M)printf("查找失败！\n");elseprintf("查找成功！\n");}/* 从二叉排序树中删除结点p，并重接它的左或右子树。
