构建一棵二叉排序树的C程序的设计1-(修复的)

构建一棵二叉排序树的C程序的设计[1]-(修复的)构建一棵二叉排序树的C程序的设计[1]-(修复的)构建一棵二叉排序树的C程序的设计[1]-(修复的)资料仅供参考文件编号：2022年4月构建一棵二叉排序树的C程序的设计[1]-(修复的)版本号：A修改号：1页次：1.0审核：批准:发布日期：学号武汉华夏理工学院课程设计报告书课程名称：数据结构题目：构建一棵二叉排序树的C程序的设计系名：信息工程学院专业班级：软件1152姓名：李天宇指导教师:王绪梅2016年6月27日课程设计任务书设计题目：构建一棵二叉排序树的C程序的设计设计目的1.巩固和加深课堂所学知识、学会分析研究数据对象的特性及数据的组织方法；2.选择的合适数据的逻辑结构和存储结构以及相应操作，实现二叉排序树的基本操作；3.提高程序设计能力、加强查阅、运用资料的能力、算法分析与程序设计素质培养；设计任务（在规定的时间内完成下列任务） 〔问题描述〕建立一棵二叉排序树，并完成插入结点、按值查找结点位置和显示等功能。〔基本要求〕按二叉树的插入方法，形成二叉排序树主模块给出操作菜单，用函数实现不同功能在主函数中调用〔算法提示〕首先设定二叉树的二叉链表的存储结构：在建立二叉树时将每一个结点按左右子树的规定形成挂到树上；按二叉排序树的特点进行查找，按中序遍历的方法显示树中结点；具体要完成的任务是：A.编制完成上述问题的C语言程序、进行程序调试并能得出正确的运行结果。B.写出规范的课程设计报告书；时间安排：6月27日7月1日第一天布置题目，确定任务、查找相关资料第二天～第四天功能分析，编写程序，调试程序、运行系统；第五天程序验收、答辩；撰写设计报告。具体要求1.课程设计报告按统一通用格式书写，具体内容如下：①设计任务与要求②总体方案与说明③软件主要模块的流程图④源程序清单与注释⑤问题分析与解决方案（包括调式报告，即在调式过程中遇到的主要问题、解决方法及改进设想）；⑥小结与体会附录：①源程序（必须有简单注释）②使用说明③参考资料2．每位学生应独立完成各自的任务且每天至少在设计室工作半天；指导教师签名：2016年6月25日教研室主任（或责任教师）签名：邱珊2016年6月25日目录1实验目的与目标 32.问题分析 33.总体设计 44.具体设计 5递归查找算法 5非递归查找算法 6插入算法 7二叉排序树的生成算法 8中序遍历算法 9删除算法 9主函数 10注意事项： 115.运行环境 116.上机调试 11语法错误及修改 11程序输出调整： 13时间和空间性能分析： 137.测试结果及分析 148.用户使用说明 209.参考文献 20附录 211实验目的与目标一、目的数据结构课程设计是学习了数据结构课后的一个综合性实践环节，是对课程学习的综合和补充。通过课程设计培养学生运用已学过的理论和技能去分析和解决实际问题的能力、加强学生的实践动手能力和创新能力。二、目标1、结合c和数据结构的理论知识，按要求独立设计方案，培养独立分析和解决实际问题的能力。加强学生的实践动手能力和创新能力。2、学会查阅资料，熟悉常用算法的用途与技巧。3、认真撰写课程设计报告，培养严谨的作风和科学态度。2.问题分析本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删除等基本操作。实现本程序需要解决以下几个问题：如何构造二叉排序树。如何通过中序遍历输出二叉排序树。如何实现多种查找。如何实现插入删除等操作。二叉排序树的定义：其左子树非空，则左子树上所有结点的值均小于根结点的值。若其右子树非空，则右子树上所有结点的值大于根结点的值。其左右子树也分别为二叉排序树。本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断过程。本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确的方法。删除操作要分几种情况讨论，在后面有介绍。3.总体设计用二叉链表作为二叉排序树的存储结构，其中key为结点关键值，*lchlid、*rchild分别为左右孩子指针。该程序的流程图所示：节点是否为0输入节点值开始节点是否为0输入节点值开始 N非递归查找J=22递归查找输入J=1显示删除插入查找退出I=2I=4I=3I=1I=0 输入i进入主菜单Y非递归查找J=22递归查找输入J=1显示删除插入查找退出I=2I=4I=3I=1I=0 输入i进入主菜单总流程图4.具体设计首先定义二叉排序树的数据类型如下：typedefstructnode{ intkey;p=p->lchild;(p->key==x)下一层p=p->rchild找不到节点查找成功开始输入节点数n调用插入函数结束删除结点*p无左孩子，也无右孩子，则*p的父结点对应的孩子指针置空；p=p->lchild;(p->key==x)下一层p=p->rchild找不到节点查找成功开始输入节点数n调用插入函数结束2.待删除结点*p有左孩子，无右孩子，则*p的左孩子替代自己；3.待删除结点*p无左孩子，有右孩子，则*p的右孩子替代自己；4.待删除结点*p有左孩子，也有右孩子，本课程（数据结构与算法）给出了两种法：方法一：首先找到待删结点*p的前驱结点*s，然后将*p的左子树改为*p父结点的左子树，而*p的右子树改为*s的右子树：f->lchild=p->lchild;s->rchild=p->rchild;free(p);方法二：首先找到待删结点*p的前驱结点*s，然后用结点*s的值替代结点*p的值，再将结点*s删除，结点*s的原左子树改为*s的双亲结点*q的右子树：p->data=s->data;q->rchild=s->lchild;free(s);我采用的是第二种算法。开始开始s-〉data〉T-〉datap=NULL Ns-〉data〉T-〉datap=NULL Yp=sp=ss=InserBST(T->)lchilds=InserBST(T->)lchilds=InserBST(T->)rchild结束结束删除算法流程图主函数voidmain(){ inti,j,k; Bstnode*tree,*p;system("cls"); printf("★☆★☆★请先建立一棵二叉排序树★☆★☆★\n\n"); printf("输入其结点信息(输入一组正整数,当输入0时结束):\n");tree=CreateBST();printf("中序遍历的二叉排序树:\n"); Inorder(tree);printf("二叉排序树的根为:%d\n",tree->key);for(;;) switch(i=mainmenu()) { case0:exit(0); case1:switch(j=searchmenu()) { case1:search_Bitree(tree);break; case2:printf("\n请输入要查找的结点的值:"); scanf("%d",&k);p=searchBST(tree,k); printf("\n"); break; 行环境MicrosoftVisualC++；MicrosoftWord20106.上机调试语法错误及修改在编写程序时，很容易出现分号漏写和括号不匹配的现象，以及缺少返回值的问题。例如：在编写非递归查找算法时：Bstnode*searchBST(Bstnode*t,intx){ Bstnode*p;intflag=0; p=t; while(p!=NULL) { if(p->key==x) { printf("找到了!");flag=1; returnp;break; } if(x<p->key) p=p->lchild; else p=p->rchild; } if(flag==0) { printf("找不到值为%d的结点",x); returnNULL; }}结果编译时出现了警告warning:'searchBST':notallcontrolpathsreturnavalue然后我做了改动，改后程序如下：Bstnode*searchBST(Bstnode*t,intx){ Bstnode*p;intflag=0;p=t; while(p!=NULL) { if(p->key==x) { printf("该结点值存在!");flag=1; break; } if(x<p->key) p=p->lchild; else p=p->rchild; } if(flag==0) { printf("找不到值为%d的结点!",x); p=NULL; } returnp;}将NULL值赋给指针p，再在程序结尾返回p，此时，编译结果就正确了！程序输出调整：在递归查找算法(Bsearch)中针对查找结果如何,没有用明确的输出函数表示出来。于是我添加了一个递归查找模块如下：search_Bitree(Bstnode*t){ ints; Bstnode*p; printf("\n请输入要查找的结点的值:"); scanf("%d",&s);if(s!=0) {p=Bsearch(t,s); if(p==NULL) printf("该结点值不存在!\n"); elseprintf("找不到值为%d的结点!\n",s); }}这样主函数便可直接调用该函数来实现查找过程。时间和空间性能分析：由于二叉排序树的中序遍历序列为一个递增的有序序列，这样可以将二叉排序树看作是一个有序表。其查找过程：若查找成功，则是从根结点出发走了一条从根到某个结点的路径；若查找不成功，则是从根结点出发走了一条从根到某个叶子结点的路径。和关键字比较次数不超过二叉排序树的深度。二叉排序树的平均查找长度与其形态有关。最坏情况是具有n个结点的单支树，其平均查找长度与顺序查找相同，为（n+1）/2；即平均查找长度的数量级为O（n）。在最好情况下，二叉排序树形态均匀，它的平均查找长度与二分查找相似，大约是log2n，其平均查找长度的数量级为O（log2n）。经验与体会：由于该设计问题是对数据结构与算法课程中二叉树章节的灵活应用，所以课本给了我很大的帮助，结合所学知识以及对二叉排序树的理解，来编写该程序。7.测试结果及分析4524534524531228904524452453122890图（a）图（b）图（1）2、选择方框中给定的项目（输入0~4中任意数）。若输入错误会有提示，可以重新输入。图（2）输入1，则出现查找菜单。选择查找方法。图（3）4、在查找菜单选1，则进行递归查找。图（4）5、同理，若选择2，则进行非递归查找。查找的值存在与否都会有显示。图（5）6、选2，则进行插入操作。插入关键值为13的结点后，显示如图（6），即插入13后的横置的二叉排序树（图（c）——图（d））。45452453122890134545245312289013图（c）图（d）图（6）选3，进行删除操作。删除关键值为24的结点后，显示如图（7），即删除24后的横置的二叉排序树（图（e）——图（f））、4545135312289045451353122890图（e）图（f）图（7）选4则显示详细信息。如图（8）所示，按中序遍历（从小到大）依次输出，并显示每个结点的孩子情况，最后打印出横置的二叉排序树。图（8）选0则退出程序。图（9）8.用户使用说明用户可以根据本程序运行过程中出现的提示性语句来进行操作。要注意括号中的提示，若没有按照提示输入的话，程序可能将无法继续进行下去。例如开始输入数据时直到输入0时才算结束输入，从而进行下一步操作。在遇到选项时，选择错误会给你重新选择的机会。提示：进行一系列插入删除等操作后，可以选择显示项来显示最后的二叉排序树状态(二叉排序树显示的是中序遍历后的序列)。9.参考文献(1)王昆仑.李红.数据结构与算法.北京：中国铁道出版社，(2)王昆仑.李红.数据结构与算法试验指导，2009(3)谭浩强.c程序设计.北京：清华大学出版社，(4)严蔚敏.数据结构：ｃ语言版.北京：清华大学出版社，2002(5)耿国华.等.数据结构:用c语言描述.北京：高等教育出版社，2004设计过程中质疑（或答辩）记载：二叉树运行过程中用了什么排序答：运用了中序遍历排序。2．中序遍历排序是怎样的答：先遍历左孩子，再遍历父结点，最后遍历右孩子。3.在设计过程中遇到过那些困难答:在编程序的过程的程序一直不能正确运行，最后发现函数的调用出现了问题。最后通过修改解决。指导教师评语：签名：2016年7月5日附录#include""#include""#include""#defineendflag0叉排序树查找┃┇\n"); printf("\t\t\t┇┃2.二叉排序树插入┃┇\n");printf("\t\t\t┇┃3.二叉排序树删除┃┇\n");printf("\t\t\t┇┃4.二叉排序树显示┃┇\n");printf("\t\t\t┇┃0.退出该程序┃┇\n"); printf("\t\t\t┇┃┃┇\n"); printf("\t\t\t┇┗┅┅┅┅┅┅┅┅┅┅┅┛┇\n"); printf("\t\t\t┗**************************┛\n");printf("\n\n\n"); do{ if(flag==0) printf("!您的输入有误,请重新输入\n");printf("请选择您要进行的项目:");scanf("%d",&choice); flag=0; }while(choice<0||choice>4); returnchoice;}法1递归查找┃┇\n"); printf("\t\t\t┇┃2.方法2非递归查找┃┇\n"); printf("\t\t\t┇┃┃┇\n"); printf("\t\t\t┇┗┅┅┅┅┅┅┅┅┅┅┅┛┇\n"); printf("\t\t\t┗**************************┛\n");printf("\n\n\n");do{ if(flag==0) printf("!您的输入有误,请重新输入\n");printf("请选择查找方法:");scanf("%d",&choice); flag=0; }while(choice!=1&&choic