数据结构课程设计-树与二叉树转换实现

1、河南工程学院数据结构与算法课程设计成果报告树与二叉树转换实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1342 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩

2、指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12 分析与设计22.1 题目分析22.2 存储结构设计22.3 算法描述42.4 程序流程图62.5 测试程序说明73 程序清单84 测试124.1 测试数据124.2 测试结果分析125 总结13参考文献141 课程设计目标与任务1.1 课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面

3、得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务 设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的

4、转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目分析课程设计的最终目标是实现树与二叉树的转换，要实现树与二叉树的转换，首先需要创建一个树，设立节点，并将节点赋值，本实验只要求使用者以数字输入。然后需要将树的数据进行遍历，以便后期实现树转换为二叉树。构建一个数队列与一个二叉树队列，依次进行树队列与二叉树队列的入队与出队。实现二叉树的数据遍历，转换节点位置。最终实现树与二叉树的转换。将转换后的二叉树进行遍历，输出遍历后的数据，确保

5、转换成功。2.2 存储结构设计二叉树的存储结构有顺序存储结构与链式存储结构。顺序存储结构的实现是按满二叉树的结点层次编号，依次存放二叉树中的数据元素。其特点是结点间的关系蕴含在其存储位置中，但是，顺序储存结构浪费存储空间。所以顺序存储结构只适用于存满二叉树和完全二叉树。图2.1 二叉树顺序存储结构设计不同的结构特点课构成不同形式的链式存储结构。由二叉树的定义可知，二叉树的结构由一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的链表中的结点至少包含3个域：数据域和左右指针域。有时，为了方便找到双亲，则在结点结构中增加一个指向其双亲结点的指针域。利用这种结点结构所得二叉树的存储结构分别

6、称为二叉链表和三叉链表。Lchild data parent rchildLchild data rchid图2.2 二叉树链式存储结构树有三种存储结构。（1）双亲表示法。每个结点含两个域，数据域，存放结点本身信息；双亲域，指示本结点的双亲结点在数组中的位置。# define MAX_TREE_SIZE 100typedef struct PTnode TElemtype data; int parent; PTnode; /结点类型 typedef struct PTNode nodesMAX_TREE_SIZE; int n; /结点个数 PTree; /树类型（2）孩子链表表示法。孩子结

7、点：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;（3）孩子兄弟表示法。用二叉链表作树的存储结构，链表中没两个结点的两个指针分别指向其第一个孩子结点和下一个兄弟结点。但是孩子兄弟表示法破坏了树的层次。 图2. 3 孩子兄弟表示法此处使用

8、兄弟表示法及链式存储结构表示程序中数据存储结构的变化。 图2.4 树与二叉树存储结构变化2.3 算法描述创建一个树的结构体，从键盘输入数据存入数组；创建一个二叉树的结构体，把树队列中出来的数存入数组中。CTreeNode *CreateSTree()，int addQueueBTree(QueueBTree *&q,BTreeNode *btroot)。遍历树的递归算法，若树为空，则空操作，否则（1）访问根节点；（2）依次遍历孩子节点；（3）遍历结束；void preorderTree(CTreeNode *ctroot初始化树队列，树队列元素入队、出队；void initQueueCTree

9、(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)。树与二叉树的转化算法，转换时结点的第一个孩子变为它的左孩子，兄弟结点变为它的

10、右孩子；void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)。主函数调用：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;将树转换为二叉树的方法：（

11、1）将树的兄弟之间加上一条线。（2）对于每个结点，除了其左孩子以外，去除与其余孩子之间的关系。（3）以树的根节点为轴心，将整棵树顺时针转45度角。 图2.5 树转化二叉树方法示意2.4 程序流程图设计树与二叉树的转换程序，需要构建树和二叉树的结构体，初始化队列，程序在计算机内进行，需要为数据分配存储空间，程序才不会出错，接着按照树转换为二叉树的方法，依次将树中的数据元素分配到二叉树的相应结点。开始 构建树结构体构建二叉树结构体初始化树队列，初始化二叉树队列开辟内存空间树队列元素入队，二叉树队列元素入队树队列元素出队，返回结点；二叉树队列元素出队，返回结点分配二叉树结点遍历二叉树，输出数组 结束

12、图2.6 树转换二叉树流程图2.5 测试程序说明该程序是为将数据结构中的树转换为二叉树结构，实现数据在结构转换中的交替传递功能。运行程序，依次输入树的总结点数量，根节点，第二个结点及其父亲结点，第三个结点及其父亲结点，直到输入所有结点。计算机会根据所编写的程序，自动为数据分配储存空间，并将数据分配到二叉树相应的结点位置，最后将生成的二叉树以先序遍历的方式在屏幕上显示出来。将程序运行结果和预期结果相比较，分析程序漏洞、错误，发现问题所在，致力改良程序。使程序更加合理，更加简便。3 程序清单/*树和二叉树的结构体*/ typedef struct st1 /树节点的类型 char data; /数

13、据域，采用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) retu

14、rn 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); fflush(stdin);/清除键盘缓存 if(j=0) return NULL;/空树，结束函数 printf(请输入根节点的

15、数据:); scanf(%d,&data); fflush(stdin); root=(CTreeNode *)malloc(sizeof(CTreeNode); root-data=data; for(i=0;ichildreni=NULL; for(i=2;idata=data; for(k=0;kchildrenk=NULL; parentNode=SearchCTree(root,parent); /查找指定数据的节点 for(k=0;kchildrenk=NULL) parentNode-childrenk=node; break; return root;/*树的遍历*/void

16、preorderTree(CTreeNode *ctroot) /遍历每个节点的操作就是输出该节点的data域 CTreeNode *ctchild; printf(%d,ctroot-data); /先遍历根节点 for(int i=0;ichildreni; if(ctchild=NULL) break; /孩子节点遍历结束，退出 else preorderTree(ctchild); /递归先序遍历/树队列结构体类型typedef struct nodeCTree CTreeNode *CTreeArrayMAX_NODE_NUM; /结构体指针数组，存放节点的地址 int CTreeF

17、ront,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;/初始化二叉树队列v

18、oid 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; re

19、turn 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 QueueB

20、TreeEmpty(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 *delQue

21、ueBTree(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 *V

22、isitedCTreeNodes; QueueBTree *VisitedBTreeNodes; /辅助队列 initQueueCTree(VisitedCTreeNodes); initQueueBTree(VisitedBTreeNodes); /初始化队列 CTreeNode *ctnode; BTreeNode *btnode,*p,*LastSibling; btroot=(BTreeNode *)malloc(sizeof(BTreeNode); /添加开辟内存空间语句 btroot-data=ctroot-data; /树的根节点作为二叉树的根节点 btroot-lchild=b

23、troot-rchild=NULL;addQueueCTree(VisitedCTreeNodes,ctroot);/树的跟节点入队addQueueBTree(VisitedBTreeNodes,btroot);/二叉树的跟节点入队while(!QueueCTreeEmpty(VisitedCTreeNodes) ctnode=delQueueCTree(VisitedCTreeNodes); /树节点出队btnode=delQueueBTree(VisitedBTreeNodes); /二叉树节点出队for(int i=0;ichildreni=NULL) /孩子节点访问完毕 break;

24、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); /二叉树节点进门

25、队列 /*二叉树的遍历*/void Preorder(BTreeNode *T) if(T) printf(%2d,T-data); Preorder(T-lchild); Preorder(T-rchild); 4 测试4.1 测试数据将树设为5个结点，其结点数据分别为5、4、3、2、1。其树结构图如图4.1。测试结果如图4.3。再将树设为6个结点，数据为10、5、8、12、3、1.如图4. 2。测试结果如图4.4。105 4581232113 图4.1 数据测试 图4.2数据测试4.2 测试结果分析根据测试数据，得到程序运行结果。图4.3 测试结果图4.4测试结果根据测试结果发现程序能完成

26、树与二叉树的转换，基本上能实现实验任务的要求，但是程序在一些方面不太完善，仍然存在有缺陷，比如不能以图的形式将二叉树显示出来，不够清晰明朗。同时在输出二叉树先序遍历的时候有时候会出现一些问题。可能会影响人的判断。5 总结本次课程设计任务主要是树、二叉树构建以及树和二叉树的转换方法，期间运用遍历和队列的知识，基本上囊括整本数据结构的要点，如果能熟练运用，轻松编程，书上的知识都基本上都能掌握。在本次课程设计任务中，我发现有许多知识都未能做到融会贯通，未能完全掌握，导致设计程序中有些地方不能达到理想的要求，使程序在某些方面存在缺陷或者问题。通过本次设计任务我发现了许多学习中的不足，在同学和老师点帮助

27、下完成任务，使我弥补知识漏洞，填充知识空白。同时我也明白理论知识不能当做动手能力，只有同时拥有理论知识以及动手能力，才会是一个合格的程序编写员。参考文献1严蔚敏等，数据结构（C语言版），清华大学出版社2徐子珊，算法设计、分析与实现（第三版），人民邮电出版3张乃孝，算法与数据结构（第二版），高等教育出版社4杨勇虎，数据结构（C语言版），东软电子出版社5张世和，数据结构习题解析与实训，清华大学出版社#include#include#define DEGREE 5 /树的高度#define NULL 0#define QUEUESIZE 10#define MAX_NODE_NUM 100 /*树和

28、二叉树的结构体*/ typedef 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) re

29、turn 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; printf(请输入树的节点的数量:); scanf(%d,&j); fflush(stdin);/清除键盘缓

30、存 if(j=0) return NULL;/空树，结束函数 printf(请输入根节点的数据:); scanf(%d,&data); fflush(stdin); root=(CTreeNode *)malloc(sizeof(CTreeNode); root-data=data; for(i=0;ichildreni=NULL; for(i=2;idata=data; for(k=0;kchildrenk=NULL; /printf(验证parent=%dn,parent); parentNode=SearchCTree(root,parent);/查找指定数据的节点 for(k=0;kc

31、hildrenk=NULL) parentNode-childrenk=node; break; return root;/*树的遍历*/void preorderTree(CTreeNode *ctroot)/遍历每个节点的操作就是输出该节点的data域 CTreeNode *ctchild; int i; printf(%d,ctroot-data);/先遍历根节点 for(i=0;ichildreni; if(ctchild=NULL) break;/孩子节点遍历结束，退出 else preorderTree(ctchild);/递归先序遍历/*结构体类型*/树队列结构体类型typede

32、f 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 initQue

33、ueCTree(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_NO

34、DE_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-BTre

35、eRear=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 NU

36、LL;/返回空指针 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