树与二叉树的转换实现16.docx

河南工程学院数据结构与算法课程设计成果报告树与二叉树的转换实现2014年12月29日2. 5测试程序说明本次课程设计任务是完成树与二叉树的转换，将（a）树转换成二叉树其步 骤及过程如下：(b)(2)抹线：就是对树中的每个结点只保存它与左孩子结点之间的连线，删 除它与其它孩子结点之间的连线。(3)旋转：就是以树的根结点为轴心，将整棵树顺时针旋转45度，使二叉 树结构层次清楚。三、程序清单#include<stdio.h>#include<malloc.h>#include<stdlib.h>#define MAX_TREE_SIZE 100/*树的双亲表示借点结构定义*/typedef struct int data;int parent;双亲位置域PTNode;/*双亲表示法树结构*/typedef structPTNode nodeMAX_TREE_SIZE;int count; 根的位置和结点个数 PTree;/*树的孩子兄弟表示结点结构定义*/ typedef struct node (int data;struct node*firstchild;struct node*rightsib;)BTNode/BTree;初始化树(双亲表示法) 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 ",T->data);preorder(T->firstchild);9preorder(T->rightsib); 树后序遍历void inoeder(BTNode *T) if(T!=NULL) inoeder(T->firstchild);printf("%d HJ->data);inoeder(T->rightsib); 水平输出二叉树void PrintBTree(BTNode*root,int level) (int i;if(root!=NULL)(PrintBTree(root->nghtsibJevel+l);for(i=l;i<8*level;i+)printf("n);printf(H%dnn,root->data);PrintBTree(root->firstchildJevel+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); printfC'Xn");)/*用双亲表示法创立树*/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.parent=fa;10T.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=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;i<T.count;i+) pi=GetTreeNode(T.nodei.data); for(i=l;i<T.count;i+) ip=&pH；is=&pj；while(T.nodei.parent !=is->data)j+；is=&pj； if(!(is->firstchild) is->firstchild=ip;ir=ip; else ir->rightsib=ip;ir=ip;)Tree=&p0;return Tree;/*主菜单*/void Menu()printf("=二二二二二二二主菜单print"'*输入1以双亲法创立一棵一般树*n“）;printf（"*输入2树的前序遍历*n"）;printf（"*输入3树的后序遍历*n"）;printfC'*输入 0printfC'*输入 0退出程序n");printf("=n"); printf(”请输入执行的指令：”);11/*副菜单*/void Menu2()printf(" * gjij 单.* * *门")printf("*9返回主菜单继续操作* *n'');退 出 程序 */*主函数*/void main() int i=0,cl,c2;PTree T;BTNode*Tree;init_ptree(&T);loop:Menu();scanf("%d",&cl);switch(cl)printf("建立一般树，依次输入各个结点情况：n");printf(“输入结点方式：双亲数据，整型数据(第一个结点双亲数据为-1,最后 以-L -1 结束)n 例子：-1, 11, 3n");T=CreatTree(T);Tree=change(T);printfC'一般树转换成二叉树后的情况：n“)；PrintBTree(TreeJ);getchar();break;printf("树的前序遍历:n“);preorder(Tree);printf("nH);break;case 1: printf("树的后序遍历:n“);inoeder(Tree);pnntf("n");break;case 0:exit ； break; Menu2();scanf("d=&c2);if(c2=9) goto loop; else if(c2=0)exit ；12测试4.1 测试数据1 .程序开始，建立一棵一般树：输入指令1,双亲法创立一棵一般树，然 后输入结点，输入结点方式：双亲数据（整型），结点数据（整型）以-1, -1结 束，如：-1, 11, 2-1, -lo 一般树创立完及一般树转换成二叉树的具体情况如图4-1：图4-1 树转换二叉树图132 .副菜单项选择择9返回主菜单后输入指令2,执行树的前序遍历，如图4-2：印123exe-1叫XK-1-1一般树转换成二叉树后的情况:|x*关关x*xx*xx-x*xx*x 曷11 菜当g xxxxx-xxx*xxxxxxxxxxx 返回主楚单继续操作* 退 ,"rp 序 XX XX XX XX XX XX XX XX XX XXXm-M-MX M X w.w WM M Mm-M-MX M X w.w WM M M12 3 0IJAIJAIJAI1A福淘输淘=主菜单=以双亲法创立一棵一般树利的前匠遍曾电后每遍历*遍历xxxxxxxxxxxxxxxxx膻胸垫口的指令：2 阚曲前序遍历：" 副菜单k*9 返回主爰单继续操作rt*1退出程序 XXXXXX-XXXXXXXXXXX图4-2树的前序遍历图-lx3 .副菜单项选择择9返回主菜单后输入指令3,执行树的后序遍历，如图4-3：c *E: 曾亚男'区*xDebug区工工. exe12 3 0 人入入入12 3 0 人入入入诙双亲法创立一楝一瓶祠的前序遍历*的后序遍历鬻霹逋驰班行的指令：2的曲前序逋历：1 3_xxxxxxxxwxwxxwxxwxxx昌11是 ffi.*)e)«e)e*_ a. *_ 4 . d - d a八 a1返回主菜单继续操作*| 卜. i I I .' I | T 'M-M-M12 3 0IJAIJAI1AI1A输输输4痢主菜单双亲法仓雇一楝一羹祠 树的前序遍历*X 树的后任遍历*退出!程，序 XXXXXXXXXXXXXXXXX的指令：31*9XMMXMMXMXXMXXXMMMXMX返回丰菜单继续操作XXXXXXXXXMXXMXXXMMX图4-3树的后序遍历图4.程序操作完毕后，副菜单项选择择0退出程序。144. 2测试结果分析在Microsoft Visual C+ 6. 0软件中建立一个空的工程，然后新建一个 C+ Source File文件，编写程序代码，后对编写的程序进行编译，直到程序 没有错误，最后执行程序，输入要测试的数据，得出执行结果。在调试过程中出现了很多问题，定义表过长，处理记录数据错误是程序的异 常，记录冲突次数，输入树的结点时总是进入死循环等等。通过问同学，查资料, 对程序进行了一系列的修改，在编译没有错误后，运行程序。根据程序的提示， 首先根据指令输入信息，生成一棵树后，再将生成的树转换成二叉树，输出二叉 树的结构图，然后根据指令选择是继续进行树与二叉树的转换或者退出程序。15五、总结之前上数据结构的理论课和实践课，对数据结构的算法的理解都是很模糊 的，很多算法的掌握都很生疏，所以导致在这次课程设计中，出现了很多问题， 算法的不完善、调试程序时总是出错、总是进入死循环等等，对这些错误，我不 得不花费大量的时间查找资料去更正，并且还要重复检查是否出现雷同的错误而 导致程序不能运行。但是通过这次课程设计，加强了我的动手能力，以及提升了局部和统一考 虑问题的思维方式。在进行程序设计的时候，要注意想好思路，即要有恰当模块 名、变量名、常量名、子程序名等。将每个功能的模块，即函数名要清晰的表述 出来，使用户能够一目了然此程序的功能。当然适当的给些注释，也是方便用户 的理解，还有在编写程序时要注意对程序的适当分配，便于用户看懂程序，也便 于自己检查程序。但是完成任何一个较大的程序，都需要掌握一定的编程基础， 需要不断的探索和求知过程，这样对自己编程能力的提高有较大的帮助。当然， 任何程序都必须经过计算机的调试，看是否调试成功，发现错误，一个个，一步 步去解决，这样就能从错误中进步。16题目树与二叉树的转换实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:参考文献1严蔚敏.数据结构（C语言版）.清华大学出版社王路群.数据结构-C语言描述.中国水利水电出版社3王国钧.数据结构实验教程（C语言版）.清华大学出版社4严蔚敏等.数据结构题集.清华大学出版社5殷人昆.数据结构（C语言描述）.机械工业出版社17一、课程设计目标与任务11.1课程设计目标11. 2课程设计任务11. 3课程设计要求1二、分析与设计22.1题目分析22. 2存储结构设计22 . 3算法描述33 .4程序流程图52. 5测试程序说明7三、程序清单9四、测试134.1测试数据134. 2测试结果分析15五、总结16参考文献17课程设计目标与任务1.1课程设计目标通过本课程设计，使我们在数据结构的选择和应用、算法的设计与实现方面 得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法 及上机操作方面受到比拟系统严格的训练，培养软件工作所需要的动手能力。通 过本课程设计，使我们进一步深化掌握c语言的基本知识；掌握结构化程序设计 的基本方法和设计技巧，进一步了解算法分析与设计概念；理解面向对象程序设 计思想，初步具备运用面向对象程序设计方法进行程序设计的能力。能熟练应用 VC+集成环境进行C+语言程序的编写、编译与调试，提高自己对本课程知识综 合运用能力。1. 2课程设计任务设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1. 3课程设计要求根据提供的课程设计的题目，掌握程序分析方法，学会程序设计的基本方法, 认真完成题目的要求，从而增强理解和运用C+程序知识的能力，并以最终程序 运行结果来证明完成课程设计任务，最后完成题目要求和程序调试并提交文档， 课程设计报告书中包含算法及局部程序代码。二、分析与设计2.1题目分析这个程序的功能是对任意二叉树用栈实现树与二叉树的转换，要求用户以字 符输入，假设要实现终端结点，最后以回车键键入数据，程序的结果将打印出树及 树转换成的二叉树。2. 2存储结构设计树是一种非线性的数据结构，树中的元素之间是一对多的层次关系。一般树 的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。这个程序运用到 的是双亲结点和孩子兄弟结点。具体存储结构如下：/*树的双亲表示借点结构定义*/typedef structint data;int parent;双亲位置域PTNode;/*双亲表示法树结构*/typedef struct(PTNode nodeMAX_TREE_SIZE;int count; 根的位置和结点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct node(int data;struct node*firstchild;struct node*rightsib;BTNode,*BTree;2. 3算法描述(1)用双亲表示法创立一棵树：创立树的结点，同时在每个结点中附设一 个指针指示结点在链表中位置，具体代码如下：PTree CreatTree(PTree T)(int i=l;int fa,ch;PTNode p;for(i=l;ch!=-l;i+)(printf("输入第d 结点:n，i);scanf("%d,%cT,&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("创立的树具体情况如下:rT);print_ptree(T);return T;)(2)树与二叉树的转换：转换时结点的第一个孩子变为它的左孩子，兄弟 结点变为它的右孩子。用孩子兄弟表示法将树转换为即以二叉链表作树的存储结 构，链表中结点的两个域分别指向该结点的第一个孩子结点和右侧第一个兄弟结 点，当你将这两个指针看作是二叉树中的左孩子指针和右孩子指针时，就是一棵 二叉树了。具体代码如下：BTNode*change(PTree T)int i,j=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;i<T.count;i+) (pi=GetTreeNode(T.nodei.data); for(i=l;i<T.count;i+) (ip=&pi；is=&pj;while(T.nodei.parent !=is->data)(j+； is=&pj；) if(!(is->firstchild) (is->firstchild=ip;ir=ip;) elseir->rightsib=ip;ir=ip;)Tree=&pO;return Tree;(3)树的前序遍历：先访问根结点，再遍历左子树，最后遍历右子树。具 体代码如下：void preorder(BTNode *T) if(T!=NULL) printf("%d ",T->data);preorder(T->fi rstch ild);preorder(T->nextchild);)(4)树的后序遍历：先遍历左子树，再遍历右子树，最后访问根结点。具 体代码如下：void inoeder(BTNode *T) if(T!=NULL) inoeder(T->firstchild);printf("%d ",T->data);inoeder(T->nextchild);)2. 4程序流程图程序开始后首先进入主菜单，选择是用双亲法创立一棵一般树还是退出程 序，假设选择退出程序，那么程序关闭；假设选择用双亲法创立一棵一般树，那么进入下 一项，按照程序给出的格式从键盘输入各个结点，计算机会根据程序的流程输出 树的结点情况，同时会输出一棵一般树创立完成的具体情况，然后计算机会根据 程序的步骤将这棵一般树转换成二叉树。最后进入副菜单，用户根据需求选择继 续进行树与二叉树的转换或者退出程序，流程图如图2-1所示。开始> 主菜单>退出程序双亲法建树按照格式输入各个结点输出树的结点情况一般树转换成二叉树副菜单退出程序图2-1 程序流程图