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

河南工程学院数据结构与算法课程设计成果报告树与二叉树转换的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1课程设计目标11.2课程设计任务11.3课程设计要求11.4课程设计基本操作方法12 分析与设计22.1 题目分析22.2存储结构设计22.3 算法思想描述33 程序清单64 程序测试105 总结12参考文献131 课程设计目标与任务1.1课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼。1.2课程设计任务（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3课程设计要求根据提供的课程设计的题目，掌握程序分析方法，学会程序设计的基本方法，认真完成题目的要求，从而增强理解和运用C+程序知识的能力，并以最终程序运行结果来证明完成课程设计任务，最后完成题目要求和程序调试并提交文档，课程设计报告书中包含算法及部分程序代码。1.4课程设计基本操作方法1按照系统文档规范要求进行操作，养成查阅文档的良好习惯；2对特殊疑难问题采用讨论、协作等方式进行解决，有意识地训练团队合作意识；3课程设计报告应多包含在课程设计过程中出现的错误及解决方法。2 分析与设计2.1 题目分析题目需求分析是课程设计的一个重要环节，通过对题目的分析，可以更好的理解题目，能更快更好的完成课程设计。本程序的功能是对二叉树进行递归前序遍历和后序遍历，还有对树的前序和后序遍历以及树与二叉树的转换。本程序要求以数值输入，若要实现终端结点，最后以回车键结束数据。本程序的结果将输出一棵树及树转换成二叉树，树的前序和后序遍历以及指定二叉树的前序、中序和后序遍历。根据所提供的题目，是要实现树与二叉树的转换，而且可以在程序设计中调用使用。学生要认真完成能够实现题目要求的函数库。由于二叉树和树都可以使用二叉链表作为存储结构，则二叉链表作为媒介可导出树与二叉树之间的一个对应关系。给定一棵树，可以找到唯一的一棵二叉树与之对应。具体的要求如下：（1）树采用双亲表示法。（2）能够将树转化为二叉树。（3）以及树的前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。2.2存储结构设计(1)设置头文件：#include#include#include(2)设置常量：#define MAX_TREE_SIZE 100(3)一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点，本实验运用到的是双亲结点和孩子兄弟结点，具体存储结构如下：Typedef structint data,parent/双亲位置域;PTNode;双亲表示法树结构：Typedef structPTNode nodeMAX_TREE_SIZE;int count;PTree;树的孩子兄弟结点表示结点结构定义：Typedef struct node int data; struct node *firstchild;struct node *rightsib;BTNode,*BTree;2.3 算法思想描述图2.1 树的结构图树的结构如上，将(a)树转换成二叉树的步骤及过程示意图如下：（1）加线：就是在所有兄弟结点之间加一条连线；图2.2 加线后的树（2）抹线：就是对树中的每个结点只保留它与左孩子结点之间的连线，删除它与其它孩子结点之间的连线；图2.3 抹线后形成的二叉树（3）旋转：就是以树的根结点为轴心，将整棵树顺时针旋转45度，使二叉树结构层次分明。图2.4 二叉树 2.4 程序流程图本程序先用双亲表示法创建一棵树，创建树的结点，同时在每个结点中附设一个指针指示结点在链表中位置，然后将其转换成二叉树。再根据树的遍历定义完成对树进行先序和后序遍历，先序遍历即先访问根结点，再先序遍历左子树再遍历右子树;后序遍历先后续遍历左子树再后续遍历右子树再访问根结点。然后创建一颗二叉树，根据上述方法完成二叉树的前中后序遍历。具体的流程图如下：开 始选择【3】后序遍历选择【1】前序遍历选择【2】中序遍历10退出程序选择1或0输出转换后的二叉树输出树的创建情况选择【0】退出系统选择【4】树的后序遍历选择【3】树的中序遍历选择【2】树的前序遍历选择【1】创建树输入选项进行操作菜单输 出 遍 历 结 果图2.4 程序流程图3 程序清单#include #include #include #define MAX_TREE_SIZE 100/树的双亲表示结点结构定义typedef structint data;int parent;/双亲位置域PTNode;/双亲表示法树结构typedef structPTNode 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-)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);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);/副菜单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);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 程序测试（1）运行前面提到的程序后，会在计算机窗口显示出程序所涉及的操作流程“主菜单”。其内部包含用双亲法创建一般树、树的先序遍历等操作功能如图所示。图4.1 主菜单（2）按照操作提示，首先输入1建立一般树，然后根据窗口提示一次输入各个结点（示例是依次输入-1，1；3，2；2，3；2,4和-1，-1），工作平台会显示出下图所示的操作过程。图4.2 示例操作数据（3）输入上述所提供的示例之后，该程序会在工作平台显示运行结果，自动生成一般树，并且输出树的具体情况（包括序号、结点和双亲）。在建立好一般树之后，系统会自动把它转化为二叉树，并输出新形成的树的具体情况。同时，程序主函数内部的“副菜单”也会被调用（如下图所示），从而显示出来供操作者根据自身情况进行操作。图4.3 树与二叉树的转换（4）当进行完以上操作后，按照提示输入9后会重新显示一个如图4.1.1所示的主菜单，然后输入3（此为示例操作），会自动调用“树的后序遍历（递归）”方法，在工作平台上显示此树的后序遍历结果，具体情形如下图所示。图4.4 树的后序遍历5 总结这次上机实习我主要学习了树与二叉树之间的转换的链式实现。从用双亲法建立树，到先序、后序，层序遍历的c语言实现，花费了很多的时间。这其中充分认识到自己对递归算法、对树与二叉树转化具体实现的不足。但最后通过查阅资料，询问老师，最终完成了这次试验。通过这次实习，我加深了对树以及二叉树这两种重要数据结构的理解。编写程序的时候枯燥，出现错误不明白原因也让人费力的查找。但程序运行带来的更多是成就感。这次上机让我明白懂得一些算法思想和能用具体的程序语言实现之间还需上机的努力。参考文献1 严蔚敏.数据结构（C语言版）. 清华大学出版社 2 殷人昆.数据结构(C语言描述). 机械工业出版社3 谭浩强.C语言程序设计. 清华大学出版社 4 谭浩强.C+程序设计基础. 清华大学出版社5 齐徳昱.算法与数据结构. 清华大学出版社 6 刘遵仁.数据结构. 人民邮电出版社#include#include#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100 / 存储空间初始分配量typedef struct char *base;char *top;int stacksize;Stack;int InitStack(Stack &S)S.base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!S.base) return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE; return OK;int Pop(Stack &S,char &e) if(S.top=S.base) return ERROR; e=*-S.top; return OK;int GetTop(Stack S,char &e)if(S.top=S.base) return ERROR;e=*-S.top;return OK;int Push(Stack &S,char ch)if(S.top-S.base=S.stacksize)S.base=(char*)realloc(S.base,(S.stacksize+10)*sizeof(char);if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=10;*S.top+=ch;return OK;char Compare(char &e,char ch) switch(e) case +:if(ch=+|ch=-|ch=) return ; else return ; else return ; break; case *:if(ch=()return ; break; case /:if(ch=()return ; break; case (:if(ch=)return =; else return ; break;