软件课程设计报告二叉树的查找

华中科技大学光电学院华中科技大学软件课程设计报告课程设计题目：二叉树的查找院（系）：光电子科学与工程学院专业班：光电1001学号：U201013352姓名：谭天弈目录1.软件设计 21.1 系统分析 21.1.1需求分析 2 1.1.2函数及文件分析 21.2系统设计 21.2.1系统模块设计 21.2.1.1代码模块化 21.2.1.2功能模块化 41.2.1.3流程模块化 61.2.2函数设计 61.2.3系统流程设计 71.2.3.1主函数流程设计 71.2.3.2create_btree流程设计 101.2.3.3search_btree流程设计 111.2.3.4print_btree流程设计 121.2.4用户界面设计 121.2.5容错性设计 132.软件测试 142.1调试过程 142.2测试用例及运行结果 143.任务的其他要求3.1源代码的注释 213.2源代码的运行结果 233.3设计心得与体会 244.参考文献 24附录：二叉树综合应用程序源码 251软件设计1.1系统分析1.1.1需求分析本二叉树综合应用程序集合了大部分二叉树的相关功能。主要包含了二叉树的建立，二叉树的检索，二叉树的遍历，二叉树的打印，以及计算二叉树的相关参数，删除二叉树的部分节点等功能。本着用户友好的原则，每一项功能都设计了相应的菜单，并且每一个功能在主函数中都对应了一个循环，方便客户使用，而不是调试程序时使用的流水线式的运行过程。二叉树可以键盘输入，也可以使用内置的二叉树进行测试。主函数中每一级菜单和每一个功能菜单都是用一个while(1)循环包裹起来的，具有很强的独立性。并且把一些小的功能做成相应的函数，以缩短代码。并且每一个函数都相对独立，其中void deltree(struct tree *r)和struct tree *binary_search(struct tree *point,char node,char *postion)设计了程序接口，方便其它子函数调用。并且在发现bug时便于更改。做到，可持续，有余地。1.1.2函数及文件分析为了尽量的缩短main()函数，把能设计成子函数的功能都设计成了子函数。包括常用的显示和分割线都写成了re1()和re2()函数。由于每个大的功能子函数都只调用了一次，所以不考虑进行文件设计。子函数被分成了3个部分，第一部分为题目中给出的3个函数，具备了建立，打印，检索3个基本功能。第二部分为功能部分，主要是4种遍历，求各种特征参数，以及用凹表，括号法打印二叉树，和两种删除（删除方法暂时不太承受）。第三个部分为用户函数，除了re1，re2和err这三个常用函数，其它全部用c_开头。为了保证屏幕的整洁，在每一个菜单函数的前面都加上了一个清屏函数。理论上，在子函数也复杂，主函数调用不可能简单的完成，例如对create_btree的调用，需要在main中进行循环和递归。所以应当设计业务子函数，让主函数可以直接调用。但考虑到实际是大多数子函数可以在主函数中直接得出结果，并且在re1，re2，err三个函数的帮助下就可以很友好地显示。再加上一旦设计了业务子函数，就会使整个调用过程更加复杂，每一个业务子函数都要调用其它子函数。故不设计业务函数，少数不能在主函数中直接运行得出结果的子函数，类似create_btree的处理。系统函数的调用，主要调用的c中的函数，混杂了少数的c+函数如new函数等，所以在编译运行时需要一些头文件如iostream.h，如若编译器不具备这些头函数可能导致程序不能运行。所以如果用c语言运行请将new改成malloc函数。1.2 系统设计1.2.1系统模块设计1.2.1.1代码模块化将代码分成几个区域来书写不同的内容，第一个区域为代码的头部，包括了头文件和该程序的核心“结构体”。 第二个部分，为函数声明，包括了两个全局变量，并说明函数功能：第三部分为主函数部分，包含了主要循环过程，和容错性设计： 第四部分为功能子函数的定义，都用编号标好，并加上简单注释，方便后期修改和调用，如：第五部分为界面子函数的定义，如：1.2.1.2功能模块化二叉树综合应用程序二叉树的建立版本信息遍历层次后序中序先序凹表打印二叉树括号法打印二叉树求参数最大最小枝长叶子树结点数树深度删除结点删除结点及子树仅删除结点模块1：二叉树的建立模块2：二叉树相关操作的功能选择模块3：遍历模块4：求参数模块5：删除节点1.2.1.3流程模块化通过嵌套循环的方法进行，因为需要用到break进行返回，故不使用switch语句，直接在if中进行循环，如图：1.2.2函数设计对每一个功能设计一个子函数，如输入函数create_btree，括号法输入函数create_btree2，层次遍历函数levelorder，求结点个数函数nodenum，等。并且对每一个菜单项设计了一个子函数如主菜单c_first_menu，遍历菜单c_order_menu。常用输出函数re1，re2，报错函数err等。子函数表：struct tree *create_btree(struct tree *root,struct tree *r,char info); /1建立一棵二叉树struct tree *search_btree(struct tree *root,char key); /2检索key函数void print_btree(struct tree *r,int l); /3将这个二叉树打印出来,中序/*二叉树的遍历*/void preorder(struct tree *r);/4先序void inorder(struct tree *r);/5中序void postorder(struct tree *r);/6后序void levelorder(struct tree *r);/7层次遍历/*其他功能*/void pdisptree(struct tree *r);/8以凹入法显示二叉树,先序int treedepth(struct tree *r);/9求二叉树的深度void nodenum(struct tree *r);/10二叉树结点个数void leafnum(struct tree *r);/11二叉树叶子结点void create_btree2(struct tree *&r,char *str);/12用括号法建立一个二叉树,入参r为根节点，str为其他节点void print_btree2(struct tree *r); /13括号法显示二叉树void maxminleaf(struct tree *r,int &m,int &n);/14计算二叉树的最小枝长和最大枝长struct tree *binary_search(struct tree *point,char node,char *postion);/15查找并记录父节点的值，16中调用struct tree *deletenode(struct tree *root,char node);/16删除一个节点，调用15void deltree(struct tree *r);/17递归删除void search_deltree(struct tree *r,char x);/18查找并删除某节点及其子树，调用17/*用户界面功能*/void c_first_menu();/19一级菜单void c_information();/20版本信息void c_sec_menu();/21二级菜单void re1();/22显示结果void re2();/23分割线void c_order_menu();/24遍历菜单void err();/25报错void c_num_menu();/26参数菜单void c_del_menu();/27删除菜单1.2.3系统流程设计1.2.3.1主函数流程设计由于主函数流程过于复杂，这里将主要的循环及选择画出来，细节部分忽略。注：如看不清晰，请调至150%观看。接下一面NYYNNYCho1=0Exit(0)Cho1=1括号法输入Error图1 c_first_menu菜单一的循环c_first_menu()Scanf cho1NY退出YNYNNNYYYYYNYNYNYNNYc_sec_menu()Scanf cho2Cho2=0Exit(0)Cho2=1c_order_menu()Scanf cho3Cho3=0Exit(0)四种遍历ErrorCho2=2pdisptreeCho2=3print_btree2Cho2=4c_num_menu ()Scanf cho4Cho4=0Exit(0)参数计算ErrorCho2=5Yc_del_menu() ()Scanf cho5Cho5=0Exit(0)删除节点ErrorCho2=6YErrorScanf choCh3=0返回上一面图2 c_sec_menu菜单二的循环1.2.3.2create_btree流程设计子函数声明为struct tree *create_btree(struct tree *root,struct tree *r,char info);用了迭代的思想进行流程设计。注：没有指向的框图为迭代时的函数入参。图3create_btree流程NNYNYR=0r=new (struct tree)R=0Return 0初始化Root=0Y根节点infoinfoYroot - left=rroot - right=rReturn rinfo infoinfo=r-info(r,r-left,info)(r,r-right,info)1.2.3.3search_btree流程设计YNNN！rootYReturn rootkeyinfoYroot=root-leftroot=root-rightRoot=0Root!=0Return rootYYroot-info!=key图4 search_btree流程1.2.3.4print_btree流程设计NR=0Yreturn(r-left,l+1)iinfo(r-right,l+1)图5print_btree流程1.2.4用户界面设计以“有好的交互，清晰的提示，简单明了的输出”为原则，进行控制台界面设计。比如用括号法输入时，给出用户示例：printf(示例：A(B(D,E(H,I),C(G):n);在输出时为了界面的整洁，设置了专门的输出函数：void re1()printf(n);printf(显示结果如下：n);printf(-n);void re2()printf(n);printf(-n);getchar();这样的输出就会非常简洁。如图：另外每个菜单子函数的前面都有清屏函数system(“cls”)这样可以保持界面的整洁，使要操作的功能菜单在控制台的最上方。另外，为了保证程序的可用性，要求每一级菜单和功能都有直接退出和返回上一级的能力，如图所示：1.2.5容错性设计为了防止用户输入错误，进行了容错性设计。每一个输入功能，如cho1，cho2的输入都用一个while(1)永真循环来包裹，当用户输入的数据错误时返回输入部分。专门设计了报错函数err，其中包含的system(“pause”)可以是屏幕内容暂缓。void err()printf(n);printf(输入错误，请重新输入n);getchar();2.软件测试2.1调试过程用如下函数调试子函数。void main () char;int;string;/变量声明，初始化。do printf(Enter a letter:); gets(s);if (!root)root=create_btree(root,root,*s);elsecreate_btree(root,root,*s);while (*s) ;print_btree(root,0);debugfunction();/被调试的函数将每一个子函数带入调试函数中，编译，组件，运行。出现的bug很少。一多半是由于printf中缺少n或者缺少system(“puase”),system(“cls”)导致显示结果不完美。比较关键的bug是由于nodenum(struct tree *r);void leafnum(struct tree *r);函数的返回类型原本是int型，且入参为一个int型指针，导致返回的数据有问题，最后设置了两个全局count1,count2来记录结点数和叶子树。返回类型也改成了void。最大的问题在于，creat_btree函数调用时，入参*s用gets函数获得，导致输入流的最后加入了一个回车符，也就是二叉树中多了一个异常的数据，所以后面的对二叉树的处理都出现了偏差。比如求最大最小枝长时，包含较小数据的枝长值会多出1，这正是多出的回车符导致的。这个问题目前没想到解决的办法，所以用另一种输入方法既括号法来代替。但括号法在输入大批数据时不太方便，此问题有待日后解决。另外，在对结点进行删除时，成功率不能达到百分之一百，因为有些结点一旦被删除会导致整个二叉树不再为二叉树，所以对指定的结点是有特殊要求的。2.2测试用例及运行结果测试环境：系统：win7家庭普通版Cpu：测试所用的二叉树如下：a(g(u(o,p(t(e,c),d(q,w),n(f(i(h(z(e,d),b),t(f,k),s),a),v(l,d),u(o,p(t(e,c),d(q,w),n(f(i(h(z(p,y),b),t(x,z),s),m),v(l,d)该二叉树为对称的，便于检查。1括号法输入数据2回车查看从左向右显示结果，及左边为根节点，向右为子树3继续回车选择界面4选择功能1，再选先序遍历5遍历结果，正确6中序遍历7层次遍历8凹表打印9括号法显示10求相关参数11深度12结点数13叶子树14最大最小枝长15删除结点16仅删除节点t根据凹表打印 前序遍历到的第一个节点t被删除17删除t的节点及子树18返回上一级结果：输入1返回19退出程序直接退出了。测试结果非常理想，鉴于第二种建树方法在调试时的bug，故不对其进行测试。3.任务的其他要求3.1源代码的注释#include#includestruct tree char info; /数据元素 struct tree *left,*right; /数的左指针域和右指针域 ;struct tree *create_btree(struct tree *root,struct tree *r,char info); /函数声明：建立一棵二叉树struct tree *search_btree(struct tree *root,char key); /函数声明：检索key函数void print_btree(struct tree *r,int l); /函数声明：将这个二叉树打印出来void main () char s100,c,key= ;/声明一个字符串，两个字符变量待用 struct tree *root=0 ; do printf(Enter a letter:); gets(s);/从控制台得到字符串sif (!root)root=create_btree(root,root,*s);/当根节点为空的时候，从根节点开始建立elsecreate_btree(root,root,*s);/否则添加新的子树 while (*s) ;/当不在输入时，建立完成，按回车结束print_btree(root,0);/将建立的二叉树打印出来key=1;/初始化keywhile ( key)printf(Enter a key to find:);scanf(%s,&c);root=search_btree(root,c);printf(press to continuen);/检索key的值 /* Btree.C 结束 */ /*子函数1*/struct tree *create_btree(struct tree *root,struct tree *r,char info) if (r =0 ) r=new (struct tree);/ 申请一块内存，在c中用：malloc(sizeof()if ( r = 0) printf(Out of memoryn); return 0 ; /如果r=0则申请内存失败 直接退出程序r-left= 0; r-right=0; r-info=info;/将r的左右节点设置为空 数据data为infoif (root) if(infoinfo) root - left=r;/要插入的data比根节点中data小 则将其放在左枝else root - right=r;/当root不为空时 创造一个子节点else r-right = 0; r-left = 0; /当root为空时 创造一个根节点return r;if (info info)create_btree(r,r-left,info);if(info=r-info)create_btree(r,r-right,info);/r不为空时，当data小于r中的data则创造左子树，反之创造右子树 /*子函数2*/struct tree *search_btree(struct tree *root,char key) if (!root) printf(Emptu btreen); return root; /当root为空时，提示空树 while(root-info!=key) if(keyinfo) root=root-left;elseroot=root-right;/要检索的值比当前结点的值小，到左子树中继续检索，反之同理if(root=0) printf(Search Failuren);break ; /root为空 提示检索失败 并退出循环 /检索到key时退出循环if (root !=0)printf(Successful searchn key=%cn,root-info);/当检索到的值不为空时，提示检索成功，并将检索到的key值打印return root ;/返回检索值 /*子函数3*/void print_btree(struct tree *r,int l) int i;if (r = 0) return ;/当r为空树时 跳出print_btree(r-left,l+1);/对左子树使用打印函数for(i=0;iinfo);print_btree(r-right,l+1);/将该节点右子树以及右子树的右子树等全部打印出来，并对其中所有左子树使用打印函数3.2源代码的运行结果查找 6 成功查找a 失败3.3设计心得与体会编程是一件很枯燥很无聊的事情，但是出于完成作业，得到学分的压力，还必须强破自己坚持下去，按照老师所说的模块化思想，分部分的进行编写。而且编程是一件高精度、模范化的事情，稍有疏乎都会影响全局，也可能因为某一处的小的错误而导致整个程序的无法运行。所以认真仔细就是非常重要的了。开始的时候真的感觉编程是一件很无聊的事情，不过当一个程序运行成功的时候那种喜悦是无法言语的，那种成就感是无法比拟的。又经过几天的努力，终于把程序完成了，尽管程序还是有很多错误和漏洞，不过还是很高兴的。无论如何是自己的劳动成果，是自己经过努力得到的成绩，同时也是学习C语言的一次实践作业，自己进步的证明。通过这次课程设计，使我对C语言有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，我也发现我的好多不足之处，首先是自己在指法上还不行，经常按错字母，通过学习也有所改进；再有对C语言的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C语言中经常出现的错误也不了解，通过实践的学习，我认识到学好计算机要重视实践操作，不仅仅是学习C语言，还是其它的语言，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。并且，更加深入的，我知道了如何设计用户友好程序，和具有强大容错性的程序。也从深层次的理解了子函数，和文件存在的意义。在课程设计过程中，收获知识，提高能力的同时，我也学到了很多人生的哲理，懂得怎么样去制定计划，怎么样去实现这个计划，并掌握了在执行过程中怎么样去克服心理上的不良情绪。因此在以后的生活和学习的过程中，我一定会把课程设计的精神带到生活中，不畏艰难，勇往直前！4.参考文献1c语言程序设计2c语言实战100例3数据结构4博客园算法频道附录：二叉树综合应用程序源码：#include #include #include #include #define TREEMAX 100struct tree char info; /数据元素 struct tree *left,*right; /数的左指针域和右指针域 ;/-int count1 = 0;/全局变量，用来记录结点个数int count2 = 0;/全局变量，用来记录叶子节点数/*函数声明*/*二叉树的基本功能*/struct tree *create_btree(struct tree *root,struct tree *r,char info); /1建立一棵二叉树struct tree *search_btree(struct tree *root,char key); /2检索key函数void print_btree(struct tree *r,int l); /3将这个二叉树打印出来,中序/*二叉树的遍历*/void preorder(struct tree *r);/4先序void inorder(struct tree *r);/5中序void postorder(struct tree *r);/6后序void levelorder(struct tree *r);/7层次遍历/*其他功能*/void pdisptree(struct tree *r);/8以凹入法显示二叉树,先序int treedepth(struct tree *r);/9求二叉树的深度void nodenum(struct tree *r);/10二叉树结点个数void leafnum(struct tree *r);/11二叉树叶子结点void create_btree2(struct tree *&r,char *str);/12用括号法建立一个二叉树,入参r为根节点，str为其他节点void print_btree2(struct tree *r); /13括号法显示二叉树void maxminleaf(struct tree *r,int &m,int &n);/14计算二叉树的最小枝长和最大枝长struct tree *binary_search(struct tree *point,char node,char *postion);/15查找并记录父节点的值，16中调用struct tree *deletenode(struct tree *root,char node);/16删除一个节点，调用15void deltree(struct tree *r);/17递归删除void search_deltree(struct tree *r,char x);/18查找并删除某节点及其子树，调用17/*用户界面功能*/void c_first_menu();/19一级菜单void c_information();/20版本信息void c_sec_menu();/21二级菜单void re1();/22显示结果void re2();/23分割线void c_order_menu();/24遍历菜单void err();/25报错void c_num_menu();/26参数菜单void c_del_menu();/27删除菜单/-void main () while(1)char str100,s100,node;/s为输入数组，node为要删去的结点 struct tree *root=0 ; intcho,cho1,cho2,cho3,cho4,cho5;int dep,max,min;/深度，最大枝长，最小枝长while(1)c_first_menu();cho1 = 0;scanf(%d%*c,&cho1);/用%*c来储存回车符if(cho1 = 0)exit(0);else if(cho1 = 1)/括号法输入二叉树printf(请输入你想建立的二叉树n);printf(示例：A(B(D,E(H,I),C(G):n);gets(str);create_btree2(root,str);re1();print_btree(root,0);re2();break;else if(cho1 = 2)do printf(Enter a letter:); gets(s);if (!root)root=create_btree(root,root,*s);elsecreate_btree(root,root,*s);while (*s) ;re1();print_btree(root,0);re2();/将建立的二叉树打印出来break;else if(cho1 = 3)c_information();elseerr();while(1)c_sec_menu();cho2 = 0;scanf(%d%*c,&cho2);if(cho2 = 0)exit(0);else if(cho2 = 1)c_order_menu();cho3 = 0;scanf(%d%*c,&cho3);while(1)if(cho3 = 0)exit(0);else if(cho3 = 1)re1();preorder(root);re2();break;else if(cho3 = 2)re1();inorder(root);re2();break;else if(cho3 = 3)re1();postorder(root);re2();break;else if(cho3 = 4)re1();levelorder(root);re2();break;else if(cho3 = 5)break;elseerr();else if(cho2 = 2)re1();pdisptree(root);re2();else if(cho2 = 3)re1();print_btree2(root);re2();else if(cho2 = 4)c_num_menu();cho4 = 0;scanf(%d%*c,&cho4);while(1)if(cho4 = 0)exit(0);else if(cho4 = 1)dep = treedepth(root);re1();printf(深度为：%d,dep);re2();break;else if(cho4 = 2)nodenum(root);re1();printf(结点个数为:%d,count1);re2();break;else if(cho4 = 3)leafnum(root);re1();printf(叶子个数为:%d,count2);re2();break;else if(cho4 = 4)maxminleaf(root,max,min);re1();printf(最大枝长=%dn,max);printf(最小枝长=%dn,min);re2();break;else if(cho4 = 5)break;elseerr();else if(cho2 = 5)c_del_menu();cho5 = 0;scanf(%d%*c,&cho5);while(1)if(cho5 = 0)exit(0);else if(cho5 = 1)printf(您要删去的结点是：);scanf(%c%*c,&node);deletenode(root,node);re1();print_btree(root,0);re2;system(pause);break;else if(cho5 = 2)printf(您要删去的结点是：);scanf(%c%*c,&node);search_deltree(root,node);re1();print_btree(root,0);re2;system(pause);break;else if(cho5 = 3)break;elseerr();else if(cho2 = 6)break;elseerr();printf(是否退出程序(输入0退出程序，输入1返回)：n);scanf(%d%*c,&cho);if(cho = 0)break; /-/*1*/struct tree *create_btree(struct tree *root,struct tree *r,char info) if (r =0 ) r=new (struct tree);/ 申请一块内存，在c中用：malloc(sizeof()if ( r = 0) printf(Out of memoryn); return 0 ; /如果r=0则申请内存失败 直接退出程序r-left= 0; r-right=0; r-info=info;/将r的左右节点设置为空 数据data为infoif (root) if(infoinfo) root - left=r;/要插入的data比根节点中data小 则将其放在左枝else root - right=r;/当root不为空时 创造一个子节点else r-right = 0; r-left = 0; /当root为空时 创造一个根节点return r;if (info info)create_btree(r,r-left,info);if(info=r-info)create_btree(r,r-right,info);/r不为空时，当data小于r中的data则创造左子树，反之创造右子树 /*2*/struct tree *search_btree(struct tree *root,char key) if (!root) printf(Emptu btreen); return root; /当root为空时，提示空树 while(root-info!=key) if(keyinfo) root=root-left;elseroot=root-right;/要检索的值比当前结点的值小，到左子树中继续检索，反之同理if(root=0) printf(Search Failuren);break ; /root为空 提示检索失败 并退出循环 /检索到key时退出循环if (root !=0)printf(Successful searchn key=%cn,root-info);/当检索到的值不为空时，提示检索成功，并将检索到的key值打印return root ;/返回检索值 /*3*/void print_btree(struct tree *r,int l) int i;if (r = 0) return ;/当r为空树时 跳出print_btree(r-left,l+1);/对左子树使用打印函数for(i=0;iinfo);print_btree(r-right,l+1);/将该节点右子树以及右子树的右子树等全部打印出来，并对其中所有左子树使用打印函数/*4*/ void preorder(struct tree *r)if(r != 0)printf(%c,r-info);preorder(r-left);preorder(r-right);/*5*/void inorder(struct tree *r)if(r != 0)inorder(r-left);printf(%c,r-info);inorder(r-right);/*6*/void postorder(struct tree *r)if(r != 0)inorder(r-left);inorder(r-right);printf(%c,r-info);/*7*/void levelorder(struct tree *r) int i,j;tree *q100,*p;p=r;if(p!=0)i=1;qi=p;j=2; while(i!=j)p=qi;printf(%c,p-info);if(p-left!=0) qj=p-left;j+; if(p-right!=0) qj=p-right; j+;i+; /*8*/void pdisptree(struct tree *r) struct tree *stackTREEMAX,*p;int levelTREEMAX2,top,n,i,width=4;if(r!=0) printf(ntt凹入表示法：ntt);top=1;stacktop=r;leveltop0=width;while(top0) p=stacktop;n=leveltop0;for(i=1;iinfo);for(i=n+1;iright!=0) top+;stacktop=p-right;leveltop0=n+width;leveltop1=2;if(p-left!=0) top+;stacktop=p-left;leveltop0=n+width;leveltop1=1;/*9*/int treedepth(struct tree *r) int ldep,rdep;if(r=0)return 0;elseldep=treedepth(r-left);rdep=treedepth(r-right);if(ldeprdep)return ldep+1;else return rdep+1;/*10*/void nodenum(struct tree *r) if(r)count1+;nodenum(r-left);nodenum(r-right);/*11*/void leafnum(struct tree *r) if(r)if(r-left = 0 & r-right = 0)count2+;leafnum(r-left);leafnum(r-right); /*12*/void create_btree2(struct tree *&r,char *str)/根据嵌套括号表示法的字符串*str生成链接存储的二叉树struct tree *stackTREEMAX,*p;int top=-1,k,j=0;/top为指针，k指定是左还是右孩子，j为str指针char ch;r=0;ch=strj;while (ch!=0)switch (ch)case (:top+;stacktop=p;k=1;break; /为左节点case ):top-;break;case ,:k=2;break; /为右节点default :p=new (struct tree);p-info=ch;p-left=p-right=0;if (r=0)