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

河南工程学院《数据结构与算法》课程设计成果报告树与二叉树转换的实现学生学号:学生姓名:学院:计算机学院专业班级:软件工程1341专业课程:《数据结构与算法》指导教师:2014年12月29日题目树与二叉树转换的实现考核项目考核内容得分平时考核(30分)出勤情况、态度、效率;知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计(20分)分析系统的功能模块编程调试(20分)实现系统的各个功能模块,并完成调试回答问题(15分)回答老师针对课程设计提出的问题课程设计报告撰写(10分)严格按照规范要求完成课程设计报告源代码(5分)按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:年月日目录1课程设计目标与任务 22分析与设计 73程序清单 84测试 115总结 13参考文献 。该实践教学是软件设计的综合训练,包括问题分析,总体结构设计用户界面设计,程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼:(1)能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法,正确分析出数据的逻辑结构,合理地选择相应的存储结构,并能设计出解决问题的有效算法;(2)通过上机实****验证自己设计的算法的正确性,学会有效利用基本调试方法,迅速找出程序代码中的错误并且修改;(3)培养算法分析能力,分析所设计算法的时间复杂度和空间复杂度,进一步提高程序设计水平;(4)尽可能借助语言环境实现图形显示功能,以便将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来,获得算法的直观感受。,认真完成软件设计的全部过程,并以最终软件设计成果来证明其独立完成实际任务的能力,从而,反映出理解和运用数据结构与算法的水平和能力,最后完成软件设计和程序调试并提交文档:课程设计报告书,报告书中包含设计的算法及部分程序代码。,以便在程序设计中调用,要求:(1)实现树与二叉树的转换;(2)最好能借助语言环境实现图形显示功能,以便将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来;(3)给出若干例程,演示通过调用自己所缩写程序来实现相关问题的求解。,则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说,给定一棵树,可以找到唯一的一颗二叉树与之对应,从物理结构看来,它们的二叉链表是相同的,只是解释不同而已。1、将树转化为二叉树树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树: ①在所有兄弟结点之间加一连线; ②对每个结点,除了保留与其长子的连线外,去掉该结点与其它孩子的连线。2、将二叉树转化为树把二叉树转换到树和森林自然的方式是:若结点x是双亲y的左孩子,则把x的右孩子,右孩子的右孩子,…,都与y用连线连起来,最后去掉所有双亲到右孩子的连线。#include<>#include<>#include<>设置常量:#defineMAX_TREE_SIZE100一般树的存储结构有以下几种:双亲结点,孩子结点,孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下:/*树的双亲表示结点结构定义*/typedefstruct{intdata;intparent;//双亲位置域}PTNode;/*双亲表示法树结构*/typedefstruct{PTNodenode[MAX_TREE_SIZE];intcount;//根的位置和节点个数}PTree;/*树的孩子兄弟表示结点结构定义*/typedefstructnode{intdata;structnode*firstchild;structnode*rightsib;}BTNode,*:用链表实现创建一个树结点的结构体,从键盘输入数据,存入数组。把下标为2*i+1的值存入左孩子,为2*i+2的存入右孩子。:若二叉树为空,则空操作;否则(1)访问根结点;(2)先序遍历左子树;(3)先序遍历右子树。voidPreOrder(BiNoderoot)。