《树与二叉树转换的相关函数库实现--数据结构课程设计》由会员分享，可在线阅读，更多相关《树与二叉树转换的相关函数库实现--数据结构课程设计（24页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法课程设计成果报告树与二叉树转换的相关函数库实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换的相关函数库实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排
2、版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程设计要求12 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述32.4程序流程图32.5测试程序说明43 程序清单54 测试104.1 测试数据104.2 测试结果分析105 总结12参考文献131 课程设计目标与任务1.1 课程设计目标通过本课程设计，使自己在数据结构的选择和应用、算法的设计与实现方面得到训练.能根据实际问题的具体情况,结合数据结构课程中的基本理论和基本算法,正确分析出数据的逻辑结构,合理选择相应的存储结构,并能设计出
3、解决问题的有效方法。1.2 课程设计任务 设计树与二叉树转换的相关函数库，方便程序设计时的调用。1.3 课程设计要求 根据课程设计目标及课程设计的任务，我们首先要清楚树与二叉树的转换程序设计的大概轮廓，根据自己所学习的C语言的知识能够正确的设计好程序。使最后输出的是一般树转换成二叉树。在课程设计中要注意认真的编写程序代码，避免不必要的麻烦。最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目需求分析本程序的功能是对任意二叉树进行递归前序遍历和后序遍
4、历，用栈实现树与二叉树的转换。用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。结合数据结构课程中的基本理论和基本算法,正确分析出数据的逻辑结构,合理选择相应的存储结构,并能设计出解决问题的有效方法. 本程序的结果将输出输出树及树转换成二叉树。2.2 存储结构设计对于树与二叉树的转化，其实有不同的算法结构，这里我们采用了如下的储存结构，一般数的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。2.3 算法描述树的初始化函数，建树结构，输出树结构。1.引入头文件#include#include#include2.设置常量：#define MA
5、X_TREE_SIZE 1003.树的创建typedef structint data;int parent;PTNode;typedef structPTNode node MAX_TREE_SIZE;int count;/根的位置和结点个数PTree;typedef struct nodeint data;struct node *firstchild; struct node *rightsib;BTNode,*BTree;4.将树转换成二叉树(1)加线：在兄弟之间加一连线(2)抹线：对每个结点，除了其左孩子外，去除其与其余孩子支架的关系(3)旋转：以树的根结点为轴心，将整树顺时针转45
6、度。如下图所示：2.4 程序流程图通过本程序流程图2可以看出，先开始执行主菜单，然后对二叉树进行创建。首先是双亲法建树，根据格式输入各个结点，通过运用双亲数据，整型数据的方式（第一个结点双亲数据为-1，最后一-1，-1结束）。然后再一次输入第一个结点，第二个结点第n个结点。最后输出一般树转换成二叉树的情况。最后形成一个完整的程序。 图2 程序流程图 2.5 测试程序说明在visual c+6.0中，运行程序时，首先会出现主界面。主界面有三个选项。选项一、选择此选项进行树的创建。按双亲结点输出树的信息。选项二、此选项可以根据提示进行树的创建。并可以把树转化成二叉树。选项三、此选项可以退出程序。3
7、 程序清单#include#include#include#define MAX_TREE_SIZE 100/*树的双亲结点结构定义*/typedef structint data;int parent;PTNode;/*双亲表示法树结构 */typedef structPTNode node MAX_TREE_SIZE;int count;/根的位置和结点个数PTree;/*树的孩子兄弟表示结点结构的定义*/typedef struct nodeint data;struct node *firstchild; struct node *rightsib;BTNode,*BTree;/初始化
8、树（双亲表示法）void int_ptree(PTree *tree)tree-count=-1; /初始化树结点（孩子兄弟表示法）BTNode GetTreeNode(int a)BTNode t;t.data=a;t.firstchild=t.rightsib=NULL;return t; /水平输出二叉树void PrintBTree(BTNode *root,int level)int i;if(root!=NULL)PrintBTree(root-rightsib,level+1);for(i=1;idata);PrintBTree(root-firstchild,level+1);
9、/输出树void print_ptree(PTree tree)int i;printf(序号 结点 双亲n);for(i=0;i=tree.count;i+)printf(%8d%8d%8d,i,tree.nodei.data,tree.nodei.parent);printf(n);/*用双亲表示法创建树*/PTree CreatTree(PTree T)int i=1;int fa,ch;PTNode p;for(i=1;ch!=-1;i+)printf(输入第%d结点:n,i);scanf(%d,%d,&fa,&ch);printf(n);p.data=ch;p.parent=fa;T
10、.count+;T.nodeT.count.data=p.data;T.nodeT.count.parent=p.parent; printf(n);return T; /*一般树转换成二叉树*/BTNode *change(PTree T)int i,j=0;BTNode pMAX_TREE_SIZE;BTNode *ip,*is,*ir,*Tree;ip=(BTNode *)malloc(sizeof(BTNode);is=(BTNode *)malloc(sizeof(BTNode);ir=(BTNode *)malloc(sizeof(BTNode);Tree=(BTNode *)ma
11、lloc(sizeof(BTNode);for(i=0;iT.count;i+)pi=GetTreeNode(T.nodei.data);for(i=1;idata)j+;is=&pj;if(!(is-firstchild)is-firstchild=ip;ir=ip;Elseir-rightsib=ip;ir=ip;if(!(is-firstchild)is-firstchild=ip;ir=ip;else ir-rightsib=ip;ir=ip;Tree=&p0;return Tree; /*主菜单*/ void Menu()printf(*主菜单*n);printf(输入1，创建一棵一
12、般树n); printf(输入2，一般树转换成二叉树后的情况:n); printf(输入3，退出程序n);printf(请输入执行的指令:n);/*副菜单*/void Menu2()printf(*副菜单*n);printf(*返回主菜单继续操作*n);printf(*退出程序*n);/*主函数*/ void main()int i=0,c1,c2;PTree T;BTNode *Tree;int_ptree(&T);Menu();scanf(%d,&c1);switch (c1)case 1:printf(建立一般树，依次输入各个结点情况:n);printf(输入结点方式:双亲数据,整型数据(第一个结点双亲数据为-1,最后以-1,-1结束)例子:-1,1,1,3n );T=CreatTree(T);Tree=change(T);case 2:printf(一般树转
