树与二叉树的转换实现数据结构与算法》课程设计成果报告.doc

河南工程学院数据结构与算法课程设计成果报告树与二叉树的转换实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程 1342 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目树与二叉树的转换实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1课程设计要求11.2 课程设计目的11.3 课程设计任务12 分析与设计22.1 题目分析22.2 存储结构设计22.3 算法设计32.4 程序流程图73 主程序94 测试与运行134.1 测试数据134.2 测试结果分析135 总结15参考文献161 课程设计目标与任务1.1课程设计要求根据数据结构所学的理念、理论和方法，按照数据结构设计的基本步骤，设计出一个适当规模的程序来实现设计课程内容中的全部功能；设计主控模块程序对给出的程序源代码要给出各部分的详细注释自己根据能力及需要添加相应功能模块，增强模拟系统功能实现树与二叉树的相互转换。1.2 课程设计目的通过本课程设计，在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。1.3 课程设计任务根据所学知识，设计树与二叉树转换的相关程序，以便在程序设计中调用，通过设计程序，掌握树与二叉树的存储结构的异同，以及树与二叉树的相互转化关系，要求实现以下要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所写程序来实现相关问题的求解。2 分析与设计2.1 题目分析本程序的主要功能是进行树与二叉树的转换，其中包含树的结构体的建立，树队列的结构体的建立，以及对树和二叉树的遍历，其中包含递归算法的使用，还有树队列和二叉树队列的初始化、判空、入队和出队等操作，队列能为二叉树遍历提供先进先出的访问条件。2.2 存储结构设计1. 树是一种非线性的数据结构，树中的元素之间是一对多的层次关系。常用的有三种存储结构，即双亲表示法、孩子表示法、和孩子兄弟表示法。 2. 将树转换成二叉树的步骤是： （1）加线。就是在所有兄弟结点之间加一条线。 （2）抹线。对树中的每个结点，只保留它与第一个孩子结点之间的连线，删除它与其他孩子结点之间的连线。 （3）旋转。以树的根结点为轴心，将整棵树顺时针旋转一定角度，使二叉树的结构层次分明。 （4）树转换成二叉树后其右子树一定为空。将树转换成二叉树如下图2-1所示。图2-1树转换成二叉树图 3.将二叉树转换为树（1）加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到所有的右孩子都与p的双亲用线连起来。（2）抹线：抹掉原二叉树中双亲与间的连线。（3）调整：二叉树的根即为树的根，将结点按层次排列，形成树结构。 将树转换成二叉树如图2-2所示：图2-2二叉树转换成树图2.3 算法设计（1）一般树的存储结构有以下几种：双亲结点，孩子结点，孩子兄弟结点。本实验运用到的是双亲结点和孩子兄弟结点。具体存储结构如下typedef struct st1/树结点的类型 char data;/数据域，采用char星 struct st1 *childrenDEGREE;/指向孩子结点的指针域CTreeNode;typedef struct st2 char data;/数据域 struct st2 *lchild,*rchild;/左右孩子结点的指针BTreeNode;（2）点下面的一段程序是树的先序遍历，遍历树的每个结点，即输出该结点的指针域，先遍历下根结点，然后依次遍历孩子结，采用递归算法。void preorderTree(CTreeNode *ctroot) CTreeNode *ctchild; int i; coutdata ; for(i=0;ichildreni; if(ctchild=NULL) break; else preorderTree(ctchild); 此程序即为二叉树的先序遍历，采用递归调用。void Preorder(BTreeNode *T) if(T) coutdatalchild); Preorder(T-rchild); （3）CTreeNode *CreateSTree()函数，输入树的结点的数量以及各个结点的数据， 用parentNode=SearchCTree(root,parent)查找指定数据的结点。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;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;（4）下面的程序是建立树队列以及二叉树队列的结构体类型，CTreeNode *CTreeArrayMAX_NODE_NUM为结构体指针数组，存放结点的地址，BTreeNode *BTreeArrayMAX_NODE_NUM为结构体指针数组，存放结点的地址。typedef struct nodeCTreeCTreeNode *CTreeArrayMAX_NODE_NUM; int CTreeFront,CTreeRear;QueueCTree;typedef struct nodeBTree BTreeNode *BTreeArrayMAX_NODE_NUM; int BTreeFront,BTreeRear;QueueBTree;（5）下面是将树转换为二叉树的主要程序段，ctroot指向树的根结点，btroot,指向二叉树的根,先初始化队列，然后开辟新的内存空间，以树的根结点作为二叉树的根结点，树的根结点入队，二叉树的根结点入队，树结点出队，二叉树结点出队，然后分配二叉树结点，二叉树的左子树为树的左子树，从根开始一直向右，遇到的右子树均依次作为树的子树(二叉树中结点的右子树中变为该结点右侧的兄弟）。void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot) QueueCTree *VisitedCTreeNodes; QueueBTree *VisitedBTreeNodes;/辅助队列 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(VisitedCTreeNodes,ctroot);/树的根结点入队 addQueueBTree(VisitedBTreeNodes,btroot); while(!QueueCTreeEmpty(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; else LastSibling-rchild=p; LastSibling=p;addQueueCTree(VisitedCTreeNodes,ctnode-childreni); addQueueBTree(VisitedBTreeNodes,p); 2.4 程序流程图程序的第一步是建立树，即数的结构体的建立，然后进行树的先序遍历，用递归方法，先遍历根结点，依次先序遍历孩子结点，输入树的结点数量，孩子结点及其父亲结点的数据，建立树队列，二叉树队列，采用结构体指针数组，存放结点的地址，完成树队列以及二叉树队列的初始化、入队、判空、出队等操作，利用VoidTreeToBTree(CTreeNode*ctroot,BTreeNode *&btroot)函数树转化为二叉树，然后进行二叉树的先序遍历，采用递归算法，输出二叉树的先序遍历结果，具体流程如下图2-3。图2-3 程序流程图3 原程序#includeusing namespace std;#include#define DEGREE 5 /树的高度#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; CTreeNode *returnNode; if(root-data=data) return root; else for(i=0;ichildreni=NULL) return NULL; else returnNode=SearchCTree(root-childreni,data);/递归查找 if(returnNode!=NULL) return returnNode; 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;i+)/依次输入每个结点的信息 cout请输入idataparent;/切记当以%c号格式输入数据时候，不要输入空格 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)/遍历每个结点的操作就是输出该结点的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;/二叉树队列结构类型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 *&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 addQueueBTree(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-BTreeFront=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 *btroot; 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 *VisitedBTreeNodes;/辅助队列 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(VisitedCTreeNodes,ctroot);/树的根结点入队 addQueueBTree(VisitedBTreeNodes,btroot);/二叉树的根结点入队 while(!QueueCTreeEmpty(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;/长子，作为父结点的做孩子 else LastSibling-rchild=p;/作为上一个兄弟结点的右孩子 LastSibling=p;addQueueCTree(VisitedCTreeNodes,ctnode-childreni);/树结点进队列addQueueBTree(VisitedBTreeNodes,p);/二叉树结点进门队列 void Preorder(BTreeNode *T) if(T) coutdatalchild); 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 测试数据输入树的结点数量，根结点的数据，还有孩子结点和其父亲结点的数据，根结点为A，A的孩子结点为B、C、E，C的孩子结点为D，按照层序遍历的结果为A、B、C、E、D。树的结构图如下图4-1所示。图4-1 树的结构图4.2 测试结果分析（1）输入数据后，输出树的先序遍历结果和二叉树的先序遍历结果，看程序运行显示的树的先序遍历和二叉树的先序遍历结果是否相同来判断生成的二叉树是否正确，如图4-2所示。图4-2 程序运行图（2）本程序中，转换时结点的第一个孩子变为它的左孩子，兄弟孩子变为它的右孩子。即根结点A的第一个孩子结点B变为A的左孩子，结点B的兄弟结点C变为B的右孩子，结点E变为C的右孩子，D变为结点C的左孩子。以树的根结点A为轴心，将整棵树顺时针旋转一定角度转换之后就得到层次分明的二叉树。转换之后的二叉树只有左子树，右子树为空。树与二叉树的存储结构以及转换过程如下图4-3所示。图4-3 树与二叉树转换存储结构图5 总结通过本次数据结构课程设计，让我加深了对数据结构的特点和算法的了解。尽管编写程序时有一定的困难，但是也可以锻炼自己读写程序的能力，在这个程序里主要用到了树、二叉树以及队列的知识，在递归遍历中，要理解递归的先后顺序和遍历时根和左右子树的遍历。用队列时，要注意它先进先出的顺序。通过编写这个程序，让我认识到了自己程序设计方面的不足，也意识到了以后要多做题，勤于思考，动手实践，争取有更大的进步。参考文献1严蔚敏.数据结构（C语言描述）. 清华大学出版社2殷人昆.数据结构（C语言描述）.机械工业出版社3谭浩强.C语言程序设计.清华大学出版社4谭浩强.C+程序设计基础.清华大学出版社5齐德昱.算法与数据结构. 清华大学出版社6刘遵仁.数据结构.人民邮电出版社#includeusing namespace std;#include#define DEGREE 5 /树的高度#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; CTreeNode *returnNode; if(root-data=data) return root; else for(i=0;ichildreni=NULL) return NULL; else returnNode=SearchCTree(root-childreni,data);/递归查找 if(returnNode!=NULL) return returnNode; 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;i+)/依次输入每个结点的信息 cout请输入idataparent;/切记当以%c号格式输入数据时候，不要输入空格 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)/遍历每个结点的操作就是输出该结点的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;/二叉树队列结构类型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 *&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 addQueueBTree(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-BTreeFront=q-BTreeRear);CTreeNode *delQueueCTree(QueueCTree *&q) /树队列元素出队 CTreeNode *ctroot; if(q-CTreeFront=q-CTreeRear)/队空