树与二叉树转换的相关函数库实现-数据结构课程设计报告

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 算法描述22.4 数据结构分析52.5 程序流程图62.6 测试程序说明73 程序清单84 测试134.1 测试数据134.2 测试结果分析145 总结15参考文献161 课程设计目标与任务1.1 课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中

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

4、习题目，认真完成软件设计的全部过程，并以最终软件设计成果来证明其独立完成实际任务的能力，从而，反映出理解和运用数据结构与算法的水平和能力，最后完成软件设计和程序调试并提交文档：课程设计报告书，报告书中包含设计的算法及部分程序代码。1.3 课程设计基本要求1树采用双亲表示法2能够将树转换为二叉树3对转换的二叉树进行算法设计统计结点的孩子数4利用转换的二叉树计算树的高度.2 分析与设计2.1 题目需求分析（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实

5、现相关问题的求解。2.2 概要设计操作集合：(1) CTreeNode*SearchCTree(CTreeNode*root,chardata) (2) CTreeNode*CreateSTree()生成树(3) voidpreorderTree(CTreeNode*ctroot)树的遍历(4) voidPrintTree(CTreeNode*troot,intdepth)树的输出(5) void initQueueCTree(QueueCTree*&q)初始化树队列(6) void initQueueBTree(QueueBTree*&q)初始化二叉树队列(7) void TreeToBTr

6、ee(CTreeNode*ctroot,BTreeNode*&btroot)/树转化为二叉树 ctroot指向树的根结点，btroot指向二叉树的根节2.3 算法描述一般数的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。1.将树转化成二叉树：（1）加线：在兄弟之间加一连线（2）抹线：对每个结点，除了其左孩子外，去除其与其余孩子支架的关系（3）旋转：以树的根结点为轴心，将整树顺时针转45度。使二叉树的结构层次分明。（4）树转换成二叉树后其右子树一定为空。将树转换为二叉树的图如图2.1：图2.1：树转换成二叉树图2.将二叉树转换为树：（1）加线：若p

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

8、*rchild;/左右孩子结点的指针;struct QueueCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/结构体指针数组，存放节点的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear; ;struct QueueBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/结构体指针数组，存放节点的地址 /struct nodeBTree *next; int BTreeFront,BTreeRear; ;2.5程序流程图从程序中可以知道，首先执行的是主菜单，然后会出现执行树的建立这

9、一功能，而我们所用的是双亲法建树，按照格式输入各个结点，再输出树的结点情况，然后第二个功能即将一般树转化成二叉树，然后会有退出程序的功能。并且，主函数的功能执行后要进行副菜单的输出，最后还有一退出程序，即程序完整地执行完毕，它的具体流程图可以如图2.4所示：开始主菜单输入树的的结点数输入信息生成树输出树的结点数树转化为二叉树二叉树的信息图树的信息图树的前序遍历二叉树的结点孩子数二叉树的结构图二叉树的深度二叉树的前序遍历树的结构图输出结果退出程序图2.4：程序流程图2.6测试程序说明1函数之间的调用关系，如图2.5：Main()Menu()CTreeNode*TreePrintIn(BTree,

10、5)Preorder(BTree)PrintTree(Tree.10)preorderTree(Tree)TreeToBTree(Tree,BTree)图2.5：函数关系调用图2. 在visual c+6.0中，运行程序时，首先会出现主界面。主界面有三个选项。选项一、选择此选项进行树的创建。按双亲结点输出树的信息。选项二、此选项可以根据提示进行树的创建。并可以把树转化成二叉树。选项三、此选项可以退出程序。3 程序清单#include#include#define DEGREE 5 /树的高度#define NULL 0 #define QUEUESIZE 10 struct CTreeNode

11、/树结点的类型char data;/数据域，采用char struct CTreeNode *childrenDEGREE;/指向孩子结点的指针域;struct BTreeNode char data;/数据域 BTreeNode *lchild,*rchild;/左右孩子结点的指针;struct QueueCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/结构体指针数组，存放节点的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear; ;struct QueueBTree BTreeNode *BTreeAr

12、rayMAX_NODE_NUM;/结构体指针数组，存放节点的地址 /struct nodeBTree *next; int BTreeFront,BTreeRear; ;void TreeToBTree(CTreeNode*ctroot,BTreeNode*&btroot)/树转化为二叉树ctroot指向树的根节点，btroot指向二叉树的根QueueCTree*VisitedCTreeNodes;QueueBTree*VisitedBTreeNodes;/辅助队列initQueueCTree(VisitedCTreeNodes);initQueueBTree(VisitedBTreeNode

13、s);/初始化队列 CTreeNode*ctnode;BTreeNode*btnode,*p,*LastSibling;int i;btroot=newBTreeNode;/添加开辟内存空间语句 btroot-data=ctroot-data;/树的根节点作为二叉树的根节点btroot-lchild=btroot-rchild=NULL;addQueueCTree(VisitedCTreeNodes,ctroot);/树的根结点入队 addQueueBTree(VisitedBTreeNodes,btroot);/二叉树的根结点入队while(!QueueCTreeEmpty(VisitedC

14、TreeNodes)ctnode=delQueueCTree(VisitedCTreeNodes);/树结点出队btnode=delQueueBTree(VisitedBTreeNodes);/二叉树结点出队for(i-0;ichildreni-NULL);/孩子结点访问完毕break;p=new BTreeNode;/分配二叉树结点p-data=ctrode-childreni-data;p-lchild=p-rchild=NULL;if(i=0)btnode-lchild=p;/长子，作为父结点的左孩子else LastSibling-rchild=p;/作为上一个兄弟结点的右孩子Last

15、Sibling=p;addQueueCTree(VisitedCTreeNodes,ctnode-childreni);/树结点进队列 addQueueBTree(VisitedBTreeNodes,p);/二叉树结点进门队列typedef struct nodeCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear;QueueCTree;/二叉树队列结构类型typedef struct nodeBTree BTreeNode *BTre

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

17、BTreeFront=q-BTreeRear=0;int main()CTreeNode*Tree;BTreeNode*BTree;int x=0;char n,i,j,k;while(1) p:n=menu();if(n=1)while(1)i=Treemenu();switch(i)case1:Tree=CreateSTree();break; case2:printTree(Tree,10);coutntt按任意键返回.n;getch();break;case3:preorderTree(Tree);coutntt按任意键返回.n;getch();break;case4:goto p;b

18、reak;if(n=2)TreeToBTree(Tree.BTree);while(1)j-BTreemenu();switch(j)case1:println(BTree,5);coutntt按任意键返回.n;getch();break;case2:preorder(BTree);coutntt按任意键返回.n;getch();break;case3:coutFindDepth(BTree);coutntt按任意键返回.n;getch();break;case4:count(BTree);coutntt按任意键返回.n;getch();break;case5:goto p;break;if(

19、n=3)break;return 0;4 测试4.1 测试结果运行程序得出如下界面输入结点数量以及孩子及其父亲结点的数据，如图4.1：图4.1：运行程序界面一般树转换为二叉树后的情况，如图4.2：图4.2：树转换二叉树界面4.2 测试结果分析 创建一棵树，输入树的结点的数量为：6输入根结点的数据为：c输入2个孩子结点的数据及其父亲结点的数据：ac输入3个孩子结点的数据及其父亲结点的数据：bc输入4个孩子结点的数据及其父亲结点的数据：dc输入5个孩子结点的数据及其父亲结点的数据：eb输入6个孩子结点的数据及其父亲结点的数据：ga则树的先序遍历结果为：c a b e d g转换后的二叉树，先序遍历

20、的结果为：c a b e d g5 总结通过这次程序设计，我发现，有关一个课题的所有知识不仅仅是在课本上，多查阅一些资料能够更好地完成课题，这就需要一种能力，即自学能力。本次课程设计还让我认识到自身的缺点。课程设计选取的是树与二叉树的转换，刚开始认为比较简单，但到后来就出现一些比较难以解决的问题，于是向老师请教，并查阅有关资料。经过不断的完善与改进，最终测试成功。这次课程设计让我对这门数据结构有了更深的认识，而且还拓展了我的知识面。这次实训也让我看到了自己的不足，对于知识不能熟练的掌握，更加让我明白了只有不断的实践才能更好的掌握知识。参考文献1 谭浩强著.C+语言设计题解与上机指导.清华大学出

21、版社2 谭浩强著.C+面向对象程序设计 .清华大学出版社3 李春葆著.数据结构教程.清华大学出版社4 严蔚敏，吴伟民著.数据结构.清华大学出版社#include#include#define DEGREE 5 /树的高度#define NULL 0 #define QUEUESIZE 10 struct CTreeNode/树结点的类型char data;/数据域，采用char struct CTreeNode *childrenDEGREE;/指向孩子结点的指针域;struct BTreeNode char data;/数据域 BTreeNode *lchild,*rchild;/左右孩子结

22、点的指针;struct QueueCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/结构体指针数组，存放节点的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear; ;struct QueueBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/结构体指针数组，存放节点的地址 /struct nodeBTree *next; int BTreeFront,BTreeRear; ;void TreeToBTree(CTreeNode*ctroot,BTreeNode*&btroot)/

23、树转化为二叉树ctroot指向树的根节点，btroot指向二叉树的根QueueCTree*VisitedCTreeNodes;QueueBTree*VisitedBTreeNodes;/辅助队列initQueueCTree(VisitedCTreeNodes);initQueueBTree(VisitedBTreeNodes);/初始化队列 CTreeNode*ctnode;BTreeNode*btnode,*p,*LastSibling;int i;btroot=newBTreeNode;/添加开辟内存空间语句 btroot-data=ctroot-data;/树的根节点作为二叉树的根节点b

24、troot-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=new BTreeNode;/分配二叉树结点p-data=ctrode-childreni-data;p-lch