树与二叉树转换实现-数据结构课程设计

1、河南工程学院数据结构与算法课程设计成果报告树与二叉树转换实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1342 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树转换实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成

2、 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1课程设计任务11.2 课程设计目标及要求12.1 题目需求分析22.2 存储结构设计22.3 算法描述32.4 程序流程图42.5 测试程序说明53 程序清单94 测试174.1 测试数据174.2 测试结果分析175 总结18参考文献181 课程设计目标与任务1.1课程设计任务1、设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自

3、己所缩写程序来实现相关问题的求解。1.2 课程设计目标及要求数据结构课程设计是计算机科学与技术专业集中实践性环节之一，是学习数据结构课程后进行的一次全面的综合练习。其目的就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体

4、情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；2 分析与设计2.1 题目需求分析本程序的功能是对任意二叉树进行与树的转换。本程序要求用户以字符输入，若要实现终端结点，最后以回车键建入数据。本程序的结果将依次打印出递归前序遍历和后序遍历，用栈实现非递归的前序和中序遍历和后序遍历，和线索化层序遍历，输入树及树传换成二叉树。2.

5、2 存储结构设计引入头文件：#include#include#include设置常量：#defineMAX_TREE_SIZE100 一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下：/*树的双亲表示结点结构定义*/typedefstructintdata;intparent;/双亲位置域PTNode;/*双亲表示法树结构*/typedefstruct PTNodenodeMAX_TREE_SIZE;intcount;/根的位置和节点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedefstructnodeint

6、data;structnode*firstchild;structnode*rightsib;BTNode,*BTree;2.3 算法描述一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。 输入一个二叉树的先序序列，构造这棵二叉树。为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如，#。在算法中，需要对每个输入的字符进行判断，如果对应的字符是#，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递

7、归调用返回时完成。 计算一棵二叉树的叶子结点数目 这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。首先要知道 树(森林)转换成二叉树的方法。一般是把树(森林)当前结点的的孩子当成左子树(或右子树)，层层转换而得到一个新的二叉树。 根据树(森林)转换二叉树的方法，逆向回去，就可以得到二叉树转换树的算法。/*树的双亲表示结点结构定义*/typedefstructintdata;intparent;/双亲位置域PTNode;/*双亲表示法树结构*/typedefstruct PTNodenod

8、eMAX_TREE_SIZE;intcount;/根的位置和节点个数PTree;2.4 程序流程图编译运行，进入主菜单选择界面，选择1创建二叉树，按格式输入各个节点。此时可以选择2输出各个节点情况，亦可以选择3输出前序遍历结果，选择4输出后序遍历结果，亦或是选择5调用Transform()将二叉树转换为树，继而根据提示输入置顶功能进行树的遍历输出功能，最后选择0退出程序开始 退出程序主菜单后序遍历建立指定的二叉树双亲法建树前序遍历将二叉树转化为树按格式输入各节点输出节点 情况输出遍历结果副菜单退出程序图2.4程序流程图2.5 测试程序说明程序开始：图2.5.1程序开始界面建立一棵树：输入指令1

9、。图2.5.2输入指令1界面输入结点的方式：双亲数据（整形），节点数据（整形）以-1,-1结束。如：-1,1 1,2 -1，-1图2.5.3输入结点界面一般树创建完的具体情况：图2.5.4创建树界面把一般树转换为二叉树后：图2.5.5树与二叉树的转换界面3 程序清单#include #include #include #define MaxSize 100typedef char ElemType;typedef struct bnode/二叉树定义ElemType data;struct bnode *lchild;struct bnode *rchild; bTNode,bTree;voi

10、d insertBTNode(bTNode *&b,char *str)/由str串创建二叉链bTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/建立的二叉树初始时为空ch=strj;while (ch!=0)/str未扫描完时循环 switch(ch) case (:top+;Sttop=p;k=1; break;/为左结点case ):top-;break;case ,:k=2; break; /为右结点default:p=(bTNode *)malloc(sizeof(bTNode);p-data=ch;p-lchild

11、=p-rchild=NULL; if (b=NULL) /p指向二叉树根结点b=p;else /已建立二叉树根结点switch(k) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;void preOrder(bTNode *T)if(T!=NULL)printf(%c ,T-data);preOrder(T-lchild);preOrder(T-rchild);/树的相关操作/*树的双亲表示结点结构定义*/typedef struct int data; int parent; /双亲位置域PTNode;/

12、*双亲表示法树结构*/typedef struct PTNode nodeMaxSize; int count; /根的位置和节点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct nodeint data;struct node *firstchild;struct node *nextchild;BTNode,*BTree;/初始化树(双亲表示法)void init_ptree(PTree *tree) tree-count=-1;/初始化树结点(孩子兄弟表示法)BTNode GetTreeNode(int x)BTNode t;t.data=x;t.firs

13、tchild=t.nextchild=NULL;return t;/树的前序遍历void preorder(BTNode *T)if(T!=NULL)printf(%d ,T-data);preorder(T-firstchild);preorder(T-nextchild);/树后序遍历(递归)void inoeder(BTNode *T)if(T!=NULL)inoeder(T-firstchild);printf(%d ,T-data);inoeder(T-nextchild);/水平输出二叉树void PrintBTree(BTNode *root,int level) int i;

14、if(root!=NULL) PrintBTree(root-nextchild,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;

15、int fa,ch;PTNode p;printf(请依次输入各节点（以数据域0结束）：);for(i=1;ch!=-1;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 pMaxSize

16、;BTNode *a,*b,*c,*Tree;a=(BTNode *)malloc(sizeof(BTNode);b=(BTNode *)malloc(sizeof(BTNode);c=(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+;b=&pj;if(!(b-firstchild)b-firstchild=a;c=a;elsec-nextchild=a;c=a;Tree=&p

17、0;return Tree;/*主菜单*/void Menu()printf(nnnn);printf( 主菜单 nnn);printf(*选项【1】* 创建一棵树nn); printf(*选项【2】* 树的前序遍历nn); printf(*选项【3】* 树的后序遍历nn);printf(*选项【4】* 建立一个指定的二叉树nn); printf(*选项【0】* 退出程序nn); printf( =n); printf(请输入执行的指令:);void Menu2()printf( *选项【5】* 返回主菜单 n);printf( *选项【0】* 退出程序 n);/*主函数*/void main

18、() int i=0,c1,c2; PTree T; BTNode *Tree;bTNode *b; init_ptree(&T); loop: Menu();scanf(%d,&c1); switch(c1) case 1: printf(输入结点方式:双亲，数据域n);T=CreatTree(T);Tree=change(T); 4 测试4.1 测试数据建立一棵树：输入指令1。输入结点的方式：双亲数据（整形），节点数据（整形）以-1,-1结束。-1,1 1,2 -1，-14.2 测试结果分析对于测试结果（详见2.5），比较符合实验预期效果，能够进行树与二叉树的转换，而且能够输出树的先序遍历

19、，后序遍历。唯一美中不足的是界面尚不美观，有待优化。5 总结以前编程的时候，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭意识和简单的语句来堆砌出一段段程序。现在变成感觉完全不同了。在编写一个程序之前，自己能够综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么。然后再选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以自习斟酌出对挑选出最合适当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写程序的质量。另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样

20、定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。这次试验也让我看到了自己的不足，还是不太用模版类。还有许多关于C的一些比较具体的东西还不太懂，比方说指针。这次实验还让我意识到只有不管在机子上调试程序，自己的水平才能得到提高。我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步和提高。参考文献1谭浩强.C语言程序设计（第四版）.清华大学出版社2严蔚敏.数据结构（C语言版）.清华大学出版社3谭浩强.C+面向对象程序设计.清华大学出版社4冯舜玺.数据结构与算法分析:C语言描述(第二版).机械工业出版社5严蔚敏.数据结构习题册（

21、C语言版）.清华大学出版社#include #include #include #define MaxSize 100typedef char ElemType;typedef struct bnode/二叉树定义ElemType data;struct bnode *lchild;struct bnode *rchild; bTNode,bTree;void insertBTNode(bTNode *&b,char *str)/由str串创建二叉链bTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/建立的二叉树初始时为空ch

22、=strj;while (ch!=0)/str未扫描完时循环 switch(ch) case (:top+;Sttop=p;k=1; break;/为左结点case ):top-;break;case ,:k=2; break; /为右结点default:p=(bTNode *)malloc(sizeof(bTNode);p-data=ch;p-lchild=p-rchild=NULL; if (b=NULL) /p指向二叉树的根结点b=p;else /已建立二叉树根结点switch(k) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;br

23、eak;j+;ch=strj;void preOrder(bTNode *T)if(T!=NULL)printf(%c ,T-data);preOrder(T-lchild);preOrder(T-rchild);/树的相关操作/*树的双亲表示结点结构定义*/typedef struct int data; int parent; /双亲位置域PTNode;/*双亲表示法树结构*/typedef struct PTNode nodeMaxSize; int count; /根的位置和节点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct nodeint data;

24、struct node *firstchild;struct node *nextchild;BTNode,*BTree;/初始化树(双亲表示法)void init_ptree(PTree *tree) tree-count=-1;/初始化树结点(孩子兄弟表示法)BTNode GetTreeNode(int x)BTNode t;t.data=x;t.firstchild=t.nextchild=NULL;return t;/树的前序遍历void preorder(BTNode *T)if(T!=NULL)printf(%d ,T-data);preorder(T-firstchild);pr

25、eorder(T-nextchild);/树后序遍历(递归)void inoeder(BTNode *T)if(T!=NULL)inoeder(T-firstchild);printf(%d ,T-data);inoeder(T-nextchild);/水平输出二叉树void PrintBTree(BTNode *root,int level) int i; if(root!=NULL) PrintBTree(root-nextchild,level+1); for(i=1;idata); PrintBTree(root-firstchild,level+1); /输出树void print_

26、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;printf(请依次输入各节点（以数据域0结束）：);for(i=1;ch!=-1;i+)scanf(%d,%d,&fa,&ch);printf(n);p.data=ch;p.parent=fa;T.

27、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 pMaxSize;BTNode *a,*b,*c,*Tree;a=(BTNode *)malloc(sizeof(BTNode);b=(BTNode *)malloc(sizeof(BTNode);c=(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+;b=&pj;if(!(b-firstchild)b-firstchild=a;c=a;elsec-ne