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

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

2、版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标11.1课程实现的目的11.2 课程设计任务11.3 课程设计任务的具体分析12 分析与设计22.1 题目算法分析22.2 存储结构设计32.3 算法描述32.4 程序流程图42.5 算法实现说明83 程序清单124 测试134.1 测试数据134.2 测试结果分析135 总结14参考文献151 课程设计目标与任务1.1 课程设计目标这次课程设计的目标是通过这次的课程设计，能够使我们在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严

3、格的训练，培养软件工作所需要的动手能力，熟练的掌握数据结构有关知识的应用，加深对数据结构有关知识的理解和应用，进一步提高自己的编程能力，提高自身的动手能力。1.2 课程设计任务利用本学期所学的数据结构的有关知识，实现树与二叉树相互转换，设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。该课程设计通过实现树与二叉树的转换，理解树与二叉树的相互转化关系，掌握树与二叉树的存储结构的异同

4、，加深对二叉树和树的理解。1.3 课程设计任务的具体分析 课程设计的任务是实现树与二叉树的转换，并且借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，因此应该充分理解二叉树与树之间的相互联系，明白两者的转换关系，了解树和二叉树的存储结构的异同，树和二叉树逻辑上都是树形结构，但是二者之间仍有区别，二叉树的度至多为2，但是树没有此限制，二叉树有左右子树之分，树没有此限制。了解二者是如何转化的，在转化的过程中，利用结构指针访问树的根结点和孩子结点，生成二叉树，并且利用队列，递归算法的有关知识，实现将树转化成二叉树的结果。2 分析与设计2.1 题

5、目算法分析该课程设计需要实现树与二叉树的相互转换，明白二者的转换关系，二叉树的根即为树的根，二叉树的左子树为树的左子树，从根开始一直向右，遇到的右子树均依次作为树的子树。将树转换为二叉树，关键是把n个分支变为两个分支，步骤如下：（1）保留所有结点与其左子结点的链接；（2）打断所有结点原本与右结点的链接；（3）连结所有兄弟结点（拥有同一个父结点的子结点）；（4）将兄弟结点顺时钟转45，树中右侧兄弟变为二叉树中该结点右子树。将二叉树转换为树，步骤如下：（1）二叉树的根即为树的根；（2）打断所有结点与其右子树的链接；（3）二叉树的左子树为树的左子树，从根开始一直向右，遇到的右子树均依次作为树的子树(

6、二叉树中结点的右子树中变为该结点右侧的兄弟)。2.2 存储结构设计分析树和二叉树的存储结构，二叉树的存储结构如图2.1。图2.1二叉树的存储结构图树是一种非线性的数据结构，树中的元素之间是一对多的层次关系。常用的有三种存储结构，即双亲表示法、孩子表示法、和孩子兄弟表示法。 事实上，一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的，只是两个指针域的名称及解释不同而已,通过图直观的表示了树与二叉树之间的对应关系和相互转换方法。如图2.2。图2.2 树和二叉树的转换图2.3 算法描述先遍历多叉树，将所有结点得到，然后结据相应的二叉树的规则构造二叉树就行了，将多

7、叉树的第一个儿子结点作为二叉树的左结点，将其兄弟结点作为二叉树的右结点。利用指针，遍历算法，队列的入队出队等算法，实现将树的根结点作为二叉树的根结点的操作，一棵树采用孩子兄弟表示法所建立的存储结构与它所对应的二叉树的二叉链表存储结构是完全相同的，只是两个指针域的名称及解释不同而已，且树与其对应的生成二叉树的前序遍历是相同的，可以用此来验证由树所转换成的二叉树是否正确。2.4 程序流程图该程序是先建立树，再以树为基础，将树转换成二叉树。该程序的流程是建立树，利用队列，递归，指针等，将树的根结点变为二叉树的根结点，进行树到二叉树的转换，程序的最终目的是根据输入的树的接点，孩子结点及其父亲结点，生成

8、二叉树，将树的先序遍历结果和二叉树的先序遍历的结果输出。如图2.3。主菜单树的信息图二叉树的信息图输入信息生成树输入树的结点数输入孩子结点及其父亲结点输出树的前序遍历输出二叉树的前序遍历图2.3 程序流程图2.5 算法实现说明（1）输入关于树的结点后，遍历每个结点的操作就是输出该结点的data域,首先先遍历树的根结点，再先序遍历树的孩子结点。void preorderTree(CTreeNode *ctroot)/遍历每个结点的操作就是输出该结点的data域 CTreeNode *ctchild; int i; coutdata ;/先遍历根结点 for(i=0;ichildreni; if(

9、ctchild=NULL) break;/孩子结点遍历结束，退出 else preorderTree(ctchild);/递归先序遍历（2）定义BTreeNode *BTreeArrayMAX_NODE_NUM结构体指针数组，用于存放结点的地址，开始初始化树队列，二叉树队列，并且分别将树和二叉树的元素分别进行入队操作，在元素进入队列时要进行判断队列，看是否为满。然后再把树队列元素出队，要进行队列是否为空的判断，利用指针返回结点的值，然后进行二叉树队列元素出队，返回空指针后返回结点。该段程序的关键是元素的出队入队操作。typedef struct nodeBTreeBTreeNode *BTre

10、eArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址/struct nodeBTree *next;int BTreeFront,BTreeRear;QueueBTree;/初始化树队列void initQueueCTree(QueueCTree *&q) q=(QueueCTree *)malloc(sizeof(QueueCTree); q-CTreeFront=q-CTreeRear=0;/初始化二叉树队列void initQueueBTree(QueueBTree *&q) q=(QueueBTree *)malloc(sizeof(QueueBTree); q-BT

11、reeFront=q-BTreeRear=0;int addQueueCTree(QueueCTree *&q,CTreeNode *ctroot) if(q-CTreeRear+1)%MAX_NODE_NUM=q-CTreeFront)/队满 return 0; q-CTreeRear=(q-CTreeRear+1)%MAX_NODE_NUM; q-CTreeArrayq-CTreeRear=ctroot; return 1;/入队列/二叉树队列元素入队int addQueueBTree(QueueBTree *&q,BTreeNode *btroot) if(q-BTreeRear+1)%

12、MAX_NODE_NUM=q-BTreeFront)/队满 return 0; q-BTreeRear=(q-BTreeRear+1)%MAX_NODE_NUM; q-BTreeArrayq-BTreeRear=btroot; return 1;/入队列（3）下面是树转换成二叉树的关键操作，树转换成二叉树时利用ctroot指向树的根结点，利用btroot指向二叉树的根，增添一个辅助队列，并且增加开辟内存空间的语句，并且树的根结点会作为二叉树的根结点，树的根结点入队后二叉树的根结点入队，然后树结点出队，二叉树的结点出队，访问所有的孩子结点后，分配二叉树的结点，按照树转换成二叉树的规则，二叉树的左

13、子树为树的左子树，从根开始一直向右，遇到的右子树均依次作为树的子树(二叉树中结点的右子树中变为该结点右侧的兄弟），将树转化成二叉树。void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/树转化为二叉树ctroot指向树的根结点，btroot,指向二叉树的根 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes;/辅助队列 initQueueCTree(VisitedCTreeNodes); initQueueBTree(VisitedBTreeNodes);/初始化队列

14、CTreeNode *ctnode; BTreeNode *btnode,*p,*LastSibling; int i; btroot=(BTreeNode *)malloc(sizeof(BTreeNode);/添加开辟内存空间语句 btroot-data=ctroot-data;/树的根结点作为二叉树的根结点 btroot-lchild=btroot-rchild=NULL; addQueueCTree(VisitedCTreeNodes,ctroot);/树的根结点入队 addQueueBTree(VisitedBTreeNodes,btroot);/二叉树的根结点入队 while(!Q

15、ueueCTreeEmpty(VisitedCTreeNodes) ctnode=delQueueCTree(VisitedCTreeNodes);/树结点出队 btnode=delQueueBTree(VisitedBTreeNodes);/二叉树结点出队 for(i=0;ichildreni=NULL)/孩子结点访问完毕 break; p=(BTreeNode *)malloc(sizeof(BTreeNode);/分配二叉树结点 p-data=ctnode-childreni-data; p-lchild=p-rchild=NULL; if(i=0) btnode-lchild=p;/长

16、子，作为父结点的做孩子 else LastSibling-rchild=p;/作为上一个兄弟结点的右孩子 LastSibling=p;addQueueCTree(VisitedCTreeNodes,ctnode-childreni);/树结点进队列 addQueueBTree(VisitedBTreeNodes,p);/二叉树结点进门队列void Preorder(BTreeNode *T) if(T) coutdatalchild); Preorder(T-rchild); 3 程序清单#includeusing namespace std;#include#define DEGREE 5

17、/树的高度#define NULL 0#define QUEUESIZE 10#define MAX_NODE_NUM 100typedef struct st1/树结点的类型 char data;/数据域，采用char星 struct st1 *childrenDEGREE;/指向孩子结点的指针域CTreeNode;typedef struct st2 char data;/数据域 struct st2 *lchild,*rchild;/左右孩子结点的指针BTreeNode;CTreeNode *SearchCTree(CTreeNode *root ,char data) int i; C

18、TreeNode *returnNode; if(root-data=data) return root;CTreeNode *CreateSTree() int i,j,k; char data, parent; CTreeNode *root,*parentNode,*node; coutj; if(j=0) return NULL;/空树，结束函数 coutdata; fflush(stdin); root=(CTreeNode *)malloc(sizeof(CTreeNode); root-data=data; for(i=0;ichildreni=NULL; for(i=2;i=j

19、;i+)/依次输入每个结点的信息 cout请输入第idataparent; fflush(stdin); node=(CTreeNode *)malloc(sizeof(CTreeNode); node-data=data; for(k=0;kchildrenk=NULL; parentNode=SearchCTree(root,parent);/查找指定数据的结点 for(k=0;kchildrenk=NULL) parentNode-childrenk=node; break; return root;void preorderTree(CTreeNode *ctroot)/遍历每个结点的

20、操作就是输出该结点的data域 CTreeNode *ctchild; int i; coutdata ;/先遍历根结点 for(i=0;ichildreni; if(ctchild=NULL) break;/孩子结点遍历结束，退出 else preorderTree(ctchild);/递归先序遍历 /树队列结构体类型typedef struct nodeCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear;QueueCTree;/二

21、叉树队列结构类型typedef struct nodeBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址 /struct nodeBTree *next; int BTreeFront,BTreeRear;QueueBTree;/初始化树队列void initQueueCTree(QueueCTree *&q) q=(QueueCTree *)malloc(sizeof(QueueCTree); q-CTreeFront=q-CTreeRear=0;/初始化二叉树队列void initQueueBTree(QueueBTree *&

22、q) q=(QueueBTree *)malloc(sizeof(QueueBTree); q-BTreeFront=q-BTreeRear=0;/树队列元素入队int addQueueCTree(QueueCTree *&q,CTreeNode *ctroot) if(q-CTreeRear+1)%MAX_NODE_NUM=q-CTreeFront)/队满 return 0; q-CTreeRear=(q-CTreeRear+1)%MAX_NODE_NUM; q-CTreeArrayq-CTreeRear=ctroot; return 1;/入队列/二叉树队列元素入队int addQueue

23、BTree(QueueBTree *&q,BTreeNode *btroot) if(q-BTreeRear+1)%MAX_NODE_NUM=q-BTreeFront)/队满 return 0; q-BTreeRear=(q-BTreeRear+1)%MAX_NODE_NUM; q-BTreeArrayq-BTreeRear=btroot; return 1;/入队列int QueueCTreeEmpty(QueueCTree *q) return(q-CTreeFront=q-CTreeRear);int QueueBTreeEmpty(QueueBTree *q) return(q-BTr

24、eeFront=q-BTreeRear);/树队列元素出队CTreeNode *delQueueCTree(QueueCTree *&q) CTreeNode *ctroot; if(q-CTreeFront=q-CTreeRear)/队空 return NULL;/返回空指针 q-CTreeFront=(q-CTreeFront+1)%MAX_NODE_NUM; ctroot=q-CTreeArrayq-CTreeFront; return ctroot;/返回结点/二叉树队列元素出队BTreeNode *delQueueBTree(QueueBTree *&q) BTreeNode *bt

25、root; if(q-BTreeFront=q-BTreeRear)/队空 return NULL;/返回空指针 q-BTreeFront=(q-BTreeFront+1)%MAX_NODE_NUM; btroot=q-BTreeArrayq-BTreeFront; return btroot;/返回结点void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)/树转化为二叉树ctroot指向树的根结点，btroot,指向二叉树的根 QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeN

26、odes;/辅助队列 initQueueCTree(VisitedCTreeNodes); initQueueBTree(VisitedBTreeNodes);/初始化队列 CTreeNode *ctnode; BTreeNode *btnode,*p,*LastSibling; int i; btroot=(BTreeNode *)malloc(sizeof(BTreeNode);/添加开辟内存空间语句 btroot-data=ctroot-data;/树的根结点作为二叉树的根结点 btroot-lchild=btroot-rchild=NULL; addQueueCTree(Visited

27、CTreeNodes,ctroot);/树的根结点入队 addQueueBTree(VisitedBTreeNodes,btroot);/二叉树的根结点入队 while(!QueueCTreeEmpty(VisitedCTreeNodes) ctnode=delQueueCTree(VisitedCTreeNodes);/树结点出队 btnode=delQueueBTree(VisitedBTreeNodes);/二叉树结点出队 for(i=0;ichildreni=NULL)/孩子结点访问完毕 break; p=(BTreeNode *)malloc(sizeof(BTreeNode);/分

28、配二叉树结点 p-data=ctnode-childreni-data; p-lchild=p-rchild=NULL; if(i=0) btnode-lchild=p;/长子，作为父结点的做孩子 else LastSibling-rchild=p;/作为上一个兄弟结点的右孩子 LastSibling=p; addQueueCTree(VisitedCTreeNodes,ctnode-childreni);/树结点进队列 addQueueBTree(VisitedBTreeNodes,p);/二叉树结点进门队列void Preorder(BTreeNode *T) if(T) coutdata

29、lchild); Preorder(T-rchild);int main() CTreeNode *Tree; BTreeNode *BTree; cout创建一棵树; Tree=CreateSTree(); cout树的先序遍历结果为:; preorderTree(Tree); coutnendl; TreeToBTree(Tree,BTree); cout转换后的二叉树，先序遍历的结果为:endl; Preorder(BTree); coutnendl; return 0;4 测试4.1 测试数据创建一个树，输入树的结点数量，再分别输入孩子结点和其父亲结点的数据，程序运行，输出树的先序遍历

30、结果和转换后二叉树的先序遍历的结果，输入数据如图4.1。 图4.1 程序运行图4.2 测试结果分析输入树的结点数，孩子结点及其父亲结点的数据后，程序输出树的先序遍历结果和转换后的二叉树的先序遍历的结果，如图4.2。图4.2 程序运行结果图5 总结通过这次的课程设计，让我更加深刻地了解课程知识，对以往的疏忽加以补充，对以后的学习和工作打下良好的基础。 在这短暂的一周内，我学到了很多，是让我对课本知识的巩固，更加强了自身的实践能力。课程设计是培训学生利用专业知识分析解决实际应用的重要环节，促进了同学之间的相互探讨与学习，使我懂得了自身努力与团队合作的重要。使我对抽象的理论有了具体的认识。 通过自己

31、的努力，将所学的知识运用到实践中，也是对自身所学的认可。参考文献1谭浩强.C语言程序设计. 清华大学出版社2谭浩强.C+程序设计基础.清华大学出版社3胡学纲.数据结构（C语言版）.高等教育出版社4刘遵仁.数据结构.人民邮电出版社5齐德昱.算法与数据结构.清华大学出版社6严蔚敏.数据结构（C语言版）.清华大学出版社#includeusing namespace std;#include#define DEGREE 5 /树的高度#define NULL 0#define QUEUESIZE 10#define MAX_NODE_NUM 100typedef struct st1/树结点的类型 c

32、har data;/数据域，采用char星 struct st1 *childrenDEGREE;/指向孩子结点的指针域CTreeNode;typedef struct st2 char data;/数据域 struct st2 *lchild,*rchild;/左右孩子结点的指针BTreeNode;CTreeNode *SearchCTree(CTreeNode *root ,char data) int i; CTreeNode *returnNode; if(root-data=data) return root;CTreeNode *CreateSTree() int i,j,k; c

33、har data, parent; CTreeNode *root,*parentNode,*node; coutj; if(j=0) return NULL;/空树，结束函数 coutdata; fflush(stdin); root=(CTreeNode *)malloc(sizeof(CTreeNode); root-data=data; for(i=0;ichildreni=NULL; for(i=2;i=j;i+)/依次输入每个结点的信息 cout请输入第idataparent; fflush(stdin); node=(CTreeNode *)malloc(sizeof(CTree

34、Node); node-data=data; for(k=0;kchildrenk=NULL; parentNode=SearchCTree(root,parent);/查找指定数据的结点 for(k=0;kchildrenk=NULL) parentNode-childrenk=node; break; return root;void preorderTree(CTreeNode *ctroot)/遍历每个结点的操作就是输出该结点的data域 CTreeNode *ctchild; int i; coutdata ;/先遍历根结点 for(i=0;ichildreni; if(ctchil

35、d=NULL) break;/孩子结点遍历结束，退出 else preorderTree(ctchild);/递归先序遍历 /树队列结构体类型typedef struct nodeCTree CTreeNode *CTreeArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址 /struct nodeCTree *next; int CTreeFront,CTreeRear;QueueCTree;/二叉树队列结构类型typedef struct nodeBTree BTreeNode *BTreeArrayMAX_NODE_NUM;/结构体指针数组，存放结点的地址 /struc

36、t nodeBTree *next; int BTreeFront,BTreeRear;QueueBTree;/初始化树队列void initQueueCTree(QueueCTree *&q) q=(QueueCTree *)malloc(sizeof(QueueCTree); q-CTreeFront=q-CTreeRear=0;/初始化二叉树队列void initQueueBTree(QueueBTree *&q) q=(QueueBTree *)malloc(sizeof(QueueBTree); q-BTreeFront=q-BTreeRear=0;/树队列元素入队int addQu

37、eueCTree(QueueCTree *&q,CTreeNode *ctroot) if(q-CTreeRear+1)%MAX_NODE_NUM=q-CTreeFront)/队满 return 0; q-CTreeRear=(q-CTreeRear+1)%MAX_NODE_NUM; q-CTreeArrayq-CTreeRear=ctroot; return 1;/入队列/二叉树队列元素入队int addQueueBTree(QueueBTree *&q,BTreeNode *btroot) if(q-BTreeRear+1)%MAX_NODE_NUM=q-BTreeFront)/队满 re

38、turn 0; q-BTreeRear=(q-BTreeRear+1)%MAX_NODE_NUM; q-BTreeArrayq-BTreeRear=btroot; return 1;/入队列int QueueCTreeEmpty(QueueCTree *q) return(q-CTreeFront=q-CTreeRear);int QueueBTreeEmpty(QueueBTree *q) return(q-BTreeFront=q-BTreeRear);/树队列元素出队CTreeNode *delQueueCTree(QueueCTree *&q) CTreeNode *ctroot; i

39、f(q-CTreeFront=q-CTreeRear)/队空 return NULL;/返回空指针 q-CTreeFront=(q-CTreeFront+1)%MAX_NODE_NUM; ctroot=q-CTreeArrayq-CTreeFront; return ctroot;/返回结点/二叉树队列元素出队BTreeNode *delQueueBTree(QueueBTree *&q) BTreeNode *btroot; if(q-BTreeFront=q-BTreeRear)/队空 return NULL;/返回空指针 q-BTreeFront=(q-BTreeFront+1)%MAX_NODE_NUM; btroot=q-BTreeArrayq-BTreeFront; retu