《树与二叉树转换实现-数据结构与算法》课程设计成果报告》由会员分享，可在线阅读，更多相关《树与二叉树转换实现-数据结构与算法》课程设计成果报告（21页珍藏版）》请在金锄头文库上搜索。
1、河南工程学院数据结构与算法课程设计成果报告树与二叉树转换实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成
2、 绩指导教师评语： 日期： 年 月 日目录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3课程设计目的22 分析与设计32.1 题目分析32.2 存储结构42.3 算法描述62.4 程序流程82.5 测试程序93 程序清单104 测试144.1 测试数据144.2 测试结果分析145 总结17参考文献181 课程设计目标与任务1.1 课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程
3、设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与
4、二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3课程设计目的通过本次课程设计，使我们在数据结构的选择与应用、算法的设计与实现方面得到很好训练，加深对数据结构基本内容的理解和灵活应用。在程序设计方法及上机操作方面受到比较系统的、严格的训练，培养我们软件工作时所需要的动手能力。同时，数型结构是一类重要的非线性数据结构，其中树和二叉树最为常用，所以掌握好树与二叉树的各种函数及其相互间的转换非常重要。2 分析与设计数据结构是计算机存储、组织数据的
5、方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。树是数据结构中比较重要的结构之一，是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很像自然界中的树那样。树结构不仅在客观世界中广泛存在，在计算机领域中也得到广泛应用。一切具有层次关系的问题都可用树来描述。2.1 题目分析树是一种重要的非线性数据结构，掌握二叉树的两种基本的存储结构，及各种操作的算法实现（建立、遍历）以及应用是非常重要的。树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外的所有结点都有且只有一个直接前趋。二叉树的特点是：每个结点至多有两棵子树（即二叉树中
6、不存在度大于2的结点），并且，二叉树的子树有左右之分，其次序不能颠倒。（1）树转换成二叉树如果F=T1,T2,.,Tm是森林，则可按如下规则转换成一棵二叉树B=（root，LB，RB）。若F为空，即m=0，则b树为空树；若F非空，即m!=0，则B的根root即为森林中第一棵树的根root（T1）；B的左子树LB是从T1中根结点的子树森林F1= T11,T22,.,T1m1 转换而成的二叉树；其右子树RB是从森林F=T1,T2,.,Tm转换而成的二叉树。（2）二叉树转换成森林如果B=（root，LB，RB）F=T1,T2,.,Tm是一棵二叉树，则可按如下规则转换成森林F=T1,T2,.,Tm。若
7、B为空，则F为空。若B非空，则F中第一棵树T1的根ROOT（T1）即为二叉树的B的根root；T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除t1之外的其余树组成的森林F=T1,T2,.,Tm是由B的右子树RB转换而成的森林。运用递归定义容易写出相关转换的递归算法。2.2 存储结构1树的存储结构有很多种形式。下面介绍常用的三种常用的存储结构：（1）双亲数组表示法这种存储结构是利用每个结点（根结点除外）只有唯一双亲的特点，用一维数组来存储一棵一般的树。，如图11、12即为一棵树及其双亲表示。在这种结构中，寻找一个结点双亲的时候，只要访问它的parent域，即可得到它的双亲的存储
8、位置。但是，要寻找一个结点的孩子时，则需遍历整个数组。ABCDFJIHGE 图2-1 双亲表示 图2-2 树 （2）结点定长的孩子链表表示法如下图2-3所示，一个三叉树，可以用三叉链表储存。其结构特点是：一个数据域和三个指针域，指针域用于指向节点的各个孩子节点。 图2-3 孩子链图 （3）孩子兄弟二叉链表表示法孩子兄弟链表作为存储结构，其特点是：一个数据域和两个指针域。其中一个指针指向它的第一个孩子节点，另一个指向它的兄弟结点。如图2-4所示： 图2-4 孩子-兄弟图2二叉树的存储结构也有好多种，下面介绍几种常用的二叉树的存储结构（1）二叉树得顺序存储结构是将二叉树的所有结点， 按照一定的次序
9、，存储到一片连续的存储单元中。 因此，必须将结点排成一个适当的线性序列， 使得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。 这种结构特别适用于近似满二叉树。 在一棵具有n个结点的近似满二叉树中， 我们从树根起，自上层到下层，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉树结构的线性序列。（2）二叉树的二叉链表存储适用于普通二叉树，每个结点除了数据外，还有分别指向左右孩子结点的指针，存储n个结点有n+1个空指针域，存储密度小于顺序存储，但是适用范围广，缺陷是正常遍历只能从双亲向孩子，退回来一般需要借助栈。typedef int TElemType; typedef struc
10、t BiTNode TElemType data; struct BiTNode *lchild,*rchild; BiTNode,*BiTree; 被封装好的每个节点，都有一个数据域data和两个指针域 *lchild,*rchild分别指向左右子树。（3）二叉树的三叉链表同样适用于普通二叉树，结点除了数据外，还有左右孩子与双亲的指针，存储密度低于二叉链表，但是可以非常方便地在二叉树中遍历，不需要其他辅助工具。树是对数据进行的一种抽象的描述，具体的实现方法是链表，计算机本身的存储构造就是开辟一个新空间，连续的，或者不连续的，然后我们就要思考如何合理的利用这些空间，节约空间或者节约时间。而现在
11、这种存储方法用二叉树的这种抽象形式表现出来，容易让人容易理解一些而已，所以对于二叉树一般采用二叉链表这样的存储方式。 2.3 算法描述树的初始化函数（双亲法和孩子结点法两种），建树函数，输出树函数，输得遍历（递归和非递归两种）。引入头文件：#include#include设置常量：#define DEGREE 5 /树的高度#define NULL 0#define QUEUESIZE 10#define MAX_NODE_NUM 100树转换成二叉树的方法。一般是把树当前结点的的孩子当成左子树(或右子树)，层层转换而得到一个新的二叉树。 根据树(森林)转换二叉树的方法，逆向回去，就可以得到二
12、叉树转换树的算法。先构建树和二叉树的结构体，数据域采用char类型。查找树的结点数，如果访问为空则返回NULL，负责放回data。输入数的结点数量、跟结点的数据及结点数据和其父结点数据，构建一个有具体数据的树。根据递归先序遍历树，存入栈、出栈方式储数中的数据。运用相关函数将树转换为二叉树。void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/树转化为二叉树ctroot指向树的根节点，btroot,指向二叉树的根。 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes; i
13、nitQueueCTree(VisitedCTreeNodes); initQueueBTree(VisitedBTreeNodes); CTreeNode *ctnode; BTreeNode *btnode,*p,*LastSibling; int i; btroot=(BTreeNode *)malloc(sizeof(BTreeNode); btroot-data=ctroot-data; btroot-lchild=btroot-rchild=NULL;依次数的根结点入队、处队，继而访问所有的孩子结点，孩子结点访问完毕，树转换成二叉树把树当前结点的的孩子当成左子树(或右子树)，层层转换而得到一个新的二叉树。具体实施如下代码所示： for(i=0;ichildreni=NULL) break; p=(BTreeNode *)malloc(sizeof(BTreeNode); p-data=ctnode-childreni-data; p-lchild=p-rchild=NULL; if(i=0)
