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

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

2、绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目的11.2 课程设计目标11.3 课程设计要求12 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法分析42.4 程序流程图73 程序清单84 测试144.1 测试结果144.2 测试结果分析145 总结16参考文献171 课程设计目标与任务1.1 课程设计目的通过本课程设计，在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。1.2 课程设计目标在设计中逐步提高

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

4、关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目需求分析本程序的主要功能是进行树与二叉树的转换，其中包含树的结构体的建立，树队列的结构体的建立，以及对树和二叉树的遍历，包含递归算法的使用，还有树队列和二叉树队列的初始化、判空、入队和出队等操作，队列能为二叉树遍历提供先进先出的访问条件。2.2 存储结构设计二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个

5、后继。它可采用顺序存储结构和链式存储结构。1.顺序存储结构二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。如图所示： 2.2.1一棵完全二叉树 2.2.2顺序存储结构2.链式存储结构二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。如图所示： 2.2.3一棵二叉树 2.2.4二叉链表存储结构3. 将树转换成二叉树:（1）加线：在兄弟之间加一连线；（2）抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系；（3）旋转：以树的根结点为轴心，将整树顺时针转45。如图2.2.5所示：图2.2.5将树转换成二叉树4.将二叉树转换成树：（1） 加线：若p结

6、点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子沿分支找到的所有右孩子，都与p的双亲用线连起来；（2）抹线：抹掉原二叉树中双亲与右孩子之间的连线；（3）调整：将结点按层次排列，形成树结构。如图2.2.6所示：图2.2.6将二叉树转换成树2.3 算法分析1. 存储结构：typedef struct st1/树结点的类型 char data;/数据域，采用char星 struct st1 *childrenDEGREE;/指向孩子结点的指针域CTreeNode;typedef struct st2 char data;/数据域 struct st2 *lchild,*rchild;/左右孩子结

7、点的指针BTreeNode;存储结构图如图2.3.1所示：图2.3.1存储结构图2. 树队列结构体类型typedef struct nodeCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear;QueueCTree;3. 二叉树队列结构类型typedef struct nodeBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址 /struct nodeBTree *next;

8、 int BTreeFront,BTreeRear;QueueBTree;4. 树队列元素入队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;/入队列5.二叉树队列元素入队int addQueueBTree(QueueBTree *&q,BTreeNode *b

9、troot) 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;/入队列6. 树队列元素出队CTreeNode *delQueueCTree(QueueCTree *&q) CTreeNode *ctroot; if(q-CTreeFront=q-CTreeRear)/队空 return NULL;/返回空指针 q-CTreeFront=(q-CTreeFront+

10、1)%MAX_NODE_NUM; ctroot=q-CTreeArrayq-CTreeFront; return ctroot;/返回结点7. 二叉树队列元素出队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;/返回节点2.4 程序流程图设计程

11、序的第一步是创建树，即数的结构体的建立，然后采用递归法法进行树的先序遍历，先遍历根结点，输入树的结点数量，孩子结点及其父亲结点的数据，建立数队列、二叉树队列。采用结构体指针数组，存放结点的地址，完成树与二叉树队列的初始化、入队、判空、出队等操作。具体流程如下图2.4.1所示：图2.4.1程序流程图3 程序清单#includeusing namespace std;#include#define DEGREE 5 /树的高度#define NULL 0#define QUEUESIZE 10#define MAX_NODE_NUM 100typedef struct st1/树结点的类型 cha

12、r 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 N

13、ULL; 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-

14、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;kchildre

15、nk=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 *CTre

16、eArrayMAX_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

17、 *)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-CTreeRea

18、r=(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 Queue

19、CTreeEmpty(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; ct

20、root=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 *ctroo

21、t,BTreeNode *&btroot)/树转化为二叉树ctroot指向树的根结点，btroot,指向二叉树的跟 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes;/辅助队列 initQueueCTree(VisitedCTreeNodes); initQueueBTree(VisitedBTreeNodes);/初始化队列 CTreeNode *ctnode; BTreeNode *btnode,*p,*LastSibling; int i; btroot=(BTreeNode *)malloc(sizeof(BTre

22、eNode);/添加开辟内存空间语句 btroot-data=ctroot-data;/树的根节点作为二叉树的根结点 btroot-lchild=btroot-rchild=NULL; addQueueCTree(VisitedCTreeNodes,ctroot);/树的跟结点入队 addQueueBTree(VisitedBTreeNodes,btroot);/二叉树的跟结点入队 while(!QueueCTreeEmpty(VisitedCTreeNodes) ctnode=delQueueCTree(VisitedCTreeNodes);/树结点出队 btnode=delQueueBTr

23、ee(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

24、,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转换后

25、的二叉树，先序遍历的结果为:endl; Preorder(BTree); coutnendl; return 0;4 测试4.1测试数据根据树与二叉树的的转换，创建一个树，输入树的结点的数目7，然后输入树根结点的数据a，再依次输入各个孩子结点的数据以及父亲结点的数据ba,ca,da,eb,fc,gc，即可推出树的结构图如图4.1.1所示：图4.1.1树的结构图4.2测试结果分析根据提示，输入数据创建一棵树，输入树的结点的数量为：7输入根结点的数据为：a输入2个孩子结点的数据及其父亲结点的数据：ba输入3个孩子结点的数据及其父亲结点的数据：ca输入4个孩子结点的数据及其父亲结点的数据：da输入5

26、个孩子结点的数据及其父亲结点的数据：eb输入6个孩子结点的数据及其父亲结点的数据：fc输入7个孩子结点的数据及其父亲结点的数据：gc如图4.2.1所示：图4.2.1输入结果图输入数据后，就能得到树的先序遍历结果和二叉树的先序遍历结果，如图4.2.2所示。图4.2.2测试结果图则树的先序遍历结果为：a b e c f g d转换后的二叉树，先序遍历的结果为：a b e c f g d5 总结通过本次课程设计，我发现，有关一个课题的所有知识不仅仅是在课本上，多查阅一些资料能够更好地完成课题，这就需要一种能力，即自学能力。本次选的课题是树与二叉树的转换，通过书本知识和查阅相关资料，经过慢慢的调试，最

27、终调试成功。这次课程设计丰富了我的数据结构知识，扩展了我的知识面，使我更加熟练的掌握各种方法。同时，我也认识到自己的不足，以后会更加努力的学习数据结构。参考文献1数据结构（C语言版）严蔚敏 清华大学出版社 2002 2数据结构-C语言描述 王路群 中国水利水电出版社 2007 3数据结构实验教程（C语言版） 王国钧 清华大学出版社 20094数据结构题集严蔚敏,吴伟民编 清华大学出版社 2002#includeusing namespace std;#include#define DEGREE 5 /树的高度#define NULL 0#define QUEUESIZE 10#define M

28、AX_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

29、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=

30、(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=SearchCT

31、ree(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);/递归先序遍历 /树队列结

32、构体类型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

33、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_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-BTr

35、eeRear=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-

36、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