《数据结构》课程设计-树与二叉树的转换的实现.doc

河南工程学院数据结构与算法课程设计成果报告树与二叉树的转换的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树的转换的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录一、课程设计目标与任务11.1 课程设计目的11.2 课程设计目标11.3 课程设计任务21.4程序分析2二、分析与设计32.1 存储结构设计32.2 算法描述42.3 程序流程图42.4 流程描述5三、主程序清单9四、 程序测试134.1测试数据134.2测试结果分析13五、总结14参考文献15一、课程设计目标与任务1.1 课程设计目的通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。1.2 课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼。主要目标：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能的借助语言环境实现图形显示功能，以便于将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.3 课程设计任务根据提供的实习题目，认真完成软件设计的全部过程，并以最终软件设计成果来证明其独立完成实际任务的能力，从而，反映出理解和运用数据结构与算法的水平和能力，最后完成软件设计和程序调试并提交文档：课程设计报告书，报告书中包含设计的算法及部分程序代码。主要任务：设计树与二叉树转换的相关函数库，以便在程序设计中调用。（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.4程序分析该课程设计需要实现树与二叉树的相互转换，明白二者的转换关系，二叉树的根即为树的根，二叉树的左子树为树的左子树，从根开始一直向右，遇到的右子树均依次作为树的子树。将树转换为二叉树，关键是把n个分支变为两个分支，步骤如下：（1）保留所有结点与其左子结点的链接；（2）打断所有结点原本与右结点的链接；（3）连结所有兄弟结点（拥有同一个父结点的子结点）；（4）将兄弟结点顺时钟转45，树中右侧兄弟变为二叉树中该结点右子树。将二叉树转换为树，步骤如下：（1）二叉树的根即为树的根；（2）打断所有结点与其右子树的链接；（3）二叉树的左子树为树的左子树，从根开始一直向右，遇到的右子树均依次作为树的子树(二叉树中结点的右子树中变为该结点右侧的兄弟)。二、分析与设计2.1 存储结构设计引入头文件：#include #include #include 设置常量：#define MAX_TREE_SIZE 100一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下：/*树的双亲表示结点结构定义*/typedef struct int data; int parent; /双亲位置域PTNode;/*双亲表示法树结构*/typedef struct PTNode nodeMAX_TREE_SIZE; int count; /根的位置和节点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct nodeint data;struct node *firstchild;struct node *rightsib;BTNode,*BTree;2.2 算法描述先遍历多叉树，将所有结点得到，然后结据相应的二叉树的规则构造二叉树就行了，将多叉树的第一个儿子结点作为二叉树的左结点，将其兄弟结点作为二叉树的右结点。利用指针，遍历算法，队列的入队出队等算法，实现将树的根结点作为二叉树的根结点的操作，一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的，只是两个指针域的名称及解释不同而已，且树与其对应的生成二叉树的前序遍历是相同的，可以用此来验证由树所转换成的二叉树是否正确。2.3 程序流程图该程序是先建立树，再以树为基础，将树转换成二叉树。该程序的流程是建立树，利用队列，递归，指针等，将树的根结点变为二叉树的根结点，进行树到二叉树的转换，程序的最终目的是根据输入的树的接点，孩子结点及其父亲结点，生成二叉树，将树的先序遍历结果和二叉树的先序遍历的结果输出。如图主菜单 树的信息图二叉树的信息图 输入信息生成树 输入树的结点数输入孩子结点及其父亲结点 输出树的前序遍历输出二叉树的前序遍历2.4 流程描述（1）输入关于树的结点后，遍历每个结点的操作就是输出该结点的data域,首先先遍历树的根结点，再先序遍历树的孩子结点。void preorderTree(CTreeNode *ctroot)/遍历每个结点的操作就是输出该结点的data域 CTreeNode *ctchild; int i; coutdata ;/先遍历根结点 for(i=0;ichildreni; if(ctchild=NULL) break;/孩子结点遍历结束，退出 else preorderTree(ctchild);/递归先序遍历（2）定义BTreeNode *BTreeArrayMAX_NODE_NUM结构体指针数组，用于存放结点的地址，开始初始化树队列，二叉树队列，并且分别将树和二叉树的元素分别进行入队操作，在元素进入队列时要进行判断队列，看是否为满。然后再把树队列元素出队，要进行队列是否为空的判断，利用指针返回结点的值，然后进行二叉树队列元素出队，返回空指针后返回结点。该段程序的关键是元素的出队入队操作。typedef struct nodeBTreeBTreeNode *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;/入队列（3）下面是树转换成二叉树的关键操作，树转换成二叉树时利用ctroot指向树的根结点，利用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); 三、主程序清单#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 st2char data;/数据域 struct st2 *lchild,*rchild;/左右孩子结点的指针BTreeNode;CTreeNode *SearchCTree(CTreeNode *root ,char data)int i; CTreeNode *returnNode; if(root-data=data) return root;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; fflush(stdin); node=(CTreeNode *)malloc(sizeof(CTreeNode); node-data=data; for(k=0;kchildrenk=NULL; 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测试数据创建一个树，输入树的结点数量，再分别输入孩子结点和其父亲结点的数据，程序运行，输出树的先序遍历结果和转换后二叉树的先序遍历的结果，输入数据。4.2测试结果分析输入树的结点数，孩子结点及其父亲结点的数据后，程序输出树的先序遍历结果和转换后的二叉树的先序遍历的结果。五、总结本次选的课题是二叉树的遍历，因为本学期所学的就是二叉树等数据结构，所以认为比较适合。刚开始认为会很简单，但到后来就出现一些难以解决的问题，就和同学讨论，并查阅相关资料。经过慢慢的调试，最终测试成功。这次课程设计让我所学到的数据结构知识发挥的淋漓尽致，而且还拓展了我的知识面，使我更加熟练的掌握各种方法。总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对数据结构更加了解。参考文献1严蔚敏等.数据结构（第三版）.清华大学出版社2彭军等.数据结构与算法（第一版）.机械工业出版社3MarkAllenWeiss .数据结构与算法分析（C语言）（第二版）.机械工业出版社4Sartaj Sahni.数据结构、算法与应用（C+语言描述）（第一版）.机械工业出版社5Thomas H.Cormen.算法导论（第二版）.机械工业出版社#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 st2char data;/数据域 struct st2 *lchild,*rchild;/左右孩子结点的指针BTreeNode;CTreeNode *SearchCTree(CTreeNode *root ,char data)int i; CTreeNode *returnNode; if(root-data=data) return root;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; fflush(stdin); node=(CTreeNode *)malloc(sizeof(CTreeNode); node-data=data; for(k=0;kchildrenk=NULL; 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-BTreeArra