树与二叉树的转换实现15.docx

《树与二叉树的转换实现15.docx》由会员分享，可在线阅读，更多相关《树与二叉树的转换实现15.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河南工程学院数据结构与算法课程设计成果报告树与二叉树的转换实现2014年12月29日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 =

2、new TreeNode *f = new TreeNode *b = new b-child0= e; b-child1 = f; TreeNode *g = new TreeNode *d = new d-child0= g;TreeNode *c = newTreeNode *e = new TreeNode *f = new TreeNode *b = new b-child0= e; b-child1 = f; TreeNode *g = new TreeNode *d = new d-child0= g;TreeNode *c = newTreeNode ( E, TreeNode

3、 ( F, TreeNode ( B,TreeNode ( G, TreeNode ( D,TreeNode ( C ,0);0);2);0);1)；0);root = new TreeNode ( A , 3);root-child0 = b;root-childl = c;root-child2= d;3程序清单include stdio. hinclude ftinclude 树的节点 struct TreeNodechar element;int childNumbers;孩子结点的个数struct TreeNode* child3;孩子的数组TreeNode () TreeNode(

4、char ele, int numbers) (element = ele;childNumbers = numbers; for (int i=0; i3; i+)childi= NULL;)TreeNodefe operator = (const TreeNode& other) (if (this = &other) return *this; else (element = other, element;childNumbers = other. childNumbers; for (int i=0; ichild0= b-childl= TreeNode *g = TreeNode

5、*d =TreeNode *e = TreeNode *f = TreeNode *b = b-child0= b-childl= TreeNode *g = TreeNode *d =new TreeNode ( E, new TreeNode ( F, new TreeNode ( B, e;f ；new TreeNode ( G, new TreeNode ( D,0);0);2);d-child0= g; TreeNode *c =new TreeNode ( C,0);1)；0);root = new TreeNode (5 A5, 3);root-child0 = b;root-c

6、hildl = 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-chiId 0); 左孩子BTreeNode *brotherChild = binaryRoot-left; /兄

7、弟 for (int i= 1; ichildNumbers; i+) (brotherChild-right = TreeToBinaryTree(treeRoot-chiIdi); brotherChild = brotherChild-right;) return binaryRoot;)二叉树中序输出void MiddleOrderPrint(BTreeNode *root) BTreeNode *temp = root;if (temp = NULL)return; elseMiddleOrderPrint(temp-left);printf (3c，root-element);Mi

8、ddleOrderPrint(temp-right);int main ()(TreeNode *treeRoot;CreateTree(treeRoot);BTreeNode *binaryRoot = TreeToBinaryTree(treeRoot);MiddleOrderPrint(binaryRoot);printf (n);return 0;104测试4.1测试数据为了实现树与二叉树的转化，需要一颗的树，用来转化为二叉树。本次 课程设计采用的树其结构图如下：图4-1原始树转化为二叉树图4-2二叉树如图4-2所示，二叉树是由图4-1的树转化而来，此二叉树的中序遍历为E、F、B、C、

9、G、D、A,故此次程序运行理论的结果为E、F、B、C、G、D、A。114. 2测试结果分析编译并运行编写的程序的到下列图结果:E F B C G D A Press any key to continue图4-3程序运行结果由上图程序运行结果可知转化之后二叉树的中序遍历结果为E、F、B、C、G、D、A,这与原始树转化为二叉树的理论值相同（由图4-2可知），所以树转化为二叉树的算法是正确的。125总结本次课程设计基本上完成了任务，编写出树转化为二叉树的算法，编写测试 程序实现算法，但也认识到了自己的缺乏，例如关键算法应用不够熟练，需要参 考借鉴书籍、网络资源等。在本次课程设计中我对编写程序有了更

10、深的认识，了解了在编写一个程序之 前，自己应该综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或 是别的什么。然后再选定一种或几种存储结构来具体的决定后面的函数的主要风 格。最后在编写每一个函数之前，可以自习斟酌出对挑选出最合适当前状况的算 法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图 了，这样无形中就提高了自己编写程序的质量。另外，我还体会到深刻理解数据 结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据 结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。13参考文献严蔚敏等，数据结构（C语言版），清华大学出版社2徐子珊，

11、算法设计、分析与实现（第三版），人民邮电出版张乃孝，算法与数据结构（第二版），高等教育出版社杨勇虎，数据结构（C语言版），东软电子出版社张世和，数据结构习题解析与实训，清华大学出版社14题目树与二叉树的转换实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期

12、: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课程设计目标数据结构与算法课程主要是研究非数值计算的程序设计问题中所出现的计 算机操作对象以及它们之间的关系和操作的学科。数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核 心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重 要基础，广泛的应用于信

13、息学、系统工程等各种领域。学习数据结构与算法是为了将实际问题中涉及的对象在计算机中表示出来 并对它们进行处理。通过课程设计可以提高学生的思维能力，促进学生的综合应 用能力和专业素质的提高。通过此次课程设计主要到达以下目的：了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法 和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应 具备的科学的工作方法和作风。1. 2课程设计任务设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（

14、1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形形式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1. 3课程设计要求（1）独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成, 遇到问题可以讨论，但不可以拷贝。（2）做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想 好调试步骤和有关环境的设置方法，准备好有关的文件。（3）按照课程设计的具体要求建立功能模块，每个模块按要求认真完成。2分析与设计1 .1题目分析课程设计的最终目标是实现树与二叉树的转换，要实现树

15、与二叉树的转换， 首先需要创立一个树，设立节点，并将节点赋值。然后需要将树的数据进行遍历, 以便后期实现树转换为二叉树。构建一个数队列与一个二叉树队列，依次进行树 队列与二叉树队列的入队与出队。编写算法实现二叉树的数据遍历，转换节点位 置。最终实现树与二叉树的转换。将转换后的二叉树进行中序遍历输出，输出遍 历后的数据，确保转换成功。2 . 2存储结构设计二叉树的存储结构有顺序存储结构与链式存储结构。顺序存储结构的实现是 按满二叉树的结点层次编号，依次存放二叉树中的数据元素。其特点是结点间的 关系蕴含在其存储位置中，但是，顺序储存结构浪费存储空间。所以顺序存储结 构只适用于存满二叉树和完全二叉树

16、。abcde0000fg123456789 10 11图2-1树图2-2存储表示设计不同的结构特点课构成不同形式的链式存储结构。由二叉树的定义可 知，二叉树的结构由一个数据元素和分别指向其左右子树的两个分支构成，那么表 示二叉树的链表中的结点至少包含3个域：数据域和左右指针域。有时，为了方 便找到双亲，那么在结点结构中增加一个指向其双亲结点的指针域。利用这种结点 结构所得二叉树的存储结构分别称为二叉链表和三叉链表。双亲表示法：每个结点含两个域，数据域，存放结点本身信息；双亲域，指 示本结点的双亲结点在数组中的位置。# define MAX_TREE_SIZE 100typedef struct

17、 PTnode TElemtype data;int parent; PTnode; 结点类型typedef structPTNode 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;

18、int n, r;结点数和根结点的位置图23孩子兄弟表示法例如 CTree;孩子兄弟表示法：用二叉链 表作树的存储结构，链表中没两 个结点的两个指针分别指向其 第一个孩子结点和下一个兄弟 结点。但是孩子兄弟表示法破坏 了树的层次。2. 3算法描述一.树与二叉树的转换：（1）加线：就是在所有兄弟结点之间加一条连线；（2）抹线：就是对树中的每个结点，只保存他与第一个孩子结点之间的连 线，删除它与其它孩子结点之间的连线；（3）旋转：就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使 之结构层次清楚图2-4原始树图2-5兄弟之间加下图2-4原始树图2-5兄弟之间加下图2-7抹线后图2-6抹线图2-

19、8旋转二.树与二叉树的遍历树的先根(次序)遍历方法：假设树不空，那么先访问根结点，然后依次先 根遍历各棵子树。二叉树的先序遍历：假设二叉树为空，那么操作结束，否那么依次执行如下 3个操作：访问根结点、先序遍历左子树、先序遍历右子树。这里，假设T为 根指针，那么遍历左右子树时，是分别遍历以T-lchild和T-rchild为根 指针的子树。由于各子树的遍历和整个二叉树的遍历方式相同，因此，各子 树的遍历可递归调用二叉树的遍历算法。void PreOrder ( BiTree *T) if ( T ) visite ( T );preorder ( T-lchild );preorder ( T-

20、rchild );) ) 三.构建一棵树 一棵树(或树形)是一个有限非空的结点集合T,其中：(1)有个被称为根的结点，记为root (T)；(2)其余结点被分成m=0个不相交的集合Ti, T2,Tm,且又都是树。树Ti, T2, ,Tm,成为的root (T)子树每一棵树的根都和root有一条边相连。此次课程设为了实现树与二叉树的转化，需定义构建一棵树，用于实现树转 化为二叉树的算法，其具体的算法如下所示:void CreateTree(TreeNode* &root)TreeNode *e = TreeNode *f = TreeNode *b = b-child0= b-childl二 T

21、reeNode *g 二 TreeNode *d =TreeNode *e = TreeNode *f = TreeNode *b = b-child0= b-childl二 TreeNode *g 二 TreeNode *d =new TreeNode ( E new TreeNode ( F new TreeNode B e;f；new TreeNode C G new TreeNode ( I)0)0)2)d-child0= g;TreeNode *c 二 new TreeNode(J C ,0);1)；0);root = new TreeNode C A，, 3); root-child0 = b;root-childl = c;root-child2 = d; 2. 4程序流程图根据课程设计要求，构思思路，为了实现树与二叉树的转化我们构建树和一 叉树的结构体，开辟内存空间，借助队列实现转化，其程序流程图如下：图2-9程序流程图