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

河南工程学院数据结构与算法课程设计成果报告树与二叉树的转换实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1342班 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树的转换实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录一、 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3课程设计要求1二、分析与设计22.1 题目分析22.2 存储结构设计22.3 算法描述32.4 程序流程图52.5测试程序说明7三、 程序清单9四、测试134.1 测试数据134.2 测试结果分析15五、总结16参考文献17一、 课程设计目标与任务1.1 课程设计目标通过本课程设计，使我们在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。通过本课程设计，使我们进一步深化掌握C语言的基本知识；掌握结构化程序设计的基本方法和设计技巧，进一步了解算法分析与设计概念；理解面向对象程序设计思想，初步具备运用面向对象程序设计方法进行程序设计的能力。能熟练应用VC+集成环境进行C+语言程序的编写、编译与调试，提高自己对本课程知识综合运用能力。1.2 课程设计任务设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3课程设计要求根据提供的课程设计的题目，掌握程序分析方法，学会程序设计的基本方法，认真完成题目的要求，从而增强理解和运用C+程序知识的能力，并以最终程序运行结果来证明完成课程设计任务，最后完成题目要求和程序调试并提交文档，课程设计报告书中包含算法及部分程序代码。二、分析与设计2.1 题目分析这个程序的功能是对任意二叉树用栈实现树与二叉树的转换，要求用户以字符输入，若要实现终端结点，最后以回车键键入数据，程序的结果将打印出树及树转换成的二叉树。2.2 存储结构设计树是一种非线性的数据结构，树中的元素之间是一对多的层次关系。一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。这个程序运用到的是双亲结点和孩子兄弟结点。具体存储结构如下：/*树的双亲表示借点结构定义*/typedef structint data;int parent; /双亲位置域PTNode;/*双亲表示法树结构*/typedef structPTNode nodeMAX_TREE_SIZE;int count; /根的位置和结点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct nodeint data;struct node*firstchild;struct node*rightsib;BTNode,*BTree;2.3 算法描述（1）用双亲表示法创建一棵树：创建树的结点，同时在每个结点中附设一个指针指示结点在链表中位置，具体代码如下：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);printf(创建的树具体情况如下:n);print_ptree(T);return T;（2） 树与二叉树的转换：转换时结点的第一个孩子变为它的左孩子，兄弟结点变为它的右孩子。用孩子兄弟表示法将树转换为即以二叉链表作树的存储结构，链表中结点的两个域分别指向该结点的第一个孩子结点和右侧第一个兄弟结点，当你将这两个指针看作是二叉树中的左孩子指针和右孩子指针时，就是一棵二叉树了。具体代码如下： 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;Tree=&p0;return Tree;（3）树的前序遍历：先访问根结点，再遍历左子树，最后遍历右子树。具体代码如下：void preorder(BTNode *T) if(T!=NULL) printf(%d ,T-data); preorder(T-firstchild); preorder(T-nextchild); （4）树的后序遍历：先遍历左子树，再遍历右子树，最后访问根结点。具体代码如下：void inoeder(BTNode *T)if(T!=NULL)inoeder(T-firstchild);printf(%d ,T-data);inoeder(T-nextchild);2.4 程序流程图程序开始后首先进入主菜单，选择是用双亲法创建一棵一般树还是退出程序，若选择退出程序，则程序关闭；若选择用双亲法创建一棵一般树，则进入下一项，按照程序给出的格式从键盘输入各个结点，计算机会根据程序的流程输出树的结点情况，同时会输出一棵一般树创建完成的具体情况，然后计算机会根据程序的步骤将这棵一般树转换成二叉树。最后进入副菜单，用户根据需求选择继续进行树与二叉树的转换或者退出程序，流程图如图2-1所示。一般树转换成二叉树退出程序退出程序开始主菜单双亲法建树按照格式输入各个结点输出树的结点情况副菜单 图2-1 程序流程图2.5测试程序说明本次课程设计任务是完成树与二叉树的转换，将（a）树转换成二叉树其步骤及过程如下：ACEDB （a)(1)加线：就是在所有兄弟结点间加一条线。ACEDB（b）（2）抹线：就是对树中的每个结点只保留它与左孩子结点之间的连线，删除它与其它孩子结点之间的连线。ACEDB（c）（3）旋转：就是以树的根结点为轴心，将整棵树顺时针旋转45度，使二叉树结构层次分明。ACEDB（d）3、 程序清单#include#include#include#define MAX_TREE_SIZE 100/*树的双亲表示借点结构定义*/typedef structint data;int parent; /双亲位置域PTNode;/*双亲表示法树结构*/typedef structPTNode nodeMAX_TREE_SIZE;int count; /根的位置和结点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct nodeint data;struct node*firstchild;struct node*rightsib;BTNode,*BTree;/初始化树（双亲表示法）void init_ptree(PTree*tree)tree-count=-1;/初始化树结点（孩子兄弟表示法）BTNode GetTreeNode(int x)BTNode t;t.data=x;t.firstchild=t.rightsib=NULL;return t;/树的前序遍历void preorder(BTNode *T)if(T!=NULL)printf(%d ,T-data);preorder(T-firstchild);preorder(T-rightsib);/树后序遍历void inoeder(BTNode *T)if(T!=NULL)inoeder(T-firstchild);printf(%d ,T-data);inoeder(T-rightsib);/水平输出二叉树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);printf(创建的树具体情况如下:n);print_ptree(T);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;else ir-rightsib=ip;ir=ip;Tree=&p0;return Tree;/*主菜单*/void Menu() printf(=主菜单=n);printf(*输入1-以双亲法创建一棵一般树*n);printf(*输入2-树的前序遍历*n);printf(*输入3-树的后序遍历*n);printf(*输入0-退出程序*n);printf(=n);printf(请输入执行的指令：);/*副菜单*/void Menu2() printf(*副菜单*n);printf(*9-返回主菜单继续操作*n);printf(*1-退出程序*n);/*主函数*/void main() int i=0,c1,c2;PTree T;BTNode*Tree;init_ptree(&T);loop:Menu();scanf(%d,&c1);switch(c1)case 1: printf(建立一般树，依次输入各个结点情况：n);printf(输入结点方式：双亲数据，整型数据（第一个结点双亲数据为-1，最后以-1，-1结束）n例子：-1，1 1，3n);T=CreatTree(T);Tree=change(T);printf(一般树转换成二叉树后的情况：n);PrintBTree(Tree,i);getchar();break;case 2: printf(树的前序遍历:n); preorder(Tree); printf(n); break; case 3: printf(树的后序遍历:n); inoeder(Tree); printf(n); break;case 0:exit(1);break;Menu2();scanf(%d,&c2);if(c2=9) goto loop;else if(c2=0)exit(1);四、测试4.1 测试数据1程序开始，建立一棵一般树：输入指令1，双亲法创建一棵一般树，然后输入结点，输入结点方式：双亲数据（整型），结点数据（整型）以-1，-1结束，如：-1，1 1，2 -1，-1。一般树创建完及一般树转换成二叉树的具体情况如图4-1：图4-1 树转换二叉树图2副菜单选择9返回主菜单后输入指令2，执行树的前序遍历，如图4-2：图4-2 树的前序遍历图3副菜单选择9返回主菜单后输入指令3，执行树的后序遍历，如图4-3：图4-3 树的后序遍历图4程序操作完毕后，副菜单选择0退出程序 。4.2 测试结果分析在MicrosoftVisualC+6.0软件中建立一个空的工程，然后新建一个C+SourceFile文件，编写程序代码，后对编写的程序进行编译，直到程序没有错误，最后执行程序，输入要测试的数据，得出执行结果。在调试过程中出现了很多问题，定义表过长，处理记录数据错误是程序的异常，记录冲突次数，输入树的结点时总是进入死循环等等。通过问同学，查资料，对程序进行了一系列的修改，在编译没有错误后，运行程序。根据程序的提示，首先根据指令输入信息，生成一棵树后，再将生成的树转换成二叉树，输出二叉树的结构图，然后根据指令选择是继续进行树与二叉树的转换或者退出程序。五、总结之前上数据结构的理论课和实践课，对数据结构的算法的理解都是很模糊的，很多算法的掌握都很生疏，所以导致在这次课程设计中，出现了很多问题，算法的不完善、调试程序时总是出错、总是进入死循环等等，对这些错误，我不得不花费大量的时间查找资料去更正，并且还要重复检查是否出现雷同的错误而导致程序不能运行。但是通过这次课程设计，加强了我的动手能力，以及提升了局部和统一考虑问题的思维方式。在进行程序设计的时候，要注意想好思路，即要有恰当模块名、变量名、常量名、子程序名等。将每个功能的模块，即函数名要清晰的表述出来，使用户能够一目了然此程序的功能。当然适当的给些注释，也是方便用户的理解，还有在编写程序时要注意对程序的适当分配，便于用户看懂程序，也便于自己检查程序。但是完成任何一个较大的程序，都需要掌握一定的编程基础，需要不断的探索和求知过程，这样对自己编程能力的提高有较大的帮助。当然，任何程序都必须经过计算机的调试，看是否调试成功，发现错误，一个个，一步步去解决，这样就能从错误中进步。参考文献1严蔚敏.数据结构（C语言版）. 清华大学出版社2王路群.数据结构-C语言描述. 中国水利水电出版社3王国钧.数据结构实验教程（C语言版）. 清华大学出版社4严蔚敏等.数据结构题集. 清华大学出版社5殷人昆.数据结构（C语言描述）. 机械工业出版社#include#include#include#define MAX_TREE_SIZE 100/*树的双亲表示借点结构定义*/typedef structint data;int parent; /双亲位置域PTNode;/*双亲表示法树结构*/typedef structPTNode nodeMAX_TREE_SIZE;int count; /根的位置和结点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct nodeint data;struct node*firstchild;struct node*rightsib;BTNode,*BTree;/初始化树（双亲表示法）void init_ptree(PTree*tree)tree-count=-1;/初始化树结点（孩子兄弟表示法）BTNode GetTreeNode(int x)BTNode t;t.data=x;t.firstchild=t.rightsib=NULL;return t;/树的前序遍历void preorder(BTNode *T)if(T!=NULL)printf(%d ,T-data);preorder(T-firstchild);preorder(T-rightsib);/树后序遍历void inoeder(BTNode *T)if(T!=NULL)inoeder(T-firstchild);printf(%d ,T-data);inoeder(T-rightsib);/水平输出二叉树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);printf(创建的树具体情况如下:n);print_ptree(T);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