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

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

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

2、 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 (B TN ode *T)(if(T!=NULL)(printf(n%d H,T-data);prcordcr(T-firstchild);preorder(T-rightsib);

3、)/树的前序遍历(非递归)void preorder2(PTree T)7 int ij=O;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=l ;idat

4、a)(j+；is=&pj;)if(!(is-firstchiid)is-firstchild=ip;ir=ip;else(ir-rightsib=ip; ir=ip;)Tree=&p0;return Tree;)/*主菜单*/void Menu()(printfC*-=M=nn);printf(*输入1以双亲法创立一棵一般树*n)；printf(”*输入2树的前序遍历(递归)*n)printf，*输入3树的后序遍历(递归)*n”)；输入4树的前序遍历(非递归)*n);printf(*输入5树的后序遍历(非递归)*rT);printf(*输入6层次序的非递归遍历*n”)；printf(*输入 0

5、退出程序*n)printf(=n); printf。请输入执行的指令/*副菜单*/void Menu2()pnntf( * pjij. * *n) printf(*9 printf(*O /*主函数*/返回主菜单继续操作*n);退出程序*n)void main() int i=0,cl,c2;PTree T;BTNode *Tree;init_ptree(&T);loop: Menu();scanf(H%dH,&cl);switch(cl)(case 1:printf(建立一般树，依次输入各个结点情况:n)prints输入结点方式:双亲数据，整型数据(第一个结点双亲数据为-1,最后以-1,-1

6、 结束)n 例子:-1/l,3n)T=CreatTree(T);Tree=change(T);printf(一般树转换成二叉树后的情况:n)PrintBTree(Tree,i)； getchar();break;case 2:printf(树的前序遍历(递归):n)preorder (Tree);printf(HnH);break;case 3:printf(树的后序遍历(递归):n)inoeder(Tree);printf(HnH);break;case 4:printf(树的前序遍历俳递归):n”)；preorder2(T);printf(HnH);break;case 5:printf(

7、树的后序遍历俳递归):n”);inoeder2(T);printf(nnn);break;case 6:printf(树的层次遍历:n”)；level(T);printf(nnn);break;case 0:exit(l);break;)Menu2();scanf(d&c2);if(c2=9)goto loop;else if(c2=0)exit(l);)104测试4.1测试数据根据选项输入一个数a C: JlSOFTCYuYanbinwteBp. exe*输入1*输入2*输入3*输入4主菜单= 以双亲法创立一棵一般树树的前序遍历（非递归）*输入5树的后序遍历（非递归）* 输入6层次序的非递归

8、遍历* 树的前序遍历（递归）* 树的后序遍历（递归）*输入o退 * 程序 *请输入执行的指令:.图 4. 1-1补 C:JISOFTCYuYanbinwvteBp.ezek*输入1k*输入2k*输入3畤*输入4k*输入5 k*输入6k*输入0主菜单二二二二二二二二二二二二二二-二二二二二 以双菱法创立一棵一般树林* 树的前序遍历（递归）* 树的后序遍历（递归）* 树的前序遍面（非递归）* 树的后序遍历（非递归）* 层次序的非递归遍历* 退出程序 *清输入执行的指令：1建立一般树,依次输入各个结点情况：前入结点方式:双亲数据,整型数据（第一个结点双亲数据为最后以T结束）列子:T,1 1,3俞入第

9、1结点：图指令输入图表11通过输入数据来访问*轴入2树的刖序遍历（递归）* *输入3树的后序遍历（递归）*输入4树的前序遍历（非递归）* *输入5树的后序遍历（非递归）*输入6层次序的非递归遍历* * 输入 0退出程序* 清谕入执行的指令：1建立一般树,依次输入各个结点情况：输入结点方式:双亲数据,整型数据（第一个结点双亲数据为-1,最后以T, T结束）例子：-1,1 1,3输入第1结点：-1,1输入第2结点: 1,2输入第3结点:1,3输入第4结点:2,4图4. 1-3遍历方法输入结点方式:双亲数据,整型数据（第一个结点双亲数据为-1,最后以T, -1结束）例子：-1,1 1,3输入第1结点

10、：-1U输入第2结点:1,2输入第3结点:1,3输入第4结点:2,4输入第5结点: 一T创立的树具体情况如下:序号结点双亲01-11212313424-1-14. 1-4各节点属性12完成树的创立c C:JlSOFTCTuTanbinwteBp. exe创立的树具体情况如下： 序号结点双亲01-1211 31422 -1T一般树转换成二叉树后的情况:13W* 割单*9返回主菜单继续操作*0退出程序*D :CYuYanbin wwtemp .exe般树转换成二叉树后的情况:i副是 s. * 返回至塞单继续操作* 退出程方*二 二 二 二 二 二 二二 二 二 二 二二 二 二 二 二 33二 二

11、 二 二 二 二 二 历xz xz d/d/_ 果归归速递一递非战遍“归二 二 二 二 二 二 二 二 二 二 二 二 二一一建历历历历递2 一一创遍遍遍遍非共 一一 序 -HH 一一或的的的的次出 单以 Izlro:1 菜一二二二 主12 3 4 5 6 0JAJAJAlAlAJAA*营艳入执行的指令：2 陶的前序逋历递归:12 4 3MMMMgl |.XXXXXXXXXXXXXXXXXXX t-r t-r v-r O返回王用单继续操作*出XMMXXXXMXMXXXXMMX4. 2-1转换后的情况13-返回王差单继续操作*一退出XX XX XX XX XX XX XX XXXXXXXXXX退

12、出程序*副 米_ * 一返回王楚单继续操作* 艮 出 序 XM* W* w* W*x*亍的指令：2 0历12 3 4 5 6 0 入入入入入入入主菜单= = = = = = = = = = = = = = = = = = = = = = = 以袤亲法画港争一羹就 ；用的前序遍历递归X 啖的后住遍历 递归） 利的前序遍历（非递归* 洞的后序遍历琲递归* 层次序曲非递归遍历41 的历 1- D:CYuYanbinwwtemp.exe-|n|x|12 3 4 5 6 0入入入入入入入一一建历历历历递8 一一创遍遍遍遍非共 一一；fWWbS 序 -HH 一 一刀的的的的次出 单次WKn 菜二一二二 主

13、 树二二 * 二 二 二二 * 二 二 二 二 二 二 二请艳人执行的指令：6 树的层次逋历：12 3 4*副米-3- XXXXXXXXXXXXXXXXXXX返回至用单继续操作*艮出 E序 XXXXXXXXXXXXXXXXX图4. 2-3程序的执行14平王程米回出副返退MMM0Press any key to continue图 4. 2-45总结通过本次程序设计，让我更深层次地了解到了树各种函数的运用，如何运用 各种存储结构创立树，以及在实验中还涉及到递归的运用，递归的思想省去了复 杂的算法设计。在实验中不可防止的出现了大大小小的问题，在调试中透彻领悟 各种算法的真谛，同样的错误在下次遇到时

14、就可以防止了。15参考文献1谭浩强C语言设计第四版清华大学出版社2谭浩强C+面向对象程序设计清华大学出版社3谭浩强.C语言程序设计教程M.第3版.高等教育出版社，20064刘振安.C语言程序设计M .机械工业出版社，200716题目树与二叉树转换实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设

15、计源代码的排版总评成绩指导教师评语:日期:17错误!未定义书签。错误!未定义书签。课程设计目标及任务1.1 课程设计目标1.2 课程设计任务1.3 课程设计分析22分析与设计32.1 题目需求分析42.2 存储结构设计42.3 算法描述52.4 程序流程图73程序清单74测试94. 1测试结果105总结12参考文献161课程设计目标与任务1.1课程设计目标了解树与二叉树的转换，以及掌握树的前序，后序的递归，非递归遍历算法, 成次序的非递归算法的实现，应包含建树的实现。1. 2课程设计任务实现树与二叉树的转换的实现，以及树的前序、后序的递 归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含

16、建树的实现。（多 种遍历可以只实现一个）2. 3课程设计分析设计过程步骤如下：一 .二叉树创立。二 .先序遍历二叉树的递归算法。三 .后序遍历二叉树的递归算法。四 .先序非递归算法。五 .后序非递归算法。六 .层次序遍历算法。2分析与设计通过分析题目和设计算法来更好的解释树树与二叉树的转换。3. 1题目分析1 .二叉树创立用链表实现创立一个树结点的结构体，从键盘输入数据，存入数组。把下标 为2*i+l的值存入左孩子，为2*i+2的存入右孩子。2 .先序遍历二叉树的递归算法假设二叉树为空，那么空操作；否那么(1)访问根结点；(2)先序遍历左子树； (3)先序遍历右子树。void PreOrder

17、 (BiNode root) o3 .后序遍历二叉树的递归算法假设二叉树为空，那么空操作；否那么(1)后序遍历左子树；(2)后序遍历右子 树。(3)访问根结点；void PostOrder (BiNode root) 04 .先序非递归算法BiNode根指针，假设BiNode!= NULL对于非递归算法，引入栈模拟递归工作 栈，初始时栈为空。5 .后序非递归算法BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问 根。需要判断根结点的左右是否均遍历过。void F_PostOrder(BiNode root) 6.层次序遍历算法按照树的层次从左到右访问树的结点，层序遍历用于保

18、存结点的容器是队 歹(J。void LevelOrder(BiNoderoot)o2. 2存储结构设计ftinclude ftinclude ftinclude 设置常量：#define MAX_TREE_SIZE 100一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下:/*树的双亲表示结点结构定义*/typedef structint data;int parent;双亲位置域PTNode;/*双亲表示法树结构*/typedef structPTNode nodeMAX_TREE_SIZE;int count;根的位置和节

19、点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct node int data;struct node *firstchild;struct node *rightsib;BTNode, *BTree2. 3算法描述树的初始化函数（双亲法和孩子结点法两种），建树函数，输出树函数，树 的前序遍历函数（递归和非递归两种），树的后序遍历函数（递归和非递归两种）， 树的层次遍历函数，一般树和二叉树的转换函数。主菜单和副菜单。主函数。 具体代码如下：初始化树（双亲表示法）void init ptree （PTree *tree） tree-count=-l;初始化树结点（

20、孩子兄弟表示法）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-firstchiId);preorder (T-rightsib);树的前序遍历(非递归)void preorder2(PTree T)(int i;for (i=0;iT. count;i+)printf (/z%d , T, nodei);)2. 4程序流程图该流程图各种数据结构方法描述了程序的执行图2. 4-1过程及方法的描述