树与二叉树转换的相关函数库实现数据结构课程设计
河南工程学院数据结构与算法课程设计成果报告树与二叉树转换的相关函数库实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法指导教师： 2014 年 12 月 29 日题 目树与二叉树转换的相关函数库实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标11.1 课程设计目标11.2 课程设计任务11.3 课程设计要求12 分析与设计22.1 题目需求分析22.2 存储结构设计22.3 算法描述32.4 程序流程图42.5 测试程序说明53 程序清单94 测试154.1 测试数据154.2 测试结果分析155 总结17参考文献181 课程设计目标与任务1.1课程设计目标此次课程不仅要从概念上理解树和二叉树，还要从相关应用实际应用中学会运用树特别是二叉树。根据树的相关概念了解树的存储方法和算法及应用以及二叉树的存储方法、遍历、算法和应用。同时在此基础上对树和二叉树的转换的实现进行编程掌握。这次课程设计的目标是通过这次的课程设计，能够使我们在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力，熟练的掌握数据结构有关知识的应用，加深对数据结构有关知识的理解和应用，进一步提高自己的编程能力，提高自身的动手能力。1.2 课程设计任务设计树与二叉树的相关数据库，以便对树与二叉树的转换的实现进行编程掌握。1.3 课程设计要求利用本学期所学的数据结构的有关知识，实现树与二叉树相互转换，设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目需求分析 树型结构是一类重要的非线性数据结构，其中以树与二叉树最为常见。二叉树的每个结点至多只有两颗子树，并且二叉树的子树有左右之分，其次序不能颠倒。由于二叉树与树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系这个一一对应的关系导致森林或树与二叉树的转换。 2.2 存储结构设计分析树和二叉树的存储结构，二叉树的存储结构如图2.1。图2.1二叉树的存储结构图树是一种非线性的数据结构，树中的元素之间是一对多的层次关系。常用的有三种存储结构，即双亲表示法、孩子表示法、和孩子兄弟表示法。 事实上，一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的，只是两个指针域的名称及解释不同而已,通过图直观的表示了树与二叉树之间的对应关系和相互转换方法。图2.2 树和二叉树的转换图2.3 算法描述将树转换为二叉树的步骤如下：1、加线：所有兄弟节点之间加线2、去线：保留树中每个结点与它第一个孩子的连线，删除其与其他孩子的连线3、层次调整：以根结点为轴心，将整棵树旋转，使之层次分明。 图2.3树转化为二叉树的形象图2.4 程序流程图该程序是先建立树，再以树为基础，将树转换成二叉树。该程序的流程是建立树，利用队列，递归，指针等，将树的根结点变为二叉树的根结点，进行树到二叉树的转换，程序的最终目的是根据输入的树的接点，孩子结点及其父亲结点，生成二叉树，将树的先序遍历结果和二叉树的先序遍历的结果输出。图2.4程序流程图2.5 测试程序说明（1）一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下typedef struct st1/树结点的类型 char data;/数据域，采用char星 struct st1 *childrenDEGREE;/指向孩子结点的指针域CTreeNode;typedef struct st2 char data;/数据域 struct st2 *lchild,*rchild;/左右孩子结点的指针BTreeNode;（2）点下面的一段程序是树的先序遍历，遍历树的每个结点，即输出该结点的指针域，先遍历下根结点，然后依次遍历孩子结，采用递归算法。void preorderTree(CTreeNode *ctroot) CTreeNode *ctchild; int i; cout<<ctroot->data<<" " for(i=0;i<DEGREE;i+) ctchild=ctroot->childreni; if(ctchild=NULL) break; else preorderTree(ctchild); 此程序即为二叉树的先序遍历，采用递归调用。void Preorder(BTreeNode *T) if(T) cout<<T->data<<" " Preorder(T->lchild); Preorder(T->rchild); （3）CTreeNode *CreateSTree()函数，输入树的结点的数量以及各个结点的数据， 用parentNode=SearchCTree(root,parent)查找指定数据的结点。CTreeNode *CreateSTree() int i,j,k; char data, parent; CTreeNode *root,*parentNode,*node; cout<<"请输入树的结点的数量:" cin>>j; if(j=0) return NULL;/空树，结束函数 cout<<"请输入根结点的数据:" cin>>data; fflush(stdin); root=(CTreeNode *)malloc(sizeof(CTreeNode); root->data=data; for(i=0;i<DEGREE;i+) root->childreni=NULL; for(i=2;i<=j;i+)/依次输入每个结点的信息 cout<<"请输入"<<i<<"个孩子结点的数据及其父亲结点的数据:" cin>>data>>parent; fflush(stdin); node=(CTreeNode *)malloc(sizeof(CTreeNode); node->data=data; for(k=0;k<DEGREE;k+) node->childrenk=NULL; parentNode=SearchCTree(root,parent); for(k=0;k<DEGREE;k+） if(parentNode->childrenk=NULL) parentNode->childrenk=node; break; return root;（4）下面的程序是建立树队列以及二叉树队列的结构体类型，CTreeNode *CTreeArrayMAX_NODE_NUM为结构体指针数组，存放结点的地址，BTreeNode *BTreeArrayMAX_NODE_NUM为结构体指针数组，存放结点的地址。typedef struct nodeCTreeCTreeNode *CTreeArrayMAX_NODE_NUM; int CTreeFront,CTreeRear;QueueCTree;typedef struct nodeBTree BTreeNode *BTreeArrayMAX_NODE_NUM; int BTreeFront,BTreeRear;QueueBTree;（5）下面是将树转换为二叉树的主要程序段，ctroot指向树的根结点，btroot,指向二叉树的根,先初始化队列，然后开辟新的内存空间，以树的根结点作为二叉树的根结点，树的根结点入队，二叉树的根结点入队，树结点出队，二叉树结点出
