树与二叉树转换实现13.docx

河南工程学院数据结构与算法课程设计成果报告树与二叉树转换实现2014年12月29日2. 5测试程序说明该程序是为将数据结构中的树转换为二叉树结构，实现数据在结构转换中 的交替传递功能。运行程序，依次输入树的总结点数量，根节点，第二个结点及其父亲结点, 第三个结点及其父亲结点，直到输入所有结点。计算机会根据所编写的程序，自动为数据分配储存空间，并将数据分配到 二叉树相应的结点位置，最后将生成的二叉树以先序遍历的方式在屏幕上显示出 来。将程序运行结果和预期结果相比拟，分析程序漏洞、错误，发现问题所在, 致力改良程序。使程序更加合理，更加简便。3程序清单/*树和二叉树的结构体*/typedef struct stl 树节点的类型char data ;数据域，采用char星struct stl *childrenDEGREE;指向孩子节点的指针域CTreeNode;typedef struct st2char data;数据域struct st2 *lchild, *rchild;左右孩子节点的指针BTreeNode;/*查找树的节点*/CTreeNode *SearchCTree(CTreeNode *root , char data) int i;CTreeNode *returnNodc;if (root->data=data) return root;else for (i=0;iDEGREE;i+)if (root->chi1dreni二二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;printf (请输入树的节点的数量:);scanf (d，&j);ff lush (stdin); 清除键盘缓存if(j=0) return NULL;空树，结束函数 printf (请输入根节点的数据:)； scanf &data);fflush(stdin);root= (CTreeNode *)malloc(sizeof(CTreeNode); root->data=data;for(i=0;i<DEGREE;i+)root->chiIdreni=NULL;for(i=2 ;i<=j; i+) 依次输入每个节点的信息printf (请输入第%d个节点的数据及其父节点的数据:，i);scanf (z，%d%d，z, &data, &parent);fflush(stdin);node=(CTreeNode malloc(sizeof(CTreeNode);node->data=data;for (k=0;k<DEGREE;k+)node->childrenk=NULL;parentNode=SearchCTree (root, parent); 查找指定数据的节点 for(k=0;k<DEGREE;k+)if(parentNode->childrenk=NULL) parentNode->chi1drenk=node;break;) return root;)/*树的遍历*/void preorderTree (CTreeNode *ctroot) CTreeNode *ctchild;printf ctroot->data);for(int i=0;-DEGREE; i+) ctchild=ctroot->chiIdreni;if (ctchild=NULL)break;else preorderTree(ctchiId);)树队列结构体类型typedef struct nodeCTreeCTreeNode *CTreeArrayMAX_NODE_NUM;i nt CTreeFront, CTreeRear;QueueCTree;二叉树队列结构类型typedef struct nodeBTreeBTreeNode *BTreeArrayMAXNODENUM;/struct nodeBTree *next;int BTreeFront, BTreeRear;QueueBTree;/*初始化树队列*/void initQueueCTree(QueueCTree *&q)遍历每个节点的操作就是输出该节点的data域先遍历根节点依次先序遍历孩子节点孩子节点遍历结束，退出递归先序遍历结构体指针数组，存放节点的地址结构体指针数组，存放节点的地址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+l) %MAX_NODE_NUM=q->CTreeFront) 队满 return 0;q->CTreeRear=(q->CTreeRear+l)%MAX_NODE_NUM;q->CTreeArrayq->CTreeRear=ctroot;return 1;入队列)二叉树队列元素入队int addQueueBTree(QueueBTree &q,BTreeNode *btroot) if(q->BTreeRear+l)%MAX_NODE_NUM=q->BTreeFront)return 0;q->BTrecRcar=(q->BTrccRcar+l)%MAX_NOI)E_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+l)%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+l)%MAX_NODE_NUM; btroot=q->BTreeArrayq->BTreeEront;10return btroot;返回节点/*树转化为二叉树*/void TreeToBTree(CTreeNode *ctroot, BTreeNode *&btroot) / ctroot 指向树的根节点，btroot 指向 二叉树的跟QueueCTree *VisitedCTreeNodes;QueueBTree *Visi tedBTreeNodes;辅助队列initQueueCTree(VisitedCTreeNodes); initQueueBTree (VisitedBTreeNodes);初始化队列CTreeNode *ctnode; BTreeNode *btnode, *p, *LastSibling; 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=dclQueueBTrce(VisitedBTreeNodes);二叉树节点出队for(int i=O;i<DEGREE;i+) 访问节点所有的孩子节点if (c tnode->ch i 1 dren i =NULL)孩子节点访问完毕break;p= (BTreeNode *)malloc(sizeof (BTreeNode);分配二叉树节点p->data=ctnode->childrcni->data;p->Ichiid=p->rch i1d=NULL;if(i=0)1)皿0(10->1(±11(1印；长子，作为父节点的左孩子else LastSibl ing->rchi 1 d=p;作为上一个兄弟节点的右孩子LastSibling=p; addQueueCTree(VisitedCTreeNodes, ctnode->childreni); 树节点进队列addQueueBTree (VisitedBTreeNodes, p);二叉树节点进门队列) ) /*二叉树的遍历*/ void Preorder(BTreeNode *T) ifCT) printf(2d，T->data); Preorder (T->lchiId); Preorder (T->rchiId); ) )114测试4.1测试数据将树设为5个结点，其结点数据分别为5、4、3、2、lo其树结构图如图4. 1。测试结果如图4. 3。再将树设为6个结点,数据为10、5、8、12、3、1.如图4.2o测试结果如图4. 4。图4.1数据测试4. 2测试结果分析根据测试数据，得到程序运行结果。1音奇里I请输S据及其父书点的姜攵据=4青辅T入第3个节点的数据及茸父节点的数据=3 落铀入第4个节点的数据及其父节点的数据=2 %输入第5个布点的数据及箕父节点的数据=A 3瞿辕音翥翌晏篇詈毙岸弱筐的结果为=5 4 3 2 XP>*ess any key to corwtz dlrwue图4, 3测试结果时茄树的蜃籥灸轧;覆普及其父节点的数据=5± 0请输入第3个节点的数据及箕父节点的数据=8翟桐入第d个节点;的数据及其父节点的数据=12 1.0请询入第S个节点的数据及其父节点的数据=3 %输入第6个节点的数据及其父节点的数据=X粤辕春蕾翌烫箫髻毙译需曷苗蠢果为5 8 P*e s s any keg t o contdLnue±X2图4.4测试结果根据测试结果发现程序能完成树与二叉树的转换，基本上能实现实验任务的 要求，但是程序在一些方面不太完善，仍然存在有缺陷，比方不能以图的形式将 二叉树显示出来，不够清晰明朗。同时在输出二叉树先序遍历的时候有时候会出 现一些问题。可能会影响人的判断。125总结本次课程设计任务主要是树、二叉树构建以及树和二叉树的转换方法，期间 运用遍历和队列的知识，基本上囊括整本数据结构的要点，如果能熟练运用, 轻松编程，书上的知识都基本上都能掌握。在本次课程设计任务中，我发现有许多知识都未能做到融会贯通，未能完全 掌握，导致设计程序中有些地方不能到达理想的要求，使程序在某些方面存在缺 陷或者问题。通过本次设计任务我发现了许多学习中的缺乏，在同学和老师点帮助下完成 任务，使我弥补知识漏洞，填充知识空白。同时我也明白理论知识不能当做动手 能力，只有同时拥有理论知识以及动手能力，才会是一个合格的程序编写员。13参考文献1严蔚敏等，数据结构（C语言版），清华大学出版社2徐子珊，算法设计、分析与实现（第三版），人民邮电出版3张乃孝，算法与数据结构（第二版），高等教育出版社4杨勇虎，数据结构（C语言版），东软电子出版社5张世和，数据结构习题解析与实训，清华大学出版社1415题目树与二叉树实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:1课程设计目标与任务11.1课程设计目标11. 2课程设计任务12分析与设计21.1 题目分析22. 2存储结构设计21.1 3算法描述42.4 程序流程图62.5 测试程序说明73程序清单84测试124.1测试数据124. 2测试结果分析125总结13参考文献141课程设计目标与任务1.1课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教 学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设 计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工 作方法学生通过数据结构课程设计各方面得到锻炼：(1)能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算 法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决 问题的有效算法；(2)通过上机实习，验证自己设计的算法的正确性，学会有效利用基本调 试方法，迅速找出程序代码中的错误并且修改；(3)培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进 一步提高程序设计水平；(4)尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来,将复杂的运行过程以动态方式显示出来，获得算法的直观感受。 1. 2课程设计任务设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：(1)实现树与二叉树的转换；(2)最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来，将复杂的运行过程以动态方式显示出来；(3)给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2分析与设计1 .1题目分析课程设计的最终目标是实现树与二叉树的转换，要实现树与二叉树的转换, 首先需要创立一个树，设立节点，并将节点赋值，本实验只要求使用者以数字输 入。然后需要将树的数据进行遍历，以便后期实现树转换为二叉树。构建一个数 队列与一个二叉树队列，依次进行树队列与二叉树队列的入队与出队。实现二叉 树的数据遍历，转换节点位置。最终实现树与二叉树的转换。将转换后的二叉树 进行遍历，输出遍历后的数据，确保转换成功。2 . 2存储结构设计二叉树的存储结构有顺序存储结构与链式存储结构。顺序存储结构的实现 是按满二叉树的结点层次编号，依次存放二叉树中的数据元素。其特点是结点间 的关系蕴含在其存储位置中，但是，顺序储存结构浪费存储空间。所以顺序存储 结构只适用于存满二叉树和完全二叉树。abcde0000fg123456789 10 11图2. 1二叉树顺序存储结构设计不同的结构特点课构成不同形式的链式存储结构。由二叉树的定义可 知，二叉树的结构由一个数据元素和分别指向其左右子树的两个分支构成，那么表 示二叉树的链表中的结点至少包含3个域：数据域和左右指针域。有时，为了方 便找到双亲，那么在结点结构中增加一个指向其双亲结点的指针域。利用这种结点 结构所得二叉树的存储结构分别称为二叉链表和三叉链表。LchilddatarchidLchilddataparentrchild图2. 2二叉树链式存储结构树有三种存储结构。(1)双亲表示法。每个结点含两个域，数据域，存放结点本身信息；双亲 域，指示本结点的双亲结点在数组中的位置。# define MAX TREE SIZE 100 typedef struct PTnode TElemtype data; int parent; PTnode; 结点类型 typedef struct (PTNode nodesMAX_TREE_SIZE; int n;结点个数 PTree; 树类型(2)孩子链表表示法。typedef struct CTNode int child;struct CTNode *next;双亲结点: *ChildPtr; typedef struct Elem data; ChildPtr firstchild;孩子链的头指针 CTBox;树结构:树结构:typedef struct CTBox nodesMAX_TREE_SIZE;int n, r;结点数和根结点的位置 CTree;A图2. 3孩子兄弟表示法(3)孩子兄弟表示法。 用二叉链表作树的存储结构, 链表中没两个结点的两个指 针分别指向其第一个孩子结 点和下一个兄弟结点。但是孩 子兄弟表示法破坏了树的层 次。图2. 4树与二叉树存储结构变化此处使用兄弟表示法及链式存储结构表示程序中数据存储结构的变化。2. 3算法描述创立一个树的结构体，从键盘输入数据存入数组；创立一个二叉树的结构 体，把树队列中出来的数存入数组中。CTreeNode *CreateSTree(), int addQueue BTree (QueueBTree *&q, BTreeNode *btroot)。遍历树的递归算法，假设树为空，那么空操作，否那么(1)访问根节点；(2) 依次遍历孩子节点；(3)遍历结束；void preorderTree(CTreeNode *ctroot初始化树队列，树队列元素入队、出队；void initQueueCTree(QueueCTree *&q), int addQueueCTree (QueueCTree *&q,CTreeNode *ctroot), CTreeNode*delQueueCTree (QueueCTree *&q)。初始化二叉树队列，初始化二叉树元素入队、 出队；void initQueueBTree (QueueBTree *&q), int addQueueBTree (QueueBTree *&q, BTreeNode *btroot), BTreeNode *delQueueBTree(QueueBTree *&q)。树与二叉树的转化算法，转换时结点的第一个孩子变为它的左孩子，兄弟 结点变为它的右孩子；void TreeToBTree (CTreeNode *ctroot, BTreeNode *&btroot)o主函数调用：int main() CTreeNode *Tree;BTreeNode *BTree;printf (创立一棵树n);Tree=CreateSTree();printf (树的先序遍历结果为:);preorderTree(Tree);printf(n)；TreeToBTree(Tree, BTree);printf(转换后的二叉树，先序遍历的结果为:)；Preorder(BTree);printf (n);return 0;)将树转换为二叉树的方法：（1）将树的兄弟之间加上一条线。（2）对于 每个结点，除了其左孩子以外，去除与其余孩子之间的关系。（3）以树的根节 点为轴心，将整棵树顺时针转45度角。图2. 5树转化二叉树方法示意52. 4程序流程图设计树与二叉树的转换程序，需要构建树和二叉树的结构体，初始化队列， 程序在计算机内进行，需要为数据分配存储空间，程序才不会出错，接着按照树 转换为二叉树的方法，依次将树中的数据元素分配到二叉树的相应结点。图2. 6树转换二叉树流程图