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

《构建一棵二叉排序树的C程序的设计[1]-(修复的)9171.pdf》由会员分享，可在线阅读，更多相关《构建一棵二叉排序树的C程序的设计[1]-(修复的)9171.pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、学号 武汉 华夏理 工学院 课 程 设 计 报 告 书 课程名称：数据结构 题 目：构建一棵二叉排序树的 C 程序的设计 系 名：信息工程学院 专业班级：软件 1152 姓 名：李天宇 指导教师:王绪梅 2016 年 6月 27日 课程设计任务书 设计题目：构建一棵二叉排序树的 C 程序的设计 设计目的 1.巩固和加深课堂所学知识、学会分析研究数据对象的特性及数据的组织方法；2.选择的合适数据的逻辑结构和存储结构以及相应操作，实现二叉排序树的基本操作；3.提高程序设计能力、加强查阅、运用资料的能力、算法分析与程序设计素质培养；设计任务（在规定的时间内完成下列任务）问题描述建立一棵二叉排序树，并

2、完成插入结点、按值查找结点位置和显示等功能。基本要求按二叉树的插入方法，形成二叉排序树 主模块给出操作菜单，用函数实现不同功能在主函数中调用 算法提示首先设定二叉树的二叉链表的存储结构：在建立二叉树时将每一个结点按左右子树的规定形成挂到树上；按二叉排序树的特点进行查找，按中序遍历的方法显示树中结点；具体要完成的任务是：A.编制完成上述问题的 C 语言程序、进行程序调试并能得出正确的运行结果。B.写出规范的课程设计报告书；时间安排：6 月 27 日-7 月 1 日 第一天 布置题目，确定任务、查找相关资料 第二天第四天 功能分析，编写程序，调试程序、运行系统；第五天 程序验收、答辩；撰写设计报告

3、。具体要求 1.课程设计报告按统一通用格式书写，具体内容如下：设计任务与要求 总体方案与说明 软件主要模块的流程图 源程序清单与注释 问题分析与解决方案（包括调式报告，即在调式过程中遇到的主要问题、解决方法及改进设想）；小结与体会 附录：源程序（必须有简单注释）使用说明 参考资料 2每位学生应独立完成各自的任务且每天至少在设计室工作半天；指 导 教 师 签 名：2016 年 6 月 25 日 教研室主任（或责任教师）签名：邱珊 2016 年 6 月 25 日 目 录 1 实验目的与目标.错误!未定义书签。2.问题分析.错误!未定义书签。3.总体设计.错误!未定义书签。4.具体设计.错误!未定义

4、书签。递归查找算法.错误!未定义书签。非递归查找算法.错误!未定义书签。插入算法.错误!未定义书签。二叉排序树的生成算法.错误!未定义书签。中序遍历算法.错误!未定义书签。删除算法.错误!未定义书签。主函数.错误!未定义书签。注意事项：.错误!未定义书签。5.运行环境.错误!未定义书签。6.上机调试.错误!未定义书签。语法错误及修改.错误!未定义书签。程序输出调整：.错误!未定义书签。时间和空间性能分析：.错误!未定义书签。7.测试结果及分析.错误!未定义书签。8.用户使用说明.错误!未定义书签。9.参考文献.错误!未定义书签。附录.错误!未定义书签。1 实验目的与目标 一、目的 数据结构课程

5、设计是学习了数据结构课后的一个综合性实践环节，是对课程学习的综合和补充。通过课程设计培养学生运用已学过的理论和技能去分析和解决实际问题的能力、加强学生的实践动手能力和创新能力。二、目标 1、结合 c 和数据结构的理论知识，按要求独立设计方案，培养独立分析和解决实际问题的能力。加强学生的实践动手能力和创新能力。2、学会查阅资料，熟悉常用算法的用途与技巧。3、认真撰写课程设计报告，培养严谨的作风和科学态度。2.问题分析 本次程序需要完成如下要求：首先输入任一组数据，使之构造成二叉排序树，并对其作中序遍历，然后输出遍历后的数据序列；其次，该二叉排序树能实现对数据（即二叉排序树的结点）的查找、插入和删

6、除等基本操作。实现本程序需要 解决以下几个问题：1、如何构造二叉排序树。2、如何通过中序遍历输出二叉排序树。3、如何实现多种查找。4、如何实现插入删除等操作。二叉排序树的定义：其左子树非空，则左子树上所有结点的值均小于根结点的值。若其右子树非空，则右子树上所有结点的值大于根结点的值。其左右子树也分别为二叉排序树。本问题的关键在于对于二叉排序树的构造。根据上述二叉排序树二叉排序树的生成需要通过插入算法来实现：输入（插入）的第一个数据即为根结点；继续插入，当插入的新结点的关键值小于根结点的值时就作为左孩子，当插入的新结点的关键值大于根结点的值时就作为右孩子；在左右子树中插入方法与整个二叉排序树相同

7、。当二叉排序树建立完成后，要插入新的数据时，要先判断已建立的二叉排序树序列中是否已有当前插入数据。因此，插入算法还要包括对数据的查找判断过程。本问题的难点在于二叉排序树的删除算法的实现。删除前，首先要进行查找，判断给出的结点是否已存在于二叉排序树之中；在删除时，为了保证删除结点后的二叉树仍为二叉排序树，要考虑各种情况，选择正确的方法。删除操作要分几种情况讨论，在后面有介绍。3.总体设计 用二叉链表作为二叉排序树的存储结构，其中key 为结点关键值，*lchlid、*rchild分别为左右孩子指针。该程序的流程图所示：开始 输入节点值 N Y 总流程图 4.具体设计 首先定义二叉排序树的数据类型

8、如下：typedef struct node 进入主菜单 输入 i I=0 I=1 I=2 I=3 I=4 退出 查找 插入 删除 显示 输入 J=1 递归查找 J=2 非递归查找 int key;删除结点*p 无左孩子，也无右孩子，则*p 的父结点对应的孩子指针置空；2.待删除结点*p 有左孩子，无右孩子，则*p 的左孩子替代自己；3.待删除结点*p 无左孩子，有右孩子，则*p 的右孩子替代自己；4.待删除结点*p 有左孩子，也有右孩子，本课程（数据结构与算法）给出了两种法：方法一：首先找到待删结点*p 的前驱结点*s，然后将*p 的左子树改为*p 父结点的左子树，而*p 的右子树改为*s

9、的右子树：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);我采用的是第二种算法。(p-key=x)查找成功 下一层p=p-lchilp=p-rchi找不到节点 开始 输入节点数 n 调用插入函结束 开始 N Y 删除算法流程图 主函数 void main()int i,j,k;Bstnode*tree,*p;syst

10、em(cls);printf(请先建立一棵二叉排序树nn);printf(输入其结点信息(输入一组正整数,当输入 0 时结束):n);tree=CreateBST();printf(中序遍历的二叉排序树:n);Inorder(tree);printf(二叉排序树的根为:%dn,tree-key);for(;)switch(i=mainmenu()case 0:exit(0);p=NULL p=s 结束 s-dataT-s=InserBST(T-)rchis=InserBST(T-)lch case 1:switch(j=searchmenu()case 1:search_Bitree(tree

11、);break;case 2:printf(n 请输入要查找的结点的值:);scanf(%d,&k);p=searchBST(tree,k);printf(n);break;行环境 Microsoft Visual C+；Microsoft Word 2010 6.上机调试 语法错误及修改 在编写程序时，很容易出现分号漏写和括号不匹配的现象，以及缺少返回值的问题。例如：在编写非递归查找算法时：Bstnode*searchBST(Bstnode*t,int x)Bstnode*p;int flag=0;p=t;while(p!=NULL)if(p-key=x)printf(找到了!);flag=

12、1;return p;break;if(xkey)p=p-lchild;else p=p-rchild;if(flag=0)printf(找不到值为%d 的结点,x);return NULL;结果编译时出现了警告 warning:searchBST :not all control paths return a value 然后我做了改动，改后程序如下：Bstnode*searchBST(Bstnode*t,int x)Bstnode*p;int flag=0;p=t;while(p!=NULL)if(p-key=x)printf(该结点值存在!);flag=1;break;if(xkey)p

13、=p-lchild;else p=p-rchild;if(flag=0)printf(找不到值为%d 的结点!,x);p=NULL;return p;将 NULL 值赋给指针 p，再在程序结尾返回 p，此时，编译结果就正确了！程序输出调整：在递归查找算法(Bsearch)中针对查找结果如何,没有用明确的输出函数表示出来。于是我添加了一个递归查找模块如下：search_Bitree(Bstnode*t)int s;Bstnode*p;printf(n 请输入要查找的结点的值:);scanf(%d,&s);if(s!=0)p=Bsearch(t,s);if(p=NULL)printf(该结点值不存

14、在!n);else printf(找不到值为%d 的结点!n,s);这样主函数便可直接调用该函数来实现查找过程。时间和空间性能分析：由于二叉排序树的中序遍历序列为一个递增的有序序列，这样可以将二叉排序树看作是一个有序表。其查找过程：若查找成功，则是从根结点出发走了一条从根到某个结点的路径；若查找不成功，则是从根结点出发走了一条从根到某个叶子结点的路径。和关键字比较次数不超过二叉排序树的深度。二叉排序树的平均查找长度与其形态有关。最坏情况是具有 n 个结点的单支树，其平均查找长度与顺序查找相同，为（n+1）/2；即平均查找长度的数量级为 O（n）。在最好情况下，二叉排序树形态均匀，它的平均查找长

15、度与二分查找相似，大约是 log2n，其平均查找长度的数量级为 O（log2n）。1、经验与体会：由于该设计问题是对数据结构与算法课程中二叉树章节的灵活应用，所以课本给了我很大的帮助，结合所学知识以及对二叉排序树的理解，来编写该程序。7.测试结果及分析 1、建立如图（a）的二叉排序树，输入的数据依次为：45 24 53 12 28 90 0（0为输入结束符），屏幕（图（1）上显示的是横置的二叉树 45 24 53 12 28 90 45 24 53 12 28 90 图（a）图（b）图（1）2、选择方框中给定的项目（输入 04 中任意数）。若输入错误会有提示，可以重新输入。图（2）3、输入 1

16、，则出现查找菜单。选择查找方法。图（3）4、在查找菜单选 1，则进行递归查找。图（4）5、同理，若选择 2，则进行非递归查找。查找的值存在与否都会有显示。图（5）6、选 2，则进行插入操作。插入关键值为 13 的结点后，显示如图（6），即插入 13 后的横置的二叉排序树（图（c）图（d）。图（c）图（d）45 24 53 12 28 90 13 45 24 53 12 28 90 13 图（6）1、选 3，进行删除操作。删除关键值为 24 的结点后，显示如图（7），即删除 24 后的横置的二叉排序树（图（e）图（f）、图（e）图（f）45 13 53 12 28 90 45 13 53 12

17、28 90 图（7）2、选 4 则显示详细信息。如图（8）所示，按中序遍历（从小到大）依次输出，并显示每个结点的孩子情况，最后打印出横置的二叉排序树。图（8）3、选 0 则退出程序。图（9）8.用户使用说明 用户可以根据本程序运行过程中出现的提示性语句来进行操作。要注意括号中的提示，若没有按照提示输入的话，程序可能将无法继续进行下去。例如开始输入数据时直到输入 0时才算结束输入，从而进行下一步操作。在遇到选项时，选择错误会给你重新选择的机会。提示：进行一系列插入删除等操作后，可以选择显示项来显示最后的二叉排序树状态(二叉排序树显示的是中序遍历后的序列)。9.参考文献(1)王昆仑.李红.数据结构

18、与算法.北京：中国铁道出版社，(2)王昆仑.李红.数据结构与算法试验指导，2009(3)谭浩强.c 程序设计.北京：清华大学出版社，(4)严蔚敏.数据结构：语言版.北京：清华大学出版社，2002(5)耿国华.等.数据结构:用 c 语言描述.北京：高等教育出版社，2004 设计过程中质疑（或答辩）记载：1 二叉树运行过程中用了什么排序 答：运用了中序遍历排序。2中序遍历排序是怎样的 答：先遍历左孩子，再遍历父结点，最后遍历右孩子。3.在设计过程中遇到过那些困难 答:在编程序的过程的程序一直不能正确运行，最后发现函数的调用出现了问题。最后通过修改解决。指导教师评语：签名：2016 年 7 月 5

19、日 附录#include#include#include#define endflag 0 叉排序树-查找n);printf(ttt2.二叉排序树-插入n);printf(ttt3.二叉排序树-删除n);printf(ttt4.二叉排序树-显示n);printf(ttt0.退出该程序 n);printf(ttt n);printf(tttn);printf(ttt*n);printf(nnn);do if(flag=0)printf(!您的输入有误,请重新输入n);printf(请选择您要进行的项目:);scanf(%d,&choice);flag=0;while(choice4);retur

20、n choice;法 1-递归查找n);printf(ttt2.方法 2-非递归查找n);printf(ttt n);printf(tttn);printf(ttt*n);printf(nnn);do if(flag=0)printf(!您的输入有误,请重新输入n);printf(请选择查找方法:);scanf(%d,&choice);flag=0;while(choice!=1&choice!=2);return choice;/主函数 void main()int i,j,k;Bstnode*tree,*p;system(cls);printf(请先建立一棵二叉排序树nn);printf(

21、输入其结点信息(输入一组正整数,当输入 0 时结束):n);tree=CreateBST();printf(中序遍历的二叉排序树:n);Inorder(tree);printf(二叉排序树的根为:%dn,tree-key);for(;)switch(i=mainmenu()case 0:exit(0);case 1:switch(j=searchmenu()case 1:search_Bitree(tree);break;case 2:printf(n 请输入要查找的结点的值:);scanf(%d,&k);p=searchBST(tree,k);printf(n);break;/default:printf(输入有误!);break;case 2:tree=insert_Bitree(tree);break;case 3:tree=delete_Bitree(tree);break;case 4:printf(n);printf(二叉排序树的根为:%dn,tree-key);printf(中序遍历后的序列为:n);print_Bitree(tree);printf(中序遍历的二叉排序树:n);Inorder(tree);printf(n);break;/default:printf(输入有误!);