《数据结构与算法》课程设计报告-树与二叉树转换的实现

数据结构与算法课程设计成果报告树与二叉树转换的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录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 课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目需求分析本程序的主要功能是进行树与二叉树的转换，其中包含树的结构体的建立，树队列的结构体的建立，以及对树与二叉树的遍历，其中包含递归算法的使用，还有树队列和二叉树队列的初始化、判断是否为空、入队和出队等操作，其中队列能为二叉树遍历提供先进先出的访问条件。2.2 存储结构设计树是一种非线性的数据结构树的元素之间是一对多的层次关系，常用的有三种存储结构，分别是：双亲表示法，孩子链表表示法，孩子兄弟表示法。实现：每个结点含两个域：数据域：存放结点本身信息。双亲域：指示本结点的双亲结点在数组中位置。本程序的存储结构为双亲表示法和兄弟表示法，具体如下： 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 算法描述将树转换成二叉树：加线：在兄弟之间加一连线。抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系。旋转：以树的根结点为轴心，将整树顺时针转45。具体如图2-2所示。图2-2 树转化为二叉树将二叉树转换成树： 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子沿分支找到的所有右孩子，都与p的双亲用线连起来 。 抹线：抹掉原二叉树中双亲与右孩子之间的连线。 调整：将结点按层次排列，形成树结构。具体如图2-3所示。图2-3 二叉树转化为树2.4 程序流程图设计程序的第一步是创建树，即数的结构体的建立，然后采用递归法法进行树的先序遍历，先遍历根结点，输入树的结点数量，孩子结点及其父亲结点的数据，建立数队列、二叉树队列。采用结构体指针数组，存放结点的地址，完成树与二叉树队列的初始化、入队、判空、出队等操作。具体流程如下图2-4。开始创建树建立数队列、二叉树队列树的遍历树、二叉树队列出队树、二叉树队列是否为空初始化数队列二叉树队列数对列、二叉树队列入队输入树结点数据树转化为二叉树二叉树遍历主函数输出转换成二叉树后的遍历结果结束2-4 程序流程图2.5 主要程序说明（1）存储结构：typedef struct st1/树结点的类型 char data;/数据域，采用char星 struct st1 *childrenDEGREE;/指向孩子结点的指针域CTreeNode;typedef struct 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);/递归先序遍历 （3）设计程序使之能够进行二叉树树的先序遍历，运用递归调用。具体设计代码如下：void Preorder(BTreeNode *T) if(T) coutdatalchild); Preorder(T-rchild); （4）设计程序将树转化为二叉树，这是程序能否完成的关键，也是主要的程序段，具体设计代码如下：void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/树转化为二叉树ctroot指向树的根结点，btroot,指向二叉树的根。 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes;/辅助队列 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(VisitedCTreeNodes,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-rchild=p;/作为上一个兄弟结点的右孩子 LastSibling=p; addQueueCTree(VisitedCTreeNodes,ctnode-childreni);/树节点进队列 addQueueBTree(VisitedBTreeNodes,p);/二叉树节点进门队列 3 程序清单#includeusing namespace std;#include#define DEGREE 5 /树的高度#define NULL 0#define QUEUESIZE 10#define MAX_NODE_NUM 100typedef struct st1/树结点的类型 char data;/数据域，采用char星 struct st1 *childrenDEGREE;/指向孩子结点的指针域CTreeNode;typedef struct st2 char data;/数据域 struct st2 *lchild,*rchild;/左右孩子结点的指针BTreeNode;CTreeNode *SearchCTree(CTreeNode *root ,char data) int i; CTreeNode *returnNode; if(root-data=data) return root; else for(i=0;ichildreni=NULL) return NULL; else returnNode=SearchCTree(root-childreni,data);/递归查找 if(returnNode!=NULL) return returnNode; CTreeNode *CreateSTree() int i,j,k; char data, parent; CTreeNode *root,*parentNode,*node; coutj; if(j=0) return NULL;/空树，结束函数 coutdata; fflush(stdin); root=(CTreeNode *)malloc(sizeof(CTreeNode); root-data=data; for(i=0;ichildreni=NULL; for(i=2;i=j;i+)/依次输入每个结点的信息 cout请输入idataparent;/切记当以%c号格式输入数据时候，不要输入空格 fflush(stdin); node=(CTreeNode *)malloc(sizeof(CTreeNode); node-data=data; for(k=0;kchildrenk=NULL; /printf(验证parent=%cn,parent); parentNode=SearchCTree(root,parent);/查找指定数据的结点 for(k=0;kchildrenk=NULL) parentNode-childrenk=node; break; return root;void preorderTree(CTreeNode *ctroot)/遍历每个节点的操作就是输出该结点的data域 CTreeNode *ctchild; int i; coutdata ;/先遍历根结点 for(i=0;ichildreni; if(ctchild=NULL) break;/孩子结点遍历结束，退出 else preorderTree(ctchild);/递归先序遍历 /树队列结构体类型typedef struct nodeCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear;QueueCTree;/二叉树队列结构类型typedef struct nodeBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址 /struct nodeBTree *next; int BTreeFront,BTreeRear;QueueBTree;/初始化树队列void initQueueCTree(QueueCTree *&q) q=(QueueCTree *)malloc(sizeof(QueueCTree); q-CTreeFront=q-CTreeRear=0;/初始化二叉树队列void initQueueBTree(QueueBTree *&q) q=(QueueBTree *)malloc(sizeof(QueueBTree); q-BTreeFront=q-BTreeRear=0;/树队列元素入队int addQueueCTree(QueueCTree *&q,CTreeNode *ctroot) if(q-CTreeRear+1)%MAX_NODE_NUM=q-CTreeFront)/队满 return 0; q-CTreeRear=(q-CTreeRear+1)%MAX_NODE_NUM; q-CTreeArrayq-CTreeRear=ctroot; return 1;/入队列/二叉树队列元素入队int addQueueBTree(QueueBTree *&q,BTreeNode *btroot) if(q-BTreeRear+1)%MAX_NODE_NUM=q-BTreeFront)/队满 return 0; q-BTreeRear=(q-BTreeRear+1)%MAX_NODE_NUM; q-BTreeArrayq-BTreeRear=btroot; return 1;/入队列/树的队列判空int QueueCTreeEmpty(QueueCTree *q) return(q-CTreeFront=q-CTreeRear);/二叉树队列判空int QueueBTreeEmpty(QueueBTree *q) return(q-BTreeFront=q-BTreeRear);/树队列元素出队CTreeNode *delQueueCTree(QueueCTree *&q) CTreeNode *ctroot; if(q-CTreeFront=q-CTreeRear)/队空 return NULL;/返回空指针 q-CTreeFront=(q-CTreeFront+1)%MAX_NODE_NUM; ctroot=q-CTreeArrayq-CTreeFront; return ctroot;/返回结点/二叉树队列元素出队BTreeNode *delQueueBTree(QueueBTree *&q) BTreeNode *btroot; if(q-BTreeFront=q-BTreeRear)/队空 return NULL;/返回空指针 q-BTreeFront=(q-BTreeFront+1)%MAX_NODE_NUM; btroot=q-BTreeArrayq-BTreeFront; return btroot;/返回节点void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/树转化为二叉树ctroot指向树的根结点，btroot,指向二叉树的跟 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes;/辅助队列 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(VisitedCTreeNodes,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-rchild=p;/作为上一个兄弟结点的右孩子 LastSibling=p; addQueueCTree(VisitedCTreeNodes,ctnode-childreni);/树节点进队列 addQueueBTree(VisitedBTreeNodes,p);/二叉树节点进门队列 void Preorder(BTreeNode *T) if(T) coutdatalchild); Preorder(T-rchild); int main() CTreeNode *Tree; BTreeNode *BTree; cout创建一棵树; Tree=CreateSTree(); cout树的先序遍历结果为:; preorderTree(Tree); coutnendl; TreeToBTree(Tree,BTree); cout转换后的二叉树，先序遍历的结果为:endl; Preorder(BTree); coutnendl; return 0;4 测试4.1 测试数据根据树与二叉树的的转换，创建一个树，输入树的结点的数目7，然后输入树根结点的数据a，再依次输入各个孩子结点的数据以及父亲结点的数据ba,ca,da,eb,fc,gc，即可推出树的结构图如图4-1。abdcgfe图4-1树的结构图4.2 测试结果分析 （1） 根据显示，输入树的结点数量，然后根据提示依次输入根节点数据和各个孩子结点的数据以及父亲结点的数据，即可得到如图4-2所示。图4-2 输入结果图（2）输入数据后，就能得到树的先序遍历结果和二叉树的先序遍历结果，如图4-3所示。 图4-3 测试结果图5 总结通过这次课程设计，使我对树和二叉树有了更深的了解和认识，极大地提高了自己的动手能力，尤其是在数据结构的选择和应用、算法的设计与实现方面得到了训练，加深对数据结构基本内容的理解和应用。通过自己动手设计，也发现了一些在课堂上容易疏漏的地方，注意到很多应该注意的细节，在专业知识方面有了很大的提高。但自己在程序设计方面还存在很大不足，今后还需要更加努力。参考文献1朱福喜.Java语言程序设计（第二版）.科学出版社2陈国君等.Java程序设计基础（第二版）.清华大学出版社3谭浩强著.C+语言设计题解与上机指导清华大学出版社4谭浩强著.C+面向对象程序设计 清华大学出版社#includeusing namespace std;#include#define DEGREE 5 /树的高度#define NULL 0#define QUEUESIZE 10#define MAX_NODE_NUM 100typedef struct st1/树结点的类型 char data;/数据域，采用char星 struct st1 *childrenDEGREE;/指向孩子结点的指针域CTreeNode;typedef struct st2 char data;/数据域 struct st2 *lchild,*rchild;/左右孩子结点的指针BTreeNode;CTreeNode *SearchCTree(CTreeNode *root ,char data) int i; CTreeNode *returnNode; if(root-data=data) return root; else for(i=0;ichildreni=NULL) return NULL; else returnNode=SearchCTree(root-childreni,data);/递归查找 if(returnNode!=NULL) return returnNode; CTreeNode *CreateSTree() int i,j,k; char data, parent; CTreeNode *root,*parentNode,*node; coutj; if(j=0) return NULL;/空树，结束函数 coutdata; fflush(stdin); root=(CTreeNode *)malloc(sizeof(CTreeNode); root-data=data; for(i=0;ichildreni=NULL; for(i=2;i=j;i+)/依次输入每个结点的信息 cout请输入idataparent;/切记当以%c号格式输入数据时候，不要输入空格 fflush(stdin); node=(CTreeNode *)malloc(sizeof(CTreeNode); node-data=data; for(k=0;kchildrenk=NULL; /printf(验证parent=%cn,parent); parentNode=SearchCTree(root,parent);/查找指定数据的结点 for(k=0;kchildrenk=NULL) parentNode-childrenk=node; break; return root;void preorderTree(CTreeNode *ctroot)/遍历每个节点的操作就是输出该结点的data域 CTreeNode *ctchild; int i; coutdata ;/先遍历根结点 for(i=0;ichildreni; if(ctchild=NULL) break;/孩子结点遍历结束，退出 else preorderTree(ctchild);/递归先序遍历 /树队列结构体类型typedef struct nodeCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear;QueueCTree;/二叉树队列结构类型typedef struct nodeBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址 /struct nodeBTree *next; int BTreeFront,BTreeRear;QueueBTree;/初始化树队列void initQueueCTree(QueueCTree *&q) q=(QueueCTree *)malloc(sizeof(QueueCTree); q-CTreeFront=q-CTreeRear=0;/初始化二叉树队列void initQueueBTree(QueueBTree *&q) q=(QueueBTree *)malloc(sizeof(QueueBTree); q-BTreeFront=q-BTreeRear=0;/树队列元素入队int addQueueCTree(QueueCTree *&q,CTreeNode *ctroot) if(q-CTreeRear+1)%MAX_NODE_NUM=q-CTreeFront)/队满 return 0; q-CTreeRear=(q-CTreeRear+1)%MAX_NODE_NUM; q-CTreeArrayq-CTreeRear=ctroot; return 1;/入队列/二叉树队列元素入队int addQueueBTree(QueueBTree *&q,BTreeNode *btroot) if(q-BTreeRear+1)%MAX_NODE_NUM=q-BTreeFront)/队满 return 0; q-BTreeRear=(q-BTreeRear+1)%MAX_NODE_NUM; q-BTreeArrayq-BTreeRear=btroot; return 1;/入队列/树的队列判空int QueueCTreeEmpty(QueueCTree *q) return(q-CTreeFront=q-CTreeRear);/二叉树队列判空int QueueBTreeEmpty(QueueBTree *q) return(q-BTreeFront=q-BTreeRear);/树队列元素出队CTreeNode *delQueueCTree(QueueCTree *&q) CTreeNode *ctroot; if(q-CTreeFront=q-CTreeRear)/队空 return NULL;/返回空指针 q-CTreeFront=(q-CTreeFront+1)%MAX_NODE_NUM; ctroot=q-CTreeArrayq-CTreeFront; return ctroot;/返回结点/二叉树队列元素出队BTreeNode *delQueueBTree(QueueBTree *&q) BTreeNode *btroot; if(q-BTreeFront=q-BTreeRear)/队空 return NULL;/返回空指针 q-BTreeFro