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

河南工程学院数据结构与算法课程设计成果报告树和二叉树转换的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程 1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转化的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1课程设计目标11.2 课程设计任务12 分析与设计22.1 题目算法分析22.2 存储结构设计32.3 算法描述32.4 程序流程图42.5 算法实现说明83 程序清单124 测试134.1 测试数据134.2 测试结果分析135 总结14参考文献151 课程设计目标与任务1.1 课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务利用本学期所学的数据结构的有关知识，实现树与二叉树相互转换，设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。该课程设计通过实现树与二叉树的转换，理解树与二叉树的相互转化关系，掌握树与二叉树的存储结构的异同，加深对二叉树和树的理解。 2 分析与设计2.1 题目算法分析该课程设计需要实现树与二叉树的相互转换，明白二者的转换关系，二叉树的根即为树的根，二叉树的左子树为树的左子树，从根开始一直向右，遇到的右子树均依次作为树的子树。将树转换为二叉树，关键是把n个分支变为两个分支，步骤如下：（1）保留所有结点与其左子结点的链接；（2）打断所有结点原本与右结点的链接；（3）连结所有兄弟结点（拥有同一个父结点的子结点）；（4）将兄弟结点顺时钟转45，树中右侧兄弟变为二叉树中该结点右子树。将二叉树转换为树，步骤如下：（1）二叉树的根即为树的根；（2）打断所有结点与其右子树的链接；（3）二叉树的左子树为树的左子树，从根开始一直向右，遇到的右子树均依次作为树的子树(二叉树中结点的右子树中变为该结点右侧的兄弟)。2.2 存储结构设计分析树和二叉树的存储结构，二叉树的存储结构如图2.1。图2.1二叉树的存储结构图树是一种非线性的数据结构，树中的元素之间是一对多的层次关系。常用的有三种存储结构，即双亲表示法、孩子表示法、和孩子兄弟表示法。 事实上，一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的，只是两个指针域的名称及解释不同而已,通过图直观的表示了树与二叉树之间的对应关系和相互转换方法。如图2.2。图2.2 树和二叉树的转换图2.3 算法描述先遍历多叉树，将所有结点得到，然后结据相应的二叉树的规则构造二叉树就行了，将多叉树的第一个儿子结点作为二叉树的左结点，将其兄弟结点作为二叉树的右结点。利用指针，遍历算法，队列的入队出队等算法，实现将树的根结点作为二叉树的根结点的操作，一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的，只是两个指针域的名称及解释不同而已，且树与其对应的生成二叉树的前序遍历是相同的，可以用此来验证由树所转换成的二叉树是否正确。2.4 程序流程图该程序是先建立树，再以树为基础，将树转换成二叉树。该程序的流程是建立树，利用队列，递归，指针等，将树的根结点变为二叉树的根结点，进行树到二叉树的转换，程序的最终目的是根据输入的树的接点，孩子结点及其父亲结点，生成二叉树，将树的先序遍历结果和二叉树的先序遍历的结果输出。如图2.3。主菜单树的信息图二叉树的信息图输入信息生成树输入树的结点数输入孩子结点及其父亲结点输出树的前序遍历输出二叉树的前序遍历图2.3 程序流程图2.5 算法实现说明（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); 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;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.1。 图4.1 程序运行图4.2 测试结果分析输入树的结点数，孩子结点及其父亲结点的数据后，程序输出树的先序遍历结果和转换后的二叉树的先序遍历的结果，如图4.2。图4.2 程序运行结果图5 总结 通过本次课程设计，使我对数据结构的理解与应用能力得到很大的提升。但在进行树与二叉树的转换实现的课题中，遇到了一些难以解决的问题，使我认识到自己对数据结构的基本内容还不能理解透彻，还不能进行灵活的运用。同时在程序设计方法与上机操作方面还有很大的不足，在动手能力不断训练的过程中还需要对树与二叉树转换知识的理解进一步加深。然而，面对课题中所遇到的困难，通过查询相关资料、与同学合作探讨、向老师请教，使我在理解的加深与应用的提升中，一步步的改正程序，仔细的检阅课题设计。经过不断的修改与调试，最终完成了老师所布置的任务，成功通过测试。当然，这次课程设计，也使我认识到了学习中的问题所在以及数据结构的深奥与理解应用能力的欠缺。同时，在复习了数据结构中树和二叉树基础知识的同时，也弥补了平时学习中的漏洞。参考文献1谭浩强.C语言程序设计. 清华大学出版社2谭浩强.C+程序设计基础.清华大学出版社3刘遵仁.数据结构.人民邮电出版社4胡学纲.数据结构（C语言版）.高等教育出版社5严蔚敏.数据结构（C语言版）.清华大学出版社6齐德昱.算法与数据结构.清华大学出版社#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; btr