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

河南工程学院数据结构与算法课程设计成果报告树与二叉树转换实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程 1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述32.4 程序流程图53 程序清单64 测试154.1 测试数据155 总结18参考文献181 课程设计目标与任务1.1 课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。1.2 课程设计任务（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目需求分析根据提供的实习题目，认真完成软件设计的全部过程，并以最终软件设计成果来证明其独立完成实际任务的能力，从而，反映出理解和运用数据结构与算法的水平和能力，最后完成软件设计和程序调试并提交文档：课程设计报告书，报告书中包含设计的算法及部分程序代码。2.2 存储结构设计引入头文件： #include #include #include 设置常量： #define MAX_TREE_SIZE 100 一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下： /*树的双亲表示结点结构定义*/ typedef struct int data; int parent; /双亲位置域 PTNode; /*双亲表示法树结构*/ typedef struct PTNode nodeMAX_TREE_SIZE; int count; /根的位置和节点个数 PTree; /*树的孩子兄弟表示结点结构定义*/typedef struct node int data; struct node *firstchild; struct node *rightsib; BTNode,*BTree;2.3 算法描述树的初始化函数（双亲法和孩子结点法两种），建树函数，输出树函数，树的前序遍历函数（递归和非递归两种），树的后序遍历函数(递归和非递归两种）,树的层次遍历函数，一般树和二叉树的转换函数。 主菜单和副菜单。 主函数。 具体代码如下： /初始化树(双亲表示法) 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 preorder2(PTree T) int i; for(i=0;icount=-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 preorder2(PTree T)int i;for(i=0;ifirstchild);printf(%d ,T-data);inoeder(T-rightsib);/树后序遍历(非递归)void inoeder2(PTree T)int i;for(i=T.count-1;i=0;i-)printf(%d ,T.nodei);/层次遍历void level(PTree T)int i;for(i=0;irightsib,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;elseir-rightsib=ip;ir=ip;Tree=&p0;return Tree;/*主菜单*/void Menu()printf(=主菜单=n);printf(*输入1-以双亲法创建一棵一般树*n); printf(*输入2-树的前序遍历(递归)*n); printf(*输入3-树的后序遍历(递归)*n); printf(*输入4-树的前序遍历(非递归)*n); printf(*输入5-树的后序遍历(非递归)*n); printf(*输入6-层次序的非递归遍历*n); printf(*输入0-退出程序*n); printf(=n); printf(请输入执行的指令:);/*副菜单*/void Menu2()printf(*副菜单*n);printf(*9-返回主菜单继续操作*n);printf(*0-退出程序*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 4: printf(树的前序遍历(非递归):n); preorder2(T); printf(n); break; case 5: printf(树的后序遍历(非递归):n); inoeder2(T); printf(n); break; case 6: printf(树的层次遍历:n); level(T); printf(n); break; case 0: exit(1); break; Menu2(); scanf(%d,&c2); if(c2=9) goto loop; else if(c2=0) exit(1); 4 测试4.1 测试数据程序开始：建立一棵一般树：输入指令1输入结点的方式：双亲数据（整型），结点数据（整型） 以-1，-1结束如：-1，1 1，2 -1，-1一般树创建完的具体情况：把一般树转换为二叉树后：5 总结通过本次程序设计，让我更深层次地了解到了树各种函数的运用，如何运用各种存储结构创建树，以及在实验中还涉及到递归的运用，递归的思想省去了复杂的算法设计。在实验中不可避免的出现了大大小小的问题，在调试中透彻领悟各种算法的真谛，同样的错误在下次遇到时就可以避免了。参考文献1朱福喜.Java语言程序设计（第二版）.科学出版社2陈国君等.Java程序设计基础（第二版）.清华大学出版社3Deitel.Java大学基础教程（第六版）.电子工业出版社4MaryCampione.Java语言导学（第四版）.机械工业出版社5Y.DanielLiang.Java语言程序设计基础篇（第六版）.机械工业出版社6KathySierra.HeadFirstJava（第二版）.东南大学出版社#include ;#include ;#include ;#define MAX_TREE_SIZE 100;/*树的双亲表示结点结构定义*/typedef struct int data; int parent; /双亲位置域PTNode;/*双亲表示法树结构*/typedef struct PTNode 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 preorder2(PTree T)int i;for(i=0;ifirstchild);printf(%d ,T-data);inoeder(T-rightsib);/树后序遍历(非递归)void inoeder2(PTree T)int i;for(i=T.count-1;i=0;i-)printf(%d ,T.nodei);/层次遍历void level(PTree T)int i;for(i=0;irightsib,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;elseir-rightsib=ip;ir=ip;Tree=&p0;return Tree;/*主菜单*/void Menu()printf(=主菜单=n);printf(*输入1-以双亲法创建一棵一般树*n); printf(*输入2-树的前序遍历(递归)*n); printf(*输入3-树的后序遍历(递归)*n); printf(*输入4-树的前序遍历(非递归)*n); printf(*输入5-树的后序遍历(非递归)*n); printf(*输入6-层次序的非递归遍历*n); printf(*输入0-退出程序*n); printf(=n); printf(请输入执行的指令:);/*副菜单*/void Menu2()printf(*副菜单*n);printf(*9-返回主菜单继续操作*n);p