树与二叉树转换实现3.docx

《树与二叉树转换实现3.docx》由会员分享，可在线阅读，更多相关《树与二叉树转换实现3.docx（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河南工程学院数据结构与算法课程设计成果报告树与二叉树转换实现2014年12月29日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-l;i=0;i-)(printf(%d ,T.nodei);层次遍历void level(PTree T)(int i;for(i=0;irightsib,level+l);for(i=l;idata);RrintBTree(roo

2、t-firstchild,level+l);)输出树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=l;int fa,ch;PTNode p;for(i=l;ch!=-l;i+)(printf(输入第d 结点:n,i);scanf(%d/%d)&fa,&ch);print

3、f(n);p.data=ch;p.parent=fa;T.count+;T.nodeT.count.data = p.data;T.nodeT.count.parent = p.parent;)printfCXn);printf(“创立的树具体情况如下:rT);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 *)ma

4、lloc(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=l;idata)(j+;is=&pj;10is-firstchild=ip;ir = ip;)else(ir-rightsib=ip;ir = ip;)Tree=&pO;return Tree;/*主菜单*/void Menu()printf(=主菜单=二=二二二=二=二=二二=仁);printf（*

5、输入1以双亲法创立一棵一般树*树的前序遍历（递归）*n）;树的后序遍历（递归）*n“）;printf（*输入4树的前序遍历（非递归）*n）;printf（*输入5树的后序遍历（非递归）*rT）;printf（*输入6层次序的非递归遍历*n）;退 I 不呈j*n”)printf(printf(=n,)；printf（“请输入执行的指令11/*副菜单*/void Menu2()printf(SC 33 3C 口3|5j 5j 3|3 SC 5|3jprintf(*9返回主菜单继续操作* *n“);printf(*O退出程序n);/*主函数*/void main()(int i=0,cl,c2;PT

6、ree T;BTNode *Tree;init_ptree(&T);loop:Menu();scanf(%d,&cl);switch(cl)(case 1: printf(建立一般树，依次输入各个结点情况:n);printf(输入结点方式:双亲数据，整型数据(第一个结点双亲数据 为-1,最后以-1,-1结束)n例子:-1,1 13n)；T=CreatTree(T);Tree=change(T);printf(一般树转换成二叉树后的情况:n);PrintBTree(TreeJ);getchar();break;12case 2: printf(树的前序遍历(递归):n);preorder(Tre

7、e);printfCXn);break;printf(树的后序遍历(递归):n);inoeder(Tree);printf(n);break;case 3: printf(树的前序遍历俳递归):n);preorder2(T);printfCXn);break;printf(树的后序遍历(非递归):rT);inoeder2(T);printf(n);break;case 4: printf(“树的层次遍历:n);level(T);printfCXn);break;13case 0:exit ；break;)Menu2();scanf(%d,&c2);if(c2=9)goto loop;else

8、if(c2=0) exit ；)144测试测试数据程序开始:cT C:JlSOFTCYuYanbinwp. exe=主菜单* *输入1以双亲法创立一棵一般树* *输入2树的前序遍历（递归）* *输入3树的后序遍历（递归）* *输入4树的前序遍历（非递归）* *输入5树的后序遍历（非递归）* *输入6层次序的非递归遍历*输入0*输入0退出程序 *请输入执行的指令:建立一棵一般树：输入指令1c、 C:J.SOFICYuYanbinxte-p. exe=主菜单=Ak*输入1以双亲法创立一棵一般树*输入2树的前序遍历（递归）*k*输入3树的后序遍历（递归）*咻*输入4树的前序遍历（非递归）*k*输入5

9、树的后序遍历（非递归）*畔*输入6层次序的非递归遍历*k* 输入 0退出程序 * 清输入执行的指令：1建立一般树,依次输入各个结点情况：俞入结点方式:双亲数据,整型数据（第一个结点双亲数据为T,最后以T, T结束）那么子:T,1 1,3俞入第1结点：15输入结点的方式：双亲数据（整型），结点数据（整型）以T, T结束如：T, 11, 2 -1, -1 C:JlSOFTCYuYanbinwtep. eze* *输入2树的前序遍历（递归）*HI* *输入3树的后序遍历（递归）* *输入4树的前序遍历（非递归）*_* *输入5树的后序遍历（非递归）* *输入6层次序的非递归遍历* 输入 0退出程序

10、*请输入执行的指令：1建立一般树,依次输入各个结点情况：输入结点方式:双亲数据,整型数据（第一个结点双亲数据为-1,最后以-1结束）例子：-1, 1 1,3输入第1结点：T, 1输入第2结点：1,2输入第3结点：1,3输入第4结点：2,4输入第5结点：-1, -1一般树创立完的具体情况：16题目树与二叉树转换实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格

11、按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:序号结点双亲01-11212313424-1-1一般树转换成二叉树后的情况:1创立的树具体情况如下:34不不不不不不不不不不不不不不不不干田UK;干干不不不不不不不不不不不不不不不不不不*9*0*9*0返回主菜单继续操作*退出 序*175总结通过本次程序设计，让我更深层次地了解到了树各种函数的运用，如何运用 各种存储结构创立树，以及在实验中还涉及到递归的运用，递归的思想省去了复 杂的算法设计。在实验中不可防止的出现了大大小小的问题，在调试中透彻领悟 各种算法的真谛，同样的错误在下次遇到时就

12、可以防止了。参考文献1朱福喜.Java语言程序设计（第二版）.科学出版社陈国君等.Java程序设计基础（第二版）.清华大学出版社Deitel.Java大学基础教程（第六版）.电子工业出版社MaryCampione.Java语言导学（第四版）.机械工业出版社丫.Daniel Liang.Java语言程序设计基础篇（第六版）.机械工业出版社Kathy Sierra.Head First Java（第二版）.东南大学出版社181课程设计目标与任务11.1课程设计目标11. 2课程设计任务12分析与设计22.1题目需求分析22. 2存储结构设计22. 3算法描述32.4程序流程图53程序清单64测试1

13、54.1测试数据155总结18参考文献181课程设计目标与任务1.1课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方 面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方 法及上机操作方面受到比拟系统严格的训练，培养软件工作所需要的动手能力。1. 2课程设计任务(1)实现树与二叉树的转换；(2)最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来，将复杂的运行过程以动态方式显示出来；(3)给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2分析与设计2. 1题目需求分析根据提供的实习题目，认真完成软件设计的全部

14、过程，并以最终软件设计 成果来证明其独立完成实际任务的能力，从而，反映出理解和运用数据结构与算 法的水平和能力，最后完成软件设计和程序调试并提交文档：课程设计报告书， 报告书中包含设计的算法及局部程序代码。3. 2存储结构设计引入头文件：#include #include #include 设置常量：#define MAX_TREE_SIZE 100一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本 实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下：/*树的双亲表示结点结构定义*/typedef struct（int data;int parent;双亲位置域）PTNode

15、;/*双亲表示法树结构*/typedef struct（PTNode nodeMAX_TREE_SIZE;int count;根的位置和节点个数）PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct node（int data;struct node *firstchild;struct node *rightsib;）BTNode/BTree;2. 3算法描述树的初始化函数（双亲法和孩子结点法两种），建树函数，输出树函数， 树的前序遍历函数（递归和非递归两种），树的后序遍历函数（递归和非递归两 种），树的层次遍历函数，一般树和二叉树的转换函数。主菜单和副菜单。主 函数

16、。具体代码如下：初始化树（双亲表示法）void init_ptree（PTree *tree） tree-count=-l;）初始化树结点（孩子兄弟表示法）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 H,T-data);preorder(T-firstchild);preorder(T-rightsib);)树的前序遍历(非递归)void preorder2(PTree T)(int i;for(i=0;icount=-l;)初始化树结点(孩子兄弟表示法)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 H,T-data);preorder(T-firstchild);preorder(T-rightsib);)树的前序遍历（非递归）