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

河南工程学院数据结构与算法课程设计成果报告树与二叉树的转换实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树的转换实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录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课程设计目标数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。 学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要达到以下目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。1.2 课程设计任务设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形形式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3 课程设计要求（1）独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝 。（2）做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。（3）按照课程设计的具体要求建立功能模块，每个模块按要求认真完成。2 分析与设计2.1 题目分析课程设计的最终目标是实现树与二叉树的转换，要实现树与二叉树的转换，首先需要创建一个树，设立节点，并将节点赋值。然后需要将树的数据进行遍历，以便后期实现树转换为二叉树。构建一个数队列与一个二叉树队列，依次进行树队列与二叉树队列的入队与出队。编写算法实现二叉树的数据遍历，转换节点位置。最终实现树与二叉树的转换。将转换后的二叉树进行中序遍历输出，输出遍历后的数据，确保转换成功。2.2 存储结构设计二叉树的存储结构有顺序存储结构与链式存储结构。顺序存储结构的实现是按满二叉树的结点层次编号，依次存放二叉树中的数据元素。其特点是结点间的关系蕴含在其存储位置中，但是，顺序储存结构浪费存储空间。所以顺序存储结构只适用于存满二叉树和完全二叉树。 图2-1树 图2-2 存储表示设计不同的结构特点课构成不同形式的链式存储结构。由二叉树的定义可知，二叉树的结构由一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含3个域：数据域和左右指针域。有时，为了方便找到双亲，则在结点结构中增加一个指向其双亲结点的指针域。利用这种结点结构所得二叉树的存储结构分别称为二叉链表和三叉链表。双亲表示法：每个结点含两个域，数据域，存放结点本身信息；双亲域，指示本结点的双亲结点在数组中的位置。# define MAX_TREE_SIZE 100typedef struct PTnode TElemtype data; 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; /结点数和根结点的位置 CTree;孩子兄弟表示法：用二叉链表作树的存储结构，链表中没两个结点的两个指针分别指向其第一个孩子结点和下一个兄弟结点。但是孩子兄弟表示法破坏了树的层次。 图2-3 孩子兄弟表示法示例2.3 算法描述一树与二叉树的转换：（1）加线：就是在所有兄弟结点之间加一条连线；（2）抹线：就是对树中的每个结点，只保留他与第一个孩子结点之间的连线，删除它与其它孩子结点之间的连线；（3）旋转：就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明 图2-4原始树 图2-5 兄弟之间加下 图2-6 抹线 图2-7 抹线后 图2-8 旋转二树与二叉树的遍历树的先根(次序)遍历方法: 若树不空，则先访问根结点，然后依次先根遍历各棵子树。二叉树的先序遍历：若二叉树为空， 则操作结束， 否则依次执行如下3个操作：访问根结点、先序遍历左子树、先序遍历右子树。这里，若T为根指针，则遍历左右子树时，是分别遍历以T-lchild 和T-rchild 为根指针的子树。由于各子树的遍历和整个二叉树的遍历方式相同，因此，各子树的遍历可递归调用二叉树的遍历算法。void PreOrder ( BiTree *T) if ( T ) visite ( T ); preorder ( T-lchild ) ; preorder ( T-rchild ) ; 3 构建一棵树一棵树（或树形）是一个有限非空的结点集合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); 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 程序流程图根据课程设计要求，构思思路，为了实现树与二叉树的转化我们构建树和二叉树的结构体，开辟内存空间，借助队列实现转化，其程序流程图如下：开始构建树构建二叉树结构体生成一颗树开辟内存空间将树转化为二叉树分配二叉树结点遍历二叉树，输出数组结束 图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 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; 3 程序清单#include stdio.h #include #include /树的节点 struct TreeNode char element; int childNumbers;/孩子结点的个数 struct TreeNode* child3;/孩子的数组 TreeNode() TreeNode(char ele, int numbers) element = ele; childNumbers = numbers; for (int i=0; i3; i+) childi = NULL; TreeNode& operator = (const TreeNode& other) if(this = &other) return *this; else element = other.element; childNumbers = other.childNumbers; for (int i=0; ichild0 = 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; /将树转换为二叉树 BTreeNode* TreeToBinaryTree(TreeNode *treeRoot) if (treeRoot = NULL) return NULL; BTreeNode* binaryRoot = new BTreeNode; /二叉树的根 binaryRoot-element = treeRoot-element; binaryRoot-left = TreeToBinaryTree(treeRoot-child0); /左孩子 BTreeNode *brotherChild = binaryRoot-left; /兄弟 for (int i= 1; ichildNumbers; i+) brotherChild-right = TreeToBinaryTree(treeRoot-childi); brotherChild = brotherChild-right; return binaryRoot; /二叉树中序输出 void MiddleOrderPrint(BTreeNode *root) BTreeNode *temp = root; if(temp = NULL) return; else MiddleOrderPrint(temp-left); printf(%3c,root-element); MiddleOrderPrint(temp-right); int main() TreeNode *treeRoot; CreateTree(treeRoot); BTreeNode *binaryRoot = TreeToBinaryTree(treeRoot); MiddleOrderPrint(binaryRoot); printf(n); return 0; 4 测试4.1 测试数据为了实现树与二叉树的转化，需要一颗已知的树，用来转化为二叉树。本次课程设计采用的已知树其结构图如下：AADECDECDCCBDCB转化为二叉树CEFGDFEG图4-1 原始树 图4-2 二叉树如图4-2所示，二叉树是由图4-1的树转化而来，此二叉树的中序遍历为E、F、B、C、G、D、A，故此次程序运行理论的结果为E、F、B、C、G、D、A。4.2 测试结果分析 编译并运行编写的程序的到下图结果：图4-3 程序运行结果由上图程序运行结果可知转化之后二叉树的中序遍历结果为E、F、B、C、G、D、A，这与原始树转化为二叉树的理论值相同（由图4-2可知），所以树转化为二叉树的算法是正确的。5 总结本次课程设计基本上完成了任务，编写出树转化为二叉树的算法，编写测试程序实现算法，但也认识到了自己的不足，例如关键算法应用不够熟练，需要参考借鉴书籍、网络资源等。在本次课程设计中我对编写程序有了更深的认识，了解了在编写一个程序之前，自己应该综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么。然后再选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以自习斟酌出对挑选出最合适当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了，这样无形中就提高了自己编写程序的质量。另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。参考文献 1严蔚敏等，数据结构（C语言版），清华大学出版社2徐子珊，算法设计、分析与实现（第三版），人民邮电出版3张乃孝，算法与数据结构（第二版），高等教育出版社4杨勇虎，数据结构（C语言版），东软电子出版社5张世和，数据结构习题解析与实训，清华大学出版社#include stdio.h #include #include /树的节点 struct TreeNode char element; int childNumbers;/孩子结点的个数 struct TreeNode* child3;/孩子的数组 TreeNode() TreeNode(char ele, int numbers) element = ele; childNumbers = numbers; for (int i=0; i3; i+) childi = NULL; /重载赋值运算符 TreeNode& operator = (const TreeNode& other) if(this = &other) return *this; else element = other.element; childNumbers = other.childNumbers; for (int i=0; ichild0 = 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; /将树转换为二叉树 BTreeNod