数据结构与算法课程设计成果报告-树与二叉树转换实现.doc

河南工程学院数据结构与算法课程设计成果报告树与二叉树转换实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程 1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录目 录31 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3课程设计题目12 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述22.4 程序流程图43 程序清单54 测试114.1 测试数据11参考文献151 课程设计目标与任务1.1 课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.2 课程设计任务根据提供的实习题目，认真完成软件设计的全部过程，并以最终软件设计成果来证明其独立完成实际任务的能力，从而，反映出理解和运用数据结构与算法的水平和能力，最后完成软件设计和程序调试并提交文档：课程设计报告书，报告书中包含设计的算法及部分程序代码。1.3课程设计题目设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目需求分析由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到唯一的一颗二叉树与之对应，从物理结构看来，它们的二叉链表是相同的，只是解释不同而已。1、将树转化为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：在所有兄弟结点之间加一连线；对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。2、将二叉树转化为树 把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。2.2 存储结构设计二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构。二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。2.3 算法描述1、 树、森林转换成二叉树将一棵树转换成二叉树的方法： 将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。特点：一棵树转换成二叉树后，根结点没有右孩子。将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。2 、二叉树还原成树或森林这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。2.4 程序流程图退出程序层次遍历开始双亲法建树按照格式输入各个结点输出树的结点情况1主菜单前序遍历（递归）后序遍历（递归）前序遍历（非递归）后序遍历（非递归）输出遍历结果副菜单退出程序23540069图2.4程序开始之后进入主菜单，这时有两个选择程序运行下去或者直接退出程序，程序运行之后有五个选择，分别是一种方法四种遍历，之后程序运行到福彩单，再者要么结束程序要么重新回到主菜单重新运行程序。3 程序清单/初始化树(双亲表示法)void init_ptree(PTree *tree) tree-count=-1;/初始化树结点(孩子兄弟表示法)BTNode GetTreeNode(int x)BTNode t;t.data=x;t.firstchild=t.rightsib=NULL;return t;/树的前序遍历(递归)void preorder(BTNode *T)if(T!=NULL)printf(%d ,T-data);preorder(T-firstchild);preorder(T-rightsib);/树的前序遍历(非递归)void preorder2(PTree T)int i;for(i=0;ifirstchild);printf(%d ,T-data);inoeder(T-rightsib);/树后序遍历(非递归)void inoeder2(PTree T)int i;for(i=T.count-1;i=0;i-)printf(%d ,T.nodei);/层次遍历void level(PTree T)int i;for(i=0;irightsib,level+1); for(i=1;idata); PrintBTree(root-firstchild,level+1); /输出树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.count+; T.nodeT.count.data = p.data; T.nodeT.count.parent = p.parent;printf(n);printf(创建的树具体情况如下:n);print_ptree(T);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 *)malloc(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;Tree=&p0;return Tree;/*主菜单*/void Menu()printf(=主菜单=n);printf(*输入1-以双亲法创建一棵一般树*n); printf(*输入2-树的前序遍历(递归)*n); printf(*输入3-树的后序遍历(递归)*n); printf(*输入4-树的前序遍历(非递归)*n); printf(*输入5-树的后序遍历(非递归)*n); printf(*输入6-层次序的非递归遍历*n); printf(*输入0-退出程序*n); printf(=n); printf(请输入执行的指令:);/*副菜单*/void Menu2()printf(*副菜单*n);printf(*9-返回主菜单继续操作*n);printf(*0-退出程序*n);/*主函数*/void main() int i=0,c1,c2; PTree T; BTNode *Tree; init_ptree(&T); loop: Menu();scanf(%d,&c1); switch(c1) case 1: printf(建立一般树,依次输入各个结点情况:n); printf(输入结点方式:双亲数据,整型数据(第一个结点双亲数据为-1,最后以-1,-1结束)n例子:-1,1 1,3n);T=CreatTree(T);Tree=change(T);printf(一般树转换成二叉树后的情况:n);PrintBTree(Tree,i);getchar(); break; case 2: printf(树的前序遍历(递归):n); preorder(Tree); printf(n); break; case 3: printf(树的后序遍历(递归):n); inoeder(Tree); printf(n); break; case 4: printf(树的前序遍历(非递归):n); preorder2(T); printf(n); break; case 5: printf(树的后序遍历(非递归):n); inoeder2(T); printf(n); break; case 6: printf(树的层次遍历:n); level(T); printf(n); break; case 0: exit(1); break; Menu2(); scanf(%d,&c2); if(c2=9) goto loop; else if(c2=0) exit(1); 4 测试4.1 测试数据程序开始：图4.1-1建立一棵一般树：输入指令1图4.1-2双亲数据（整型），结点数据（整型） 以-1，-1结束如：-1，1 1，2 -1，-1图4.1-3图4.1-4图4.1-5图4.1-6图4.1-7图4.1-95 总结通过这次实训，让我深刻的认识到数据结构这门课程的结构性与严谨性。这次学习不仅让我加固了知识的理解与掌握，更重要的是让我明白了数据与算法的深刻含义。在实验中不可避免的出现了大大小小的问题，在调试中透彻领悟各种算法的真谛，同样的错误在下次遇到时就可以避免了。在实验中，分别使用了VC+和Turbo C两种编译器，在使用各种编译器的同时能了解不同的编译器的不同之处，取长补短，更好的设计程序。参考文献1谭浩强.c语言程序设计.清华大学出版社2谭浩强.c+面向对象程序设计.清华大学出版社3朱昌杰等.数据结构（c语言版）.清华大学出版社4MaryCampione.Java语言导学（第四版）.机械工业出版社5Y.Daniel Liang.Java语言程序设计基础篇（第六版）.机械工业出版社#include ;#include ;#include ;#define MAX_TREE_SIZE 100;/*树的双亲表示结点结构定义*/typedef struct int data; int parent; /双亲位置域PTNode;/*双亲表示法树结构*/typedef struct PTNode nodeMAX_TREE_SIZE; int count; /根的位置和节点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct nodeint data;struct node *firstchild;struct node *rightsib;BTNode,*BTree;/初始化树(双亲表示法)void init_ptree(PTree *tree) tree-count=-1;/初始化树结点(孩子兄弟表示法)BTNode GetTreeNode(int x)BTNode t;t.data=x;t.firstchild=t.rightsib=NULL;return t;/树的前序遍历(递归)void preorder(BTNode *T)if(T!=NULL)printf(%d ,T-data);preorder(T-firstchild);preorder(T-rightsib);/树的前序遍历(非递归)void preorder2(PTree T)int i;for(i=0;ifirstchild);printf(%d ,T-data);inoeder(T-rightsib);/树后序遍历(非递归)void inoeder2(PTree T)int i;for(i=T.count-1;i=0;i-)printf(%d ,T.nodei);/层次遍历void level(PTree T)int i;for(i=0;irightsib,level+1); for(i=1;idata); PrintBTree(root-firstchild,level+1); /输出树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.count+; T.nodeT.count.data = p.data; T.nodeT.count.parent = p.parent;printf(n);printf(创建的树具体情况如下:n);print_ptree(T);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 *)malloc(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;Tree=&p0;return Tree;/*主菜单*/void Menu()printf(=主菜单=n);printf(*输入1-以双亲法创建一棵一般树*n); printf(*输入2-树的前序遍历(递归)*n); printf(*输入3-树的后序遍历(递归)*n); printf(*输入4-树的前序遍历(非递归)*n); printf(*输入5-树的后序遍历(非递归)*n); printf(*输入6-层次序的非递归遍历*n); printf(*输入0-退出程序*n); printf(=n); print