数据结构课程设计报告-树与二叉树转换的实现.doc

河南工程学院数据结构与算法课程设计成果报告树与二叉树转换的实现学生学号： 学生姓名： 学 院： 计 算 机 学 院 专业班级： 软件工程 1342 专业课程： 数据结构与算法指导教师： 2014 年 12 月 29 日题 目树与二叉树转换的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程设计要求12 分析与设计22.1 题目功能分析22.2 存储结构设计22.3 算法描述32.4 程序流程图42.5 测试程序说明53 程序清单64 测试94.1 测试数据94.2 测试结果分析95 总结11参考文献121 课程设计目标与任务1.1 课程设计目标通过本课程设计，使自己在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，巩固所学的理论知识，培养综合运用所学知识解决实际问题的能力。根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务设计树与二叉树转换的相关函数库，输入树及树转化成二叉树。根据提供的实习题目，认真完成软件设计的全部过程，并以最终软件设计成果来证明其独立完成实际任务的能力，从而，反映出理解和运用数据结构与算法的水平和能力，最后完成软件设计和程序调试并提交文档：课程设计报告书，报告书中包含设计的算法及部分程序代码。1.3 课程设计要求（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目功能分析（1）本程序的功能是对任意二叉树进行递归前序遍历和后序遍历，用栈实现非递归的前序、和后序遍历，还有对树的层序遍历以及树与二叉树的转换。 （2）本程序要求以字符输入，若要实现终端结点，最后以回车键建入数据。（3）本程序的结果将依次打印出输入树及树创建树及转化换成二叉树。2.2 存储结构设计对于树与二叉树的转化，其实有不同的算法结构，这里我们采用了如下的储存结构，一般数的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下：树的存储结构-双亲表示法实现：每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中的位置#define MAX_TREE_SIZE 100Typef struct PTnodeInt parent;PTNode;/结点类型typedef structPTNode node MAX_TREE_SIZE;int count;/结点个数PTree;/树类型树的存储结构-孩子链表表示法孩子结点：typedef struct CTNodeint child;Struct CTNode *next;*CbildPtr;双亲结点：typed structElem data;CbildPtr firstchild;/孩子链的头指针CTBox;树结构：typedef structCTBox nodesMAX_TREE_SIZE;Int n,r;/结点树和根结点的位置CTree;2.3 算法描述树的初始化函数（双亲法和孩子结点法两种），创建普通树结构，以及将其转化为二叉树，这里我们采用了如下的储存结构，进行设计：1.引入头文件：#include#include#include2.设置常量：#define MAX_TREE_SIZE 1003.树的创建：PTree CreatTree(PTree T)int i=1;int fa,ch;PTNode p;for(i=1;ch!=-1;i+)printf(输入第%d结点:n,i);scanf(%d,%d,&fa,&ch);printf(n);p.data=ch;p.parent=fa;T.count+;T.nodeT.count.data=p.data;T.nodeT.count.parent=p.parent; printf(n);return T;4.将树转化成二叉树：(1)加线：在兄弟之间加一连线(2)抹线：对每个结点，除了其左孩子外，去除其与其余孩子支架的关系(3)旋转：以树的根结点为轴心，将整树顺时针转45度。2.4 程序流程图从程序中我们可以知道，我们首先执行的是主菜单，然后会出现执行树的建立这一功能，而我们所用的是双亲法建树，按照格式输入各个结点，再输出树的结点情况，然后第二个功能即将一般树转化成二叉树，然后会有退出程序的功能。并且，主函数的功能执行后要进行副菜单的输出，最后还有一退出程序，即程序完整地执行完毕，它的具体流程图可以如下图2-1所示：图2-1 程序流程图2.5 测试程序说明在visual c+6.0中，运行程序时，首先会出现主界面。主界面有三个选项。选项一、选择此选项进行树的创建。按双亲结点输出树的信息。选项二、此选项可以根据提示进行树的创建。并可以把树转化成二叉树。选项三、此选项可以退出程序。3 程序清单我们在visual C+ 6.0中写出了可以实现要求的程序；以下是详细的程序清单：#include#include#include#define MAX_TREE_SIZE 100/*树的双亲结点结构定义*/typedef structint data;int parent;PTNode;/*双亲表示法树结构 */typedef structPTNode node MAX_TREE_SIZE;int count;/根的位置和结点个数PTree;/*树的孩子兄弟表示结点结构的定义*/typedef struct nodeint data;struct node *firstchild; struct node *rightsib;BTNode,*BTree;/初始化树（双亲表示法）void int_ptree(PTree *tree)tree-count=-1; /初始化树结点（孩子兄弟表示法）BTNode GetTreeNode(int a)BTNode t;t.data=a;t.firstchild=t.rightsib=NULL;return t; /水平输出二叉树void PrintBTree(BTNode *root,int level)int i;if(root!=NULL)PrintBTree(root-rightsib,level+1);for(i=1;idata);PrintBTree(root-firstchild,level+1);/输出树void print_ptree(PTree tree)int i;printf(序号 结点 双亲n);for(i=0;i=tree.count;i+)printf(%8d%8d%8d,i,tree.nodei.data,tree.nodei.parent);printf(n);/*用双亲表示法创建树*/PTree CreatTree(PTree T)int i=1;int fa,ch;PTNode p;for(i=1;ch!=-1;i+)printf(输入第%d结点:n,i);scanf(%d,%d,&fa,&ch);printf(n);p.data=ch;p.parent=fa;T.count+;T.nodeT.count.data=p.data;T.nodeT.count.parent=p.parent; printf(n);return T; /*一般树转换成二叉树*/BTNode *change(PTree T)int i,j=0;BTNode pMAX_TREE_SIZE;BTNode *ip,*is,*ir,*Tree;ip=(BTNode *)malloc(sizeof(BTNode);is=(BTNode *)malloc(sizeof(BTNode);ir=(BTNode *)malloc(sizeof(BTNode);Tree=(BTNode *)malloc(sizeof(BTNode);for(i=0;iT.count;i+)pi=GetTreeNode(T.nodei.data);for(i=1;idata)j+;is=&pj;if(!(is-firstchild)is-firstchild=ip;ir=ip;elseir-rightsib=ip;ir=ip;if(!(is-firstchild)is-firstchild=ip;ir=ip;else ir-rightsib=ip;ir=ip;Tree=&p0;return Tree; /*主菜单*/ void Menu()printf(*主菜单*n);printf(输入1，创建一棵一般树n); printf(输入2，一般树转换成二叉树后的情况:n); printf(输入3，退出程序n);printf(请输入执行的指令:n);/*副菜单*/void Menu2()printf(*副菜单*n);printf(*返回主菜单继续操作*n);printf(*退出程序*n);/*主函数*/ void main()int i=0,c1,c2;PTree T;BTNode *Tree;int_ptree(&T);Menu();scanf(%d,&c1);switch (c1)case 1:printf(建立一般树，依次输入各个结点情况:n);printf(输入结点方式:双亲数据,整型数据(第一个结点双亲数据为-1,最后以-1,-1结束)例子:-1,1,1,3n );T=CreatTree(T);Tree=change(T);case 2:printf(一般树转换成二叉树后的情况:n);PrintBTree(Tree,i);getchar();break;case 3:exit(1);break; Menu2();scanf(%d,&c2);if (c2=9)exit(3);else if(c2=0)exit(1); 4 测试4.1 测试数据正如程序中所述：输入结点方式：双亲数据，整形数据（第一个结点双亲数据为-1，最后以-1，-1结束），所以本次输入数据依次定为：-1,9；1,6；-1，-1。4.2 测试结果分析1.在运行程序时会出现以下界面，如图4.2-1主菜单：图4.2-1主菜单2.用双亲结点创建二叉树，如图4.2-2创建二叉树：图4.2-2创建二叉树3.一般树转化二叉树后的情况，如图4.2-3转化二叉树：图4.2-3转化二叉树5 总结以前用C编程，只是注重如何编写函数能够完成所需要的功能，只是凭意识和简单的语句来堆砌出一段程序。但是现在经过了一周的实训，我们同学自己的讨论，黄老师耐心解答中，我自己感觉完全变了，在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构。然后再选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以自己斟酌出对挑选出最合适当前状况的算法。这样，即使在完整的程序还没写出来之前，自己心中已经有了明确的原图。这次实训也让我看到了自己的不足，还是不能统筹兼顾。还有许多关于C+的一些具体的东西还不太懂。这次实训还让我意识到只有在机子上调试程序，自己的水平才能得到提高。参考文献1程杰.大话数据结构.清华大学出版社2S巴斯.计算机算法：设计和分析引论（朱洪等译）.复旦大学出版社3奈霍夫.数据结构与算法分析（第二版）.清华大学出版社4CliffordA.Shaffer.数据结构与算法分析（第三版）.电子工业出版社 5梅因.数据结构与面向对象程序设计（金名译第四版）.清华大学出版社6姚诗斌.数据库系统基础（第八期）.机械工业出版社#include#include#include#define MAX_TREE_SIZE 100/*树的双亲结点结构定义*/typedef structint data;int parent;PTNode;/*双亲表示法树结构 */typedef structPTNode node MAX_TREE_SIZE;int count;/根的位置和结点个数PTree;/*树的孩子兄弟表示结点结构的定义*/typedef struct nodeint data;struct node *firstchild; struct node *rightsib;BTNode,*BTree;/初始化树（双亲表示法）void int_ptree(PTree *tree)tree-count=-1; /初始化树结点（孩子兄弟表示法）BTNode GetTreeNode(int a)BTNode t;t.data=a;t.firstchild=t.rightsib=NULL;return t; /水平输出二叉树void PrintBTree(BTNode *root,int level)int i;if(root!=NULL)PrintBTree(root-rightsib,level+1);for(i=1;idata);PrintBTree(root-firstchild,level+1);/输出树void print_ptree(PTree tree)int i;printf(序号 结点 双亲n);for(i=0;i=tree.count;i+)printf(%8d%8d%8d,i,tree.nodei.data,tree.nodei.parent);printf(n);/*用双亲表示法创建树*/PTree CreatTree(PTree T)int i=1;int fa,ch;PTNode p;for(i=1;ch!=-1;i+)printf(输入第%d结点:n,i);scanf(%d,%d,&fa,&ch);printf(n);p.data=ch;p.parent=fa;T.count+;T.nodeT.count.data=p.data;T.nodeT.count.parent=p.parent; printf(n);return T; /*一般树转换成二叉树*/BTNode *change(PTree T)int i,j=0;BTNode pMAX_TREE_SIZE;BTNode *ip,*is,*ir,*Tree;ip=(BTNode *)malloc(sizeof(BTNode);is=(BTNode *)malloc(sizeof(BTNode);ir=(BTNode *)malloc(sizeof(BTNode);Tree=(BTNode *)malloc(sizeof(BTNode);for(i=0;iT.count;i+)pi=GetTreeNode(T.nodei.data);for(i=1;ida