树与二叉树转换的实现.docx

《树与二叉树转换的实现.docx》由会员分享，可在线阅读，更多相关《树与二叉树转换的实现.docx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河南工程学院数据结构与算法课程设计成果报告树与二叉树转换的实现2014年12月29日int vextex;int x,y;edgenode *link;vexnode;const int px=1,2,2,1,-1,2,-2,-1;const int py=2,1,-1,-2,-2,-1,1,2;const int L=8,H=8;vexnode gaL*H;int visitedL*H=0;int stackL*H;int top;seqstack;seqstack s;void setnull(seqstack *s)s-top=-l;int empty(seqstack *s)if(s-

2、toptopL*H-l)printf(stack overflow!n);7return 0;)elses-stack+s-top = x;return 1;)int pop(seqstack *s)(if(s-toptop-;return(s-stacks-top+l);)void init()int n;for (int i=0;iH;i+)for (int j=O;jL;j+)n=L*i+j;gan.vextex=n;gan.x=j;gan.y=i;gan.link=NULL;)for (i=0;iL*H;i+)edgenode *p;for (int k=0;kMAX;k+)int t

3、x=gai.x+pxk;int ty=gai.y+pyk;if(tx0| |ty=L| |ty=H) continue;else(p=(edgenode*)malloc(sizeof(edgenode);p-vextex=ty*L+tx;p-next=gai.link;gai.link=p;)void show()int i;printf(n);for (i=0;izgai.vextex);edgenode *p;p=(edgenode*)malloc(sizeof(edgenode);p=gai.link;while (p!=NULL)printf(%d ,p-vextex);p=p-nex

4、t;)printf(n);)void showanswerf)int rankL*H;int tag=s.top;for (int i=L*H-l;i=O;i-)ranks.stacktag-=i;)for (i=O;ivextex)HFS(p-vextex);)p=p-next;)if (s.top=L*H-l)printffanswer %d:n/sum+);showanswerf);printf(n);)visited s.stacks.top=0;pop(&s);if (empty(&s)return 0;)return 0;int main()11int n;for (n=0;nH*

5、L;n+)memsetfvisitedAsizeoffvisited);init();show();setnull(&s);HFS(n);getch();)return 0;)4测试4.1测试数据程序开始:5qC:JIS0FTCTuYanbinwvtep. ex请输入执行的指令:.主菜单*输入1以双亲法创立一棵一般树*输入2树的前序遍历（递归）*输入3树的后序遍历（递归）*输入4树的前序遍历（非递归）*聿输入5树的后序遍历（非递归）*输入6层次序的非递归遍历*输入0退出 gjy：*图4. 1-1开始界面12建立一棵一般树：输入指令1C:JISOFTCTuyanbwvrteBp. exe募单*输

6、入1以双亲法创立一棵一般树*科输入2一树的前序遍历（递归）*c*输入3树的后序遍历（递归）*输入4树的前序遍历（非递归）*,*输入5树的后序遍历（非递归）*F*输入6层次序的非递归遍历*输入0退出程序 *着输入执行的指令：1建立一般树，依次输入各个结点情况：俞入结点方式:双亲数据,整型数据（第一个结点双亲数据为-1,最后以-1, -1结束）列子:T,1 1,3俞入第1结点： 输入结点的方式: 双亲数据（整型），结点数据（整型）以T, T结束如：-1, 11, 2 -1, -1C:JiSOFTCToTnbinmFep. ee，“蛹入攵树的前存遍历健丽* *输入3-树的后序遍历（递归”*瑜入4树的

7、前序遍历（非递归）*输入5树的后序遍历（非递归）*输入6其次序的非递归遍历”等*编入0退出程序*mxma请输入执行的指令：1建立一般树,依次输入各个给点情况：希入结点方式:双亲数据,整型数据（第一个结点双亲数据为一】，是后以T, -1结束）例子:-1,1 1,3输入第1转点：-bl物人第2结点：1,2粕入第3结点：1,3输入第4结点：2,4徜入第5结点：图4. 1-2 一殷树初始建立13迥, .一般树创立完的具体情况:a C:JlSOFTCTuTnnbinwtop.仄缁点方式:双亲数据,整型数据舜二T菇点寿数据存1,最后以寸1结葡仔：-1,1 1,3i入第1结点：输入第2结点:1,2输入第3布

8、点: 1,3输入第S防点:2,4输入第5诘点:创立的树具体情况如下:序号结点双亲01-11212313424-1-1JlSOFTCTuTanbxnwtGap.创立的树具体情况如下:序号结点双亲01-11212313424-1-1一用树转换成二叉树后的情况:DACvuYan I 修i ,、vUh】Tes e：-般树转换成二叉树后的情况:D:CYuYanib wwtFnipxnce-B?*=*,243-副菜单一P返回企差单继续揉倍*0退,出程序 MW*-1口1*1图4. 1-4 一般树转化为二叉树需三 T声 单王程 si 副返退执序 入后3翦215一1树健历历历国 LA BL IL 二二创遢遍遍靠

9、法 iiyhifAs 序 双的的的的次出 ,以层退副菜单项选择择:选择。结束程序黄留!十 frfMriMtwirfMrfwrwiewwwwwi*-9速直至菜单继续操作*-*退 出程方二Procs any koy to continue图4. 1-5返回主菜单界面4. 2测试分析详细设计过程共有以下函数的实现：树的初始化函数（双亲法和孩子节点法两种），建树函数，输出树函数，树 的前序遍历函数（递归和非递归两种），树的后序遍历函数（递归和非递归两种）， 树的层次遍历函数，一般树和二叉树的转换函数。主菜单和副菜单，主函数。5总结16题目树与二叉树转换的实现考核工程考核内容得分平时考核（30分）出勤情

10、况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有 明确的战术，只是凭意识和简单的语句来堆砌出一段段程序。现在变成感觉完全 不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要 的数据结构，是树还是图或是别的什么。然后再

11、选定一种或几种存储结构来具体 的决定后面的函数的主要风格。最后在编写每个函数之前，可以自习斟酌出对 挑选出最合适当前状况的算法。这样，即使在完整的程序还没有写出来之前，自 己心中己经有了明确的原图了。这样无形中就提高了自己编写程序的质量。另外, 我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好 处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往 往是编写程序的关键。这次试验也让我看到了自己的缺乏，还是不太用模版类。 还有许多关于C+的一些比拟具体的东西还不太懂，比方说指针。这次实验还让 我意识到只有不管在机子上调试程序，自己的水平才能得到提高。我会继续我

12、的 兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步和提高。17参考文献1严蔚敏、吴伟民编.数据结构（C语言版）（含盘）.清华大学出版社2严蔚敏.数据结构题集（C语言版）（第二版）.清华大学出版社3赵坚、姜梅主编.数据结构（C语言版）学习指导与习题解答（第六版）.中国水利水电出版社4秋叶拓哉等.挑战程序设计竞赛（第2版）.人民邮电出版社5严蔚敏等.数据结构（C语言版）.清华大学出版社Thomas 11. Cormen.算法导论（第二版）.机械工业出版社出版6 Jon Bentley.编程珠矶.人民邮电出版社181课程设计目标11.1 课程设计目标11.2 课程设计任务11.3 课程设计

13、要求22分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述42.4 程序流程图42.5 测试程序说明53程序清单64测试124.1 测试数据124.2 测试结果分析165总结16参考文献181课程设计目标与任务1.1 课程设计目标（1）通过课程设计，巩固所学的理论知识，培养综合运用所学知识解决实 际问题的能力。（2） 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计 能力。（3）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基 本方法和技能。（4）提高综合运用所学的理论知识和方法独立分析和解决问题的能力，增 强理论与实践相结合的技巧。（5）训练用系

14、统的观点和软件开发一般规范进行软件开发，培养软件工作 者所应具备的科学的工作方法和作风。（6）增强团队合作意识，初步了解软件开发的一般过程，培养学习热情以 及加强自主学习。（7）训练自己动手分析，解决问题的能力，掌握调试程序，排成错误的常 用技巧。（8）增强动手能力，学会结合实际解决问题。1. 2课程设计任务（1）根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算 法，正确分析出数据的逻辑结构，合理地选择相映的存储结构，并能设计出解决 问题的有效算法。实现树与二叉树之间的转换。（2）掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。（3）掌握用指针类型描述、访问和处理二叉树的运

15、算。2. 3课程设计要求（1）认真阅读和掌握本实验的程序。（2）上机编写并运行本程序。（3）保存和打印出本程序的运行结果，并结合程序进行分析。（4）按照二叉树的操作需求，重新改写主程序并运行，打印出文件清单和 运行结果。2分析与设计2.1 题目需求分析实现树与二叉树的转换，以及树的前序、后序的递归、非递归遍历算法，层 次序的非递归算法的实现，应包含建树的实现。（多种遍历可以只实现一个）2存储结构设计引入头文件：#include#include#include设置常量：ftdefineMAX TREE SIZE 100一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实 验运用到的

16、是双亲结点和孩子兄弟结点，具体存储结构如下:/*树的双亲表示结点结构定义*/typedef struct(int data;int parent;双亲位置域JPTNode；/ *双亲表示法树结构* /typedef struct(PTNode nodeMAX_TREE_SIZE;int count;根的位置和结点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct node(int data;struct node*firstchild;struct node*rightsib;BTNode, *BTree;2. 3算法描述1 .二叉树创立用链表实现创立一个树结点的

17、结构体，从键盘输入数据，存入数组。把下标 为2*i+l的值存入左孩子，为2*i+2的存入右孩子。2 .先序遍历二叉树的递归算法假设二叉树为空，那么空操作；否那么(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。void PreOrder (BiNode root) o3 .后序遍历二又树的递归算法假设二叉树为空，那么空操作；否那么(1)后序遍历左子树；(2)后序遍历右子 树。(3)访问根结点；void PostOrder (BiNode root) 04 .先序非递归算法BiNodc根指针，假设BiNode!二NULL对于非递归算法，引入栈模拟递归工作 栈，初始时栈为空。5 .后序

18、非递归算法BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。void F_PostOrder (BiNode root) 06 .层次序遍历算法按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队 列。void LevelOrder (BiNode root) o2.4程序流程图设计如下流程图：首先根据指令，输入信息，生成一棵树后，再将生成的树转化为二叉树，然 后输出生成的二叉树的结构图、二叉树的前序遍历结果以及二叉树的深度和孩子 结点。在非递归遍历时，容易进入死循环，这时需要分步调试并最终找到循环结 束条件，顺利输出结

19、果。图2. 4-1程序流程图2. 5测试程序说明在调试过程中出现了很多问题，定义表过长的，处理记录数量错误时程序的 异常，记录冲突次数等等。通过问同学，查资料，我知道路定义过长那么减少某些属性的字符数。处理记 录数量错误时程序的异常那么在被调用类（被主程序或其他类调用的类）中捕获异 常记录到容器类中，然后抛出；在调用类（非主程序类）中继续捕获，然后同样 是记录到错误容器继续向上抛出；依此方法直到最后在主程序中（入口程序类） 捕获异常（记住这个捕获一定要捕获所有可能异常的情况）然后连同此次错误信 息一并记录到错误容器，写入错误日志，给出相应提示。二叉树遍历中用到的最重要的一个思想就是递归调用，这

20、次作业使我对递归 有了深入的理解，尤其是对退回上一层后应执行的语句和结点位置的丝路更加清 晰。程序调试比拟顺利。3程序清单typedef struct #include#include#include#include#define edgetype int/define vextype int/define MAX 8typedef struct nodeint vextex;struct node *next;Jedgenode;typedef struct632 4*副菜单* *9整回主菜单继续糜作* * * 0退 出*”*/*，*，*图4. 1-3 一般树的完善副菜单项选择择：选择9继续操作运用各种遍历形式遍历树：14