《树与二叉树的转换实现数据结构课程设计成果》由会员分享，可在线阅读，更多相关《树与二叉树的转换实现数据结构课程设计成果（20页珍藏版）》请在金锄头文库上搜索。
1、河南工程学院数据结构与算法课程设计成果报告树与二叉树的转换实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树的转换实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩
2、指导教师评语： 日期： 年 月 日目 录1课程设计目标与任务11.1课程设计目标11.2 课程设计任务11.3 课程设计要求12 分析与设计22.1 题目分析22.2 存储结构设计22.3 算法描述42.4 程序流程图62.5 测试程序说明73 程序清单84 测试114.1 测试数据114.2 测试结果分析125 总结13参考文献141 课程设计目标与任务1.1课程设计目标数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译
3、原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。1.2 课程设计任务设计树与二叉树转换的相关函
4、数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形形式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3 课程设计要求（1）独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝 。（2）做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。（3）按照课程设计的具体要求建立功能模块，每个模块按要求认真完成。2 分析与设计2.1 题目分析课程设计的最终目标
5、是实现树与二叉树的转换，要实现树与二叉树的转换，首先需要创建一个树，设立节点，并将节点赋值。然后需要将树的数据进行遍历，以便后期实现树转换为二叉树。构建一个数队列与一个二叉树队列，依次进行树队列与二叉树队列的入队与出队。编写算法实现二叉树的数据遍历，转换节点位置。最终实现树与二叉树的转换。将转换后的二叉树进行中序遍历输出，输出遍历后的数据，确保转换成功。2.2 存储结构设计二叉树的存储结构有顺序存储结构与链式存储结构。顺序存储结构的实现是按满二叉树的结点层次编号，依次存放二叉树中的数据元素。其特点是结点间的关系蕴含在其存储位置中，但是，顺序储存结构浪费存储空间。所以顺序存储结构只适用于存满二叉
6、树和完全二叉树。 图2-1树 图2-2 存储表示设计不同的结构特点课构成不同形式的链式存储结构。由二叉树的定义可知，二叉树的结构由一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含3个域：数据域和左右指针域。有时，为了方便找到双亲，则在结点结构中增加一个指向其双亲结点的指针域。利用这种结点结构所得二叉树的存储结构分别称为二叉链表和三叉链表。双亲表示法：每个结点含两个域，数据域，存放结点本身信息；双亲域，指示本结点的双亲结点在数组中的位置。# define MAX_TREE_SIZE 100typedef struct PTnode TElemtype data;
7、 int parent; PTnode; /结点类型 typedef struct PTNode nodesMAX_TREE_SIZE; int n; /结点个数 PTree; /树类型孩子链表表示法：孩子结点：typedef struct CTNode int child; struct CTNode *next; *ChildPtr;双亲结点：typedef struct Elem data; ChildPtr firstchild; /孩子链的头指针 CTBox;树结构： typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; /结点数和根结
8、点的位置 CTree;孩子兄弟表示法：用二叉链表作树的存储结构，链表中没两个结点的两个指针分别指向其第一个孩子结点和下一个兄弟结点。但是孩子兄弟表示法破坏了树的层次。 图2-3 孩子兄弟表示法示例2.3 算法描述一树与二叉树的转换：（1）加线：就是在所有兄弟结点之间加一条连线；（2）抹线：就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；（3）旋转：就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明 图2-4原始树 图2-5 兄弟之间加下 图2-6 抹线 图2-7 抹线后 图2-8 旋转二树与二叉树的遍历树的先根(次序)遍历方法: 若树
9、不空，则先访问根结点，然后依次先根遍历各棵子树。二叉树的先序遍历：若二叉树为空， 则操作结束， 否则依次执行如下3个操作：访问根结点、先序遍历左子树、先序遍历右子树。这里，若T为根指针，则遍历左右子树时，是分别遍历以T-lchild 和T-rchild 为根指针的子树。由于各子树的遍历和整个二叉树的遍历方式相同，因此，各子树的遍历可递归调用二叉树的遍历算法。void PreOrder ( BiTree *T) if ( T ) visite ( T ); preorder ( T-lchild ) ; preorder ( T-rchild ) ; 三 构建一棵树一棵树（或树形）是一个有限非空
10、的结点集合T，其中：（1）有个被称为根的结点，记为root(T)；（2）其余结点被分成m=0个不相交的集合T1，T2，,Tm,且又都是树。树T1，T2，,Tm,成为的root(T)子树每一棵树的根都和root(T)有一条边相连。此次课程设为了实现树与二叉树的转化，需定义构建一棵树，用于实现树转化为二叉树的算法，其具体的算法如下所示：void CreateTree(TreeNode* &root) TreeNode *e = new TreeNode(E, 0); TreeNode *f = new TreeNode(F, 0); TreeNode *b = new TreeNode(B, 2)
11、; b-child0 = e; b-child1 = f; TreeNode *g = new TreeNode(G, 0); TreeNode *d = new TreeNode(D, 1); d-child0= g; TreeNode *c = new TreeNode(C, 0); root = new TreeNode(A, 3); root-child0 = b; root-child1 = c; root-child2 = d; 2.4 程序流程图根据课程设计要求，构思思路，为了实现树与二叉树的转化我们构建树和二叉树的结构体，开辟内存空间，借助队列实现转化，其程序流程图如下：开始构
12、建树构建二叉树结构体生成一颗树开辟内存空间将树转化为二叉树分配二叉树结点遍历二叉树，输出数组结束 图2-9 程序流程图2.5 测试程序说明（1）设置主函数调用相关函数用于实现树与二叉树的转换：int main() TreeNode *treeRoot; CreateTree(treeRoot); BTreeNode *binaryRoot = TreeToBinaryTree(treeRoot); MiddleOrderPrint(binaryRoot); printf(n); return 0; （2）设置辅助函数供主程序调用，方便实现算法：void CreateTree(TreeNode* &root) TreeNode *e = new TreeNode(E, 0); TreeNode *f = new TreeNode(F, 0); TreeNode *b = new TreeNode(B, 2); b-child0 = e; b-child1 = f; TreeNode *g = new
