树与二叉树转换的实现8

1、河南工程学院数据结构与算法课程设计成果报告树与二叉树转换的实现2014年12月29日3程序清单ftinclude ftinclude ftinclude ftdefine MAX_TREE_SIZE 100树的双亲表示结点结构定义typedef structint data;int parent;/双亲位置域PTNode;双亲表示法树结构typedef structPTNode nodeMAX_TREE_SIZE;int count; 根的彳立置和结点个数PTree,树的孩子兄弟表示结点结构定义typedef struct nodeint data;struct node irstchild;

2、struct node *rightsib;BTNode, *BTree;void init_ptree(PTree *tree)tree-count =T;)初始化树结点(孩子兄弟表示法)BTNode GetTreeNode(int x) BTNode t;t. data =x;t. firstchild =t.rightsib =NULL; return t;树的先序遍历(递归)void preorder (BTNode *T) if (T!=NULL)(printf T-data );preorder(T-firstchild );preorder (T-rightsib );)树的先序

3、遍历(非递归)void preorder2(PTree T) int i;for(i=0;ifirstchild);printf(%d, T-data);inoeder (T-rightsib );7树的后序遍历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=l;idata);PrintBTree(root-firstchild, level+1);)输出树void

4、 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);printf(n);p. data=ch;p

5、. 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(BTNo

6、de);Tree= (BTNode*)malloc (sizeof (BTNode); for (i=0; KT. count; i+) (p i=GetTreeNode (T. nodei. data);)for (i=l;idata)j+； is=&pj;if(!(is-firstchild)is-firstchild=ip; ir=ip;elseir-rightsib=ip;ir=ip;Tree=&p0;return Tree;return Tree;）主菜单void Menu ()printfprintf (* 输入 1printf (*输入 2printf (*输入 3 printf

7、 (*输入 4 printf (*输入 5 printf (*输入 6printf (*输入 0 printf (zz=主菜单=以双亲法创立一般树对的免序遍历（递归）西的后序遍历（递归）两而先用遍历（非递回）两的后序遍历（非递回）层次序的非递归遍历退出程序请输入执行的指令=二、);*n);*n);*n);*n);*n);*n);*n); 二n);副菜单void Menu2 () printf (=副菜单=n);printf (*输入9返向菜单继续工作*n);printf (*输入 0退出程序*n)；主函数void main () int i=0, cl, c2;PTree T;BTNode *

8、Tree;init_ptree(&T);loop:Menu();scanf(%d, &cl);switch (cl) case 1printf(建立一般树，依次输入各个结点情况：n)；printf(输入结点方式：双亲数据，整型数据(第一个结点双亲数据为 T,最后以T, -1结束)n);T=CreatTree(T);Tree二change(T)printf (一般树柄换成二叉树后的情况n);PrintBTree(Tree, i);getchar ();break;printf (树的先序遍历(递归)：n)；preorder (Tree);printf(n);break;printf (树的后序遍

9、历(递归)：n)；inoeder (Tree);printf(n);break;printf(树的先序遍历(非递归)：n)；preorder2(T);printf(n);break;printf (树的后序遍历(非递归)：n)；inoeder2(T);printf(n);break;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);io4测试4.1测试数据（1）运行前面提到的程序后，会在计算

10、机窗口显示出程序所涉及的操作流 程“主菜单”。其内部包含用双亲法创立一般树、树的先序遍历等操作功能，如 下列图所示。后.D:学习专用软件C+练习、不成我练习晨Debuggu.exe”I = |向 11rrrrrr（图4.1主菜单）3in/输请：“半一 一建历历历令 一一创指 ?杀一号招序程仃 王双的的的的次出执 一一 入3333 一、V5 r-5 rd - TV 叔1遴炉 臀递4!.-1 % ill:. -1 二二-1 二二-1二；-111 二-111 二. - 11 * *（2）按照操作提示，首先输入1建立一般树，然后根据窗口提示一次输入 各个结点（例如是依次输入T, 1; 1, 2； 1,

11、 3； 2,4和-1, -1）,工作平台会 显示出下列图所示的操作过程。E2d：学习专用软件C+4练习春薪练习由Debuggu.exe-91乌遇台建立一根树，依次输入各个节点情困地入节尢或 双宗数塘，整理数据（第一个节点双亲数据为T，最后以-，T结束）输入第1个节表-1 1输入第2个节点2输入第3个节点3输入第4个节点4输入第5个节点-1 -1（图4.2例如操作数据）（3）输入上述所提供的例如之后，该程序会在工作平台显示运行结果，自 动生成一般树，并且输出树的具体情况（包括序号、结点和双亲）。在建立好一 般树之后，系统会自动把它转化为二叉树，并输出新形成的树的具体情况。同时,11程序主函数内部

12、的“副菜单”也会被调用（如下列图所示），从而显示出来供操作 者根据自身情况进行操作。 D:学习专用软件J+练习、木成氨练习Debuggu.exe4-14-1双杀2-1序号一般树转换成二叉树后的情况2单wt 保菜程 副回出 _返退9 0入入.ilsr.-一即* *01234继续工作34*MMM（图4.3树与二叉树的转换）（4）当进行完以上操作后，按照提示输入9后会重新显示一个如图4.L1所示的主菜单，然后输入3 （此为例如操作），会自动调用“树的后序遍历（递 归）”方法，在工作平台上显示此树的后序遍历结果，具体情形如下列图所示。请输入执行的指令弱的后序遍历（递归）： 4231=副菜单= 返回菜里

13、继续工作 退出程序（图4.4树的后序遍历）4. 2测试结果分析输出树中的“printf（,i,）“ D:学习专用费据供训内初实训谓C+原件De bugfwe.exe . D:学习专用费据供训内初实训谓C+原件De bugfwe.exe .rrr33333T;输请，712 3 4 5 6-Ill- nnn RnRn RnAnnnnt、 5rM- nJ 权 迸进炉 瞥递X * * X况 情4y 5 秋35几又6田1-第J入建输建历历历蟠令 一 一创指 单法liww5ts3 法M号瞿序程仃 王双的的的的次出执 一一 入个 各 入点ST次个依40（图4. 5测试结果）125课程设计体会通过本次课程设计

14、，我发现，有关一个课题的所有知识不仅仅是在课本上， 多查阅一些资料能够更好的完成课题，这就需要一种能力，即自学能力。本次课 程设计还让我认识到自己的缺点。本次选的课题是二叉树的遍历，因为本学期所 学的就是二叉树等数据结构，所以认为比拟适合。刚开始认为会很简单，但到后 来就出现一些难以解决的问题，就像老师请教，并查阅相关资料。经过慢慢的调 试，最终测试成功。这次课程设计让我所学到了许多数据结构知识，而且还拓展 了我的知识面，使我更加熟练的掌握各种方法。总之，这次课程设计增强了我的 自学能力，拓展了我的知识面，让我对数据结构更加了解。13参考文献1朱战立.数据结构一使用C语言（第四版）电子工业出版

15、社20092周海英.马巧梅数据结构与算法设计（第二版）国际工业出版社20053吴跃.数据结构和算法机械工业出版社20104严蔚敏.吴伟民数据结构：C语言版清华大学出版社20075刘振宇.数据结构（C语言版）.东软电子出版社14题目树与二叉树转换的实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设

16、计源代码的排版总评成绩指导教师评语:日期: TOC o 1-5 h z 1课程设计目标与任务11.1课程设计目标11. 2课程设计任务1 HYPERLINK l bookmark17 o Current Document 1.3课程设计所用设施12分析与设计22.1题目分析2 HYPERLINK l bookmark22 o Current Document 2. 2存储结构设计2 HYPERLINK l bookmark24 o Current Document 2. 3算法描述3 HYPERLINK l bookmark26 o Current Document 2.4程序流程图6 HYP

17、ERLINK l bookmark2 o Current Document 3程序清单7 HYPERLINK l bookmark0 o Current Document 4测试11 HYPERLINK l bookmark4 o Current Document 4.1测试数据11 HYPERLINK l bookmark8 o Current Document 4. 2测试结果分析12 HYPERLINK l bookmark10 o Current Document 5课程设计体会13 HYPERLINK l bookmark12 o Current Document 参考文献141课程

18、设计目标与任务课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学 是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计 基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作 方法学生通过数据结构课程设计各方面得到锻炼：(1)能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算 法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决 问题的有效算法；(2)通过上机实习，验证自己设计的算法的正确性，学会有效利用基本调试方 法，迅速找出程序代码中的错误并且修改；(3)培养算法分析能力，分析所设计算法的时间复杂度和

19、空间复杂度，进一 步提高程序设计水平；(4)尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形 方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。 1. 2课程设计任务根据提供的实习题目，认真完成软件设计的全部过程，并以最终软件设计成 果来证明其独立完成实际任务的能力，从而，反映出理解和运用数据结构与算法 的水平和能力，最后完成软件设计和程序调试并提交文档：课程设计报告书，报 告书中包含设计的算法及局部程序代码。3课程设计所用设施PC机、VC6.0语言编辑、编译运行工具、文档编辑软件等。2分析与设计2.1题目分析根据所提供的题目，是要实现树与二叉树的转换，而且可

20、以在程序设计中 调用使用。学生要认真完成能够实现题目要求的函数库。由于二叉树和树都可以 使用二叉链表作为存储结构，那么二叉链表作为媒介可导出树与二叉树之间的一个 对应关系。给定一棵树，可以找到唯一的一棵二叉树与之对应。2存储结构设计(1)设置头文件：#include#include#include(2)设置常量：ttdefine MAX_TREE_SIZE 100(3)一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点， 本实验运用到的是双亲结点和孩子兄弟结点，具体存储结构如下：Typedef structint data, parent/双亲位置域；PTNode;双亲表示法树结构：

21、Typedef struct PTNode nodeMAX_TREE_SIZE;int count;PTree;树的孩子兄弟结点表示结点结构定义：Typedef struct nodeint data;struct node *firstchild;struct node *rightsib;BTNode, *BTree;3算法描述按照程序执行先后顺序进行描述(1)树的构建完成后，用孩子兄弟表示法对树进行初始化结点，所用到的方 法是：BTNode GetTreeNode(int x) BTNode t;t.data =x;t.firstchild =t.rightsib =NULL;retur

22、n t;(2)树创立成功后，进行树的先序遍历，如果树不为空，先访问根结点，再 先序遍历左子树，然后先序遍历右子树。先序遍历二叉树基本操作方法是递归算 法，使用的方法是：void preorder (BTNode *T) if (T!=NULL)preorder(T-firstchild );preorder(T-rightsib );)(3)树的后序遍历中，如果树不为空，首先后序遍历左子树，再后序遍历右 子树，然后访问根结点，使用的方法是：void inoeder (BTNode *T) int i;for(;i=T. count-1;i-)printfT. nodei);树的层次遍历，如果二叉树非空，将根指针入队进行循环，直到队列为空,其方法是:void level (PTree T)for (i=0;iT. count;i+) printf(d，T. nodei);(5)用双亲表示法表示树，创立一维数组表示法，数组的元素具有两个数据 域data和双亲位置域parent,每一个元素对应一个数组下标，其方法是：PTree CreatTree(PTree T) int i=l;int fa, ch;PTNode p;for (i=l;ch!=-l;i+)T