资源描述：
《数据结构实验-二叉排序树应用实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、.实验报告实验课程：数据结构实验项目：实验四二叉排序树应用专业：计算机科学与技术班级：姓名：学号：指导教师：教育资料.目录一、问题定义及需求分析（1）问题描述（2）实验任务（3）需求分析二、概要设计：(1)抽象数据类型定义(2)主程序流程(3)模块关系三、详细设计(1)数据类型及存储结构(2)模块设计四、调试分析(1)调试分析(2)算法时空分析(3)经验体会五、使用说明(1)程序使用说明六、测试结果(1)运行测试结果截图七、附录(1)源代码教育资料.一、问题定义及需求分析（1）实验目的二叉排序树应用问题描述互联
2、网域名系统是一个典型的树形层次结构。从根节点往下的第一层是顶层域，如cn、com等，最底层（第四层）是叶子结点，如www等。因此，域名搜索可以构造树的结构完成；（2）实验任务设计基于二叉排序树的搜索互联网域名的程序。（3）需求分析：1）采用二叉树的二叉链表存储结构。2）完成二叉排序树的创建、插入、删除、查询操作。3）可以考虑两棵二叉排序树的合并。二、概要设计：(1)抽象数据类型定义：程序中定义了二叉排序树的节点类型；由数据域和左右孩子指针构成；指针类型为该节点类型，指向该类型的节点形成二叉排序树；数据域是由字符
3、数组构成，用于存储节点数据信息。(2)主程序流程：输入域名拆分域名并完成二叉排序树的创建调用功能函数进入功能菜单选择执行不同的操作(查找、插入、删除)操作完毕后可选择返回功能函数继续执行操作或者结束程序(3)模块间的调用关系:创建二叉排序树功能函数查找插入删除选择结束教育资料.三、详细设计采用二叉链表存储结构的二叉排序树的定义如下：typedefstructBiTNode{ElemTypedata[30];//定义数据域类型为字符数组structBiTNode*lchild,*rchild;//定义左右孩子节点
4、指针}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);/*若该节点小于当前节点，则在左子树中继续查找
5、*/elsereturnSearchBST(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为新的根结点*/e
6、lseif(strcmp(key,p->data)<0)教育资料.p->lchild=s;/*插入s为左孩子*/elsep->rchild=s;/*插入s为右孩子*/return1;}elsereturn0;/*树中已有关键字相同的结点，不再插入*/}模块3-删除节点算法如下：intDelete(BiTree*p){BiTreeq,s;if((*p)->rchild==NULL)/*右子树空则只需重接它的左子树（待删结点是叶子也走此分支)*/{q=*p;*p=(*p)->lchild;free(q);}else
7、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的右
8、子树*/elseq->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
