《《数据结构与算法》课程设计报告-树与二叉树转换的实现》由会员分享，可在线阅读，更多相关《《数据结构与算法》课程设计报告-树与二叉树转换的实现（32页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法课程设计成果报告树与二叉树转换的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教
2、师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述32.4 程序流程图42.5 测试程序说明63 程序清单104 测试164.1 测试数据164.2 测试结果分析165 总结18参考文献19附 录201 课程设计目标与任务1.1 课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各
3、方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树
4、的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目需求分析本程序的主要功能是进行树与二叉树的转换，其中包含树的结构体的建立，树队列的结构体的建立，以及对树与二叉树的遍历，其中包含递归算法的使用，还有树队列和二叉树队列的初始化、判断是否为空、入队和出队等操作，其中队列能为二叉树遍历提供先进先出的访问条件。2.2 存储结构设计树是一种非线性的数据结构树的元素之间是一对多的层次关系，常用的有三种存储结构，分别是：双亲表示法，孩子链表
5、表示法，孩子兄弟表示法。实现：每个结点含两个域：数据域：存放结点本身信息。双亲域：指示本结点的双亲结点在数组中位置。本程序的存储结构为双亲表示法和兄弟表示法，具体如下： typedef struct st1/树结点的类型 char data;/数据域，采用char struct st1 *childrenDEGREE;/指向孩子结点的指针域CTreeNode;typedef struct st2 char data;/数据域 struct st2 *lchild,*rchild;/左右孩子结点的指针BTreeNode;存储结构图如图2-1。2-1存储结构图2.3 算法描述将树转换成二叉树：加线
6、：在兄弟之间加一连线。抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系。旋转：以树的根结点为轴心，将整树顺时针转45。具体如图2-2所示。图2-2 树转化为二叉树将二叉树转换成树： 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子沿分支找到的所有右孩子，都与p的双亲用线连起来 。 抹线：抹掉原二叉树中双亲与右孩子之间的连线。 调整：将结点按层次排列，形成树结构。具体如图2-3所示。图2-3 二叉树转化为树2.4 程序流程图设计程序的第一步是创建树，即数的结构体的建立，然后采用递归法法进行树的先序遍历，先遍历根结点，输入树的结点数量，孩子结点及其父亲结点的数据，建立数
7、队列、二叉树队列。采用结构体指针数组，存放结点的地址，完成树与二叉树队列的初始化、入队、判空、出队等操作。具体流程如下图2-4。开始创建树建立数队列、二叉树队列树的遍历树、二叉树队列出队树、二叉树队列是否为空初始化数队列二叉树队列数对列、二叉树队列入队输入树结点数据树转化为二叉树二叉树遍历主函数输出转换成二叉树后的遍历结果结束2-4 程序流程图2.5 主要程序说明（1）存储结构：typedef struct st1/树结点的类型 char data;/数据域，采用char星 struct st1 *childrenDEGREE;/指向孩子结点的指针域CTreeNode;typedef stru
8、ct st2 char data;/数据域 struct st2 *lchild,*rchild;/左右孩子结点的指针BTreeNode;（2）设计程序使之能够进行树的先序遍历，采用递归算法。具体设计代码如下：void preorderTree(CTreeNode *ctroot)/遍历每个节点的操作就是输出该结点的data域 CTreeNode *ctchild; int i; coutdata ;/先遍历根结点 for(i=0;ichildreni; if(ctchild=NULL) break;/孩子结点遍历结束，退出 else preorderTree(ctchild);/递归先序遍历
9、 （3）设计程序使之能够进行二叉树树的先序遍历，运用递归调用。具体设计代码如下：void Preorder(BTreeNode *T) if(T) coutdatalchild); Preorder(T-rchild); （4）设计程序将树转化为二叉树，这是程序能否完成的关键，也是主要的程序段，具体设计代码如下：void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/树转化为二叉树ctroot指向树的根结点，btroot,指向二叉树的根。 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedB
10、TreeNodes;/辅助队列 initQueueCTree(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; addQueueCTree(Vi
11、sitedCTreeNodes,ctroot);/树的跟结点入队 addQueueBTree(VisitedBTreeNodes,btroot);/二叉树的跟结点入队 while(!QueueCTreeEmpty(VisitedCTreeNodes) ctnode=delQueueCTree(VisitedCTreeNodes);/树结点出队 btnode=delQueueBTree(VisitedBTreeNodes);/二叉树节点出队 for(i=0;ichildreni=NULL)/孩子结点访问完毕 break; p=(BTreeNode *)malloc(sizeof(BTreeNode);/分配二叉树结点 p-data=ctnode-childreni-data; p-lchild=p-rchild=NULL; if(i=0) btnode-lchild=p;/长子，作为父结点的做孩子 else LastSibling-rchi
