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

河南工程学院《数据结构与算法》课程设计成果报告树与二叉树的转换实现学生学号:学生姓名:学院:计算机学院专业班级:软件工程1342班专业课程:《数据结构与算法》指导教师:2014年12月29日题目树与二叉树的转换实现考核项目考核内容得分平时考核(30分)出勤情况、态度、效率;知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计(20分)分析系统的功能模块编程调试(20分)实现系统的各个功能模块,并完成调试回答问题(15分)回答老师针对课程设计提出的问题课程设计报告撰写(10分)严格按照规范要求完成课程设计报告源代码(5分)按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:年月日目录一、课程设计目标与任务 1二、分析与设计 7三、程序清单 9四、测试 15五、总结 16参考文献 17一、,使我们在数据结构的选择和应用、算法的设计与实现方面得到训练,加深对数据结构基本内容的理解和灵活应用,同时,在程序设计方法及上机操作方面受到比较系统严格的训练,培养软件工作所需要的动手能力。通过本课程设计,使我们进一步深化掌握C语言的基本知识;掌握结构化程序设计的基本方法和设计技巧,进一步了解算法分析与设计概念;理解面向对象程序设计思想,初步具备运用面向对象程序设计方法进行程序设计的能力。能熟练应用VC++集成环境进行C++语言程序的编写、编译与调试,提高自己对本课程知识综合运用能力。,以便在程序设计中调用,要求:(1)实现树与二叉树的转换;(2)最好能借助语言环境实现图形显示功能,以便将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来;(3)给出若干例程,演示通过调用自己所缩写程序来实现相关问题的求解。,掌握程序分析方法,学会程序设计的基本方法,认真完成题目的要求,从而增强理解和运用C++程序知识的能力,并以最终程序运行结果来证明完成课程设计任务,最后完成题目要求和程序调试并提交文档,课程设计报告书中包含算法及部分程序代码。二、,要求用户以字符输入,若要实现终端结点,最后以回车键键入数据,程序的结果将打印出树及树转换成的二叉树。,树中的元素之间是一对多的层次关系。一般树的存储结构有以下几种:双亲结点,孩子结点,孩子兄弟结点。这个程序运用到的是双亲结点和孩子兄弟结点。具体存储结构如下:/*树的双亲表示借点结构定义*/typedefstruct{intdata; intparent;//双亲位置域}PTNode;/*双亲表示法树结构*/typedefstruct{ PTNodenode[MAX_TREE_SIZE]; intcount;//根的位置和结点个数}PTree;/*树的孩子兄弟表示结点结构定义*/typedefstructnode{ intdata; structnode*firstchild; structnode*rightsib;}BTNode,*BTree;(1)用双亲表示法创建一棵树:创建树的结点,同时在每个结点中附设一个指针指示结点在链表中位置,具体代码如下:PTreeCreatTree(PTreeT){ inti=1; intfa,ch; PTNodep; for(i=1;ch!=-1;i++) { printf("输入第%d结点:\n",i); scanf("%d,%d",&fa,&ch); printf("\n"); =ch; =fa; ++; [].data=; [].parent=; } printf("\n"); printf("创建的树具体情况如下:\n"); print_ptree(T); returnT;}(2)树与二叉树的转换:转换时结点的第一个孩子变为它的左孩子,兄弟结点变为它的右孩子。用孩子兄弟表示法将树转换为即以二叉链表作树的存储结构,链表中结点的两个域分别指向该结点的第一个孩子结点和右侧第一个兄弟结点,当你将这两个指针看作是二叉树中的左孩子指针和右孩子指针时,就是一棵二叉树了。具体代码如下:BTNode*change(PTreeT){ inti,j=0; BTNod