树与二叉树的转换实现-数据结构与算法课程设计定稿

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

2、评 成 绩指导教师评语： 日期： 年 月 日目 录一、 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3课程设计要求1二、分析与设计22.1 题目分析22.2 存储结构设计22.3 算法描述32.4 程序流程图62.5测试程序说明7三、 程序清单9四、测试134.1 测试数据134.2 测试结果分析13五、总结16参考文献17一、 课程设计目标与任务1.1 课程设计目标学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理，理解面向对象程序设计思想，初步具备运用面向对象程序设计方法进行程序设计的能力。通过本课程设计，使我们进一步深化掌握C语言和C+的

3、基本知识，进一步了解算法分析与设计，掌握数据结构与算法的基本设计方法，初步具备程序设计的能力，在算法的设计与实现方面得到更强的训练，加深对数据结构基本内容的理解和灵活应用，提高综合运用所学理论知识和方法独立分析和解决问题的能力。能熟练应用VC+集成环境进行C+语言程序的编写、编译与调试，提高自己对本课程知识综合运用能力。1.2 课程设计任务设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现

4、相关问题的求解。1.3课程设计要求根据提供的课程设计的题目，要求先对问题进行分析，了解题目的要求，学会程序设计的基本方法，认真完成题目的要求。本次课程设计的要求是将树转换为二叉树，将抽象的数据结构以图形方式显示出来，画出流程图选择合适算法写出程序，并以最终程序运行结果来证明完成课程设计任务，最后完成题目要求和程序调试并提交文档，课程设计报告书中包含算法及程序代码，程序流程图及测试结果分析等。二、分析与设计2.1 题目分析对题目的分析是课程设计的一个重要环节，通过对题目的分析，可以更好的理解题目，能更快更好的完成课程设计。本程序的功能进行树与二叉树的转换，其中包含树的结构体的建立，对树进行前序和

5、后序遍历以及对二叉树进行递归前序遍历和后序遍历。本程序要求以数值输入，本程序的结果将输出一棵树及树转换成二叉树，树的前序和后序遍历以及指定二叉树的前序、中序和后序遍历。2.2 存储结构设计树是一种非线性的数据结构。常用的有三种存储结构，本程序中用的是双亲表示法和孩子兄弟表示法，用双亲表示法一般采用顺序存储结构，即用一组连续空间存储树的结点，同时在每个结点中附设一个指针指示结点在链表中位置；用孩子兄弟表示法即以二叉链表作树的存储结构，链表中结点的两个域分别指向该结点的第一个孩子结点和右侧第一个兄弟结点，当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。/二叉链表的创建B

6、iTree* createTree() DataType ch; Bitree *T; ch=getchar();if(ch=#) return NULL;Else T=(BiTree*)malloc(sizeof(BiTree); T-data=ch; T-lchild=createBiTree(); T-rchild=createBiTree(); return T; /树的双亲表示借点结构定义typedef structint data;int parent; PTNode;/双亲表示法树结构typedef structPTNode nodeMAX_TREE_SIZE;int count

7、; PTree;/树的孩子兄弟表示结点结构定义typedef struct nodeint data;struct node*firstchild;struct node*rightsib;BTNode,*BTree; 2.3 算法描述（1）用双亲表示法创建一棵树：创建树的结点，同时在每个结点中附设一个指针指示结点在链表中位置PTree CreatTree(PTree T)int i=1;int fa,ch;PTNode p;printf(请依次输入各结点（以数据域-1结束）：);for(i=1;ch!=-1;i+)scanf(%d,%d,&fa,&ch);printf(n);p.data=c

8、h;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;（2） 树与二叉树的转换：用孩子兄弟表示法将树转换为即以二叉链表作树的存储结构，链表中结点的两个域分别指向该结点的第一个孩子结点和右侧第一个兄弟结点，当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。 BTNode *change(PTree T)int i,j=0;BTNode pMaxSize;B

9、TNode *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; Tre

10、e=&p0; return Tree;（3）树的前序遍历：先访问根结点，再遍历左子树，最后遍历右子树。 void preorder(BTNode *T) if(T!=NULL) printf(%d ,T-data);preorder(T-firstchild);preorder(T-nextchild); （4）树的后序遍历：先遍历左子树，再遍历右子树，最后访问根结点。 void inoeder(BTNode *T)if(T!=NULL) inoeder(T-firstchild);printf(%d ,T-data);inoeder(T-nextchild); 2.4 程序流程图本程序开始后

11、进入主菜单选择用双亲法创建一棵树或退出程序，选择用双亲法创建一棵一般树，则进入下一项按格式其结点，计算机会根据程序的流程输出树的结点情况，同时会输出一棵一般树创建完成的具体情况，然后计算机会根据程序的步骤将这棵一般树转换成二叉树。最后进入副菜单，用户根据需求选择返回主菜单继续进行树与二叉树的转换还是退出程序，流程图如图2-1所示。一般树转换成二叉树退出程序退出程序开始主菜单双亲法建树按照格式输入各个结点输出树的结点情况副菜单开始主菜单双亲法创建树退出程序按照格式输入结点值输出树的结点情况一般树转换成二叉树副菜单 退出程序图2-1 程序流程图2.5测试程序说明本次课程设计任务是完成树与二叉树的转

12、换，将（a）树转换成二叉树其步骤及过程如下：AEDBFC （a)(1)加线：就是在所有兄弟结点间加一条线；ADBCEF（b）（2）抹线：就是对树中的每个结点只保留它与左孩子结点之间的连线，删除它与其它孩子结点之间的连线；ABDCEF（c）（3）旋转：就是以树的根结点为轴心，将整棵树顺时针旋转45度，使二叉树结构层次分明。ABECFD（d）3、 程序清单 #include #include #include #define MaxSize 100typedef char ElemType;/二叉树定义typedef struct bnodeElemType data;struct bnode *

13、lchild;struct bnode *rchild; bTNode,*bTree;/树的双亲表示结点结构定义typedef struct int data,parent; PTNode;/双亲表示法树结构typedef struct PTNode nodeMaxSize; int count; PTree;/树的孩子兄弟表示结点结构定义typedef struct nodeint data;struct node *firstchild,*nextchild;BTNode,*BTree;/二叉链表的创建BiTree* createTree() DataType ch; Bitree *T;

14、 ch=getchar();if(ch=#) return NULL;else T=(BiTree*)malloc(sizeof(BiTree); T-data=ch; T-lchild=createBiTree(); T-rchild=createBiTree();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-f

15、irstchild);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_ptree(PTree tree) int i; printf( 序号 结点 双亲n); for(i=0;i=tree.count;i+) printf(

16、%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(请依次输入各节点（以数据域-1结束）：);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);

17、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.no

18、dei.data);for(i=1;idata)j+;b=&pj;if(!(b-firstchild)b-firstchild=a;c=a;elsec-nextchild=a;c=a;Tree=&p0;return Tree;/主菜单void Menu()printf(nnnn);printf( 主菜单 n );printf( *选项【1】* 创建一棵树n ); printf( *选项【2】* 树的前序遍历n ); printf( *选项【3】* 树的后序遍历n );printf( *选项【4】* 建立一个指定的二叉树n ); printf( *选项【0】* 退出程序n ); printf(=

19、n); printf(请输入执行的指令:);void Menu2()printf( *选项【1】* 二叉树的前序遍历n );printf( *选项【2】* 二叉树的中序遍历n ); printf( *选项【3】* 二叉树的后序遍历n );/主函数void main() 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);

20、printf(一般树转换成二叉树后的情况:n);PrintBTree(Tree,i);getchar(); break; case 2: printf(树的前序遍历:n); preorder(Tree); printf(n); break; case 3: printf(树的后序遍历:n); inoeder(Tree); printf(n); break;case 4: printf(二叉树的结构A(B(D,E(H(J,K(L,M(,N),C(F,G(,I):n); insertBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I);int a;Menu2();pri

21、ntf(请输入执行的指令:);scanf(%d,&a);switch(a)case 1:printf(二叉树的前序遍历:nn);preOrder(b);printf(n);break;case 2:printf(二叉树的中序遍历:nn);zOrder(b);printf(n);break;case 3:printf(二叉树的后序遍历:nn);hOrder(b);printf(n);break; printf(n); break; case 0: exit(1); break; 四、测试4.1 测试数据根据主界面选择选项1创建一棵树，并以双亲，数据域方式输入结点，数据域以-1结束，输入各结点的值

22、1,1 1,2 1,3 1,4 1,-1然后按回车键输出创建的树，并输出将树转换成二叉树的情况。 4.2 测试结果分析根据程序的提示，首先根据选项输入信息，输入选项后计算机会根据相应选项执行相应的步骤。1程序运行主界面如图4-1所示：图4-1 程序运行主界面2 根据提示选择相应选项，输入选项1并以双亲，数据域方式输入各结点的值所得界面如图4-2所示：图4-2 程序运行界面3以双亲，数据域的方式输入各结点的值创建一棵树并将树转换成二叉树，转换成的二叉树中结点4为结点1的右孩子，结点3为结点4的左孩子，结点2为结点3的左孩子，程序输出结果如图4-3所示：图4-3 树转换二叉树界面4选择选项1返回主

23、菜单，再选择选项4建立一棵二叉树，如图4-4所示：图4-4 建二叉树界面5选择子菜单选项1将指定二叉树按前序输出如图4-5所示：图4-5 二叉树前序遍历五、总结以前用C编程，只是注重如何编写函数能够完成所需要的功能，只是用简单的语句来编写一段程序，但现在不同了，在编写之前需要考虑各方面的因素，首先选取自己需要的数据结构，然后选取存储结构，再选取适合要求的算法。我还深刻体会到数据结构的重要性，只有真正理解一种数据类型，才能灵活的运用。刚学数据结构时候，感觉还挺有意思的，可是当我真的动手编程的时候，才发现并没有想象中的那么简单。单个知识点是弄清了，但是，将所有的知识点综合起来运用时，就碰到了各种各

24、样的问题了。编程的过程中会遇到很多问题。通过这次课程设计我知道了只有通过平时多加练习，才能有助于自己巩固知识点。通过这次课程设计我也看到了自己的不足，许多关于C+的一些具体的东西还不太懂，比如说指针。在这次课程设计中，弄清楚了很多以前不明白的东西，比如对链表的使用，知道了如何才能运用好链表。这次实训使我对树与二叉树的转换和树的遍历有了进一步的掌握，加深了对数据结构一些基本内容的理解，增强了对问题分析的能力，在上级操作方面受到了训练。刚学数据结构时候，感觉还挺有意思的，可是，真的当我动手编程的时候，才发现并没有想象中的那么简单。单个知识点是弄清了，但是，将所有的知识点综合起来运用时，就碰到了各种

25、各样的问题了。有时候，一个错误得找好久，才能发现。通过这次课程设计我知道了只有通过平时多加练习，才能有助于自己巩固知识点。参考文献1 严蔚敏.数据结构（C语言版）. 清华大学出版社 2 殷人昆.数据结构（C语言描述）. 机械工业出版社3 谭浩强.C语言程序设计. 清华大学出版社 4 谭浩强.C+程序设计基础. 清华大学出版社5 齐徳昱.算法与数据结构. 清华大学出版社 6 刘遵仁.数据结构. 人民邮电出版社#include #include #include #define MaxSize 100typedef char ElemType;typedef struct bnode/二叉树定义E

26、lemType 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=strj;while (ch!=0) /str未扫描完时循环 switch(ch) case (:top+;Sttop=p;k=1; break;/为左结点case ):top-;break;case ,:k=2

27、; 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;break; j+;ch=strj;void preOrder(bTNode *T)if(T!=NULL)printf(%c ,T-data);preOrder(T-lchild);preOrder(T-rch

28、ild);/*树的双亲表示结点结构定义*/typedef struct int data; int parent; /双亲位置域PTNode;/*双亲表示法树结构*/typedef struct PTNode nodeMaxSize; int count; /根的位置和节点个数PTree;/*树的孩子兄弟表示结点结构定义*/typedef struct node int data; struct node *firstchild; struct node *nextchild;BTNode,*BTree;/初始化树(双亲表示法)void init_ptree(PTree *tree) tree

29、-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); preorder(T-nextchild);/树后序遍历(递归)void inoeder(BTNode *T)if(T!=NULL) inoeder(T-firstchild); printf(%d ,

30、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_ptree(PTree tree) int i; printf( 序号 结点 双亲n); for(i=0;i=tree.count;i+) printf(%8d%8d%8d,i,tree.no

31、dei.data,tree.nodei.parent); printf(n); /*用双亲表示法创建树*/PTree CreatTree(PTree T)int i=1;int fa,ch;PTNode p;printf(请依次输入各结点（以数据域-1结束）：);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;BTNode *a,*b,*c,*Tree;a=(BTNode *)malloc(sizeof(BTNode);b=(BTNode *)malloc(sizeof(BTNode);c=(BTNode *)malloc(sizeof(BTNode);Tree=(BTNode *)mal