树与二叉树的转换1.docx

河南工程学院数据结构与算法课程设计成果报告树与二叉树的转换2014年12月29日2.4程序流程图设计程序的第一步是创立树，即数的结构体的建立，然后采用递归法法 进行树的先序遍历，先遍历根结点，输入树的结点数量，孩子结点及其父亲结点 的数据，建立数队列、二叉树队列。采用结构体指针数组，存放结点的地址，完 成树与二叉树队列的初始化、入队、判空、出队等操作。具体流程如下列图2. 4.1 所示：树的遍历树的遍历建立数队列、二叉树队 石|渝入树结点数据渝入树结点数据*始数列叉队II 初俗队二树相对、叉队入数列二树列队、叉队是为 一树二树列否空I 一树、 二叉 树队 列出 队图2.4. 1程序流程图3程序清单#include<iostream> using namespace std; #include<malloc. h> Sdefine DEGREE 5 /树的高度#define NULL 0ttdefine QUEUESIZE 10ttdefine MAX_N0DE_NUM 100typedef struct stl树结点的类型 (char data;数据域，采用char星 struct stl children DEGREE; 指向孩子结点的指针域 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;i<DEGREE;i+) if(root->chiIdreni=NULL) return NULL;else (returnNode=SearchCTree (root->chiIdreni, data);递归查找 if (returnNode!=NULL)return returnNode;CTreeNode *CreateSTree() int i, j, k;char data, parent;CTreeNode *root,*parentNode, *node;cout* 请输入树的结点的数量：； cin»j;if (j=0)return NULL;空树，结束函数cout* 请输入根结点的数据：；cin»data;fflush(stdin);root=(CTreeNode *)malloc(sizeof(CTreeNode);root-data=data;for(i=0;i<DEGREE;i+)root->chi1dreni=NULL;for(i=2; i<=j; i+)依次输入每个结点的信息 (cout。请输入个孩子结点的数据及其父亲结点的数据:;cin»data>parent;切记当以%c号格式输入数据时候，不要输入空格 fflush (stdin);node=(CTreeNode *)malloc(sizeof(CTreeNode);node-data=data;for (k=0;DEGREE ;k+)node->childrenk=NULL;printf (“验证parent二%cn，parent);parentNode=SearchCTree (root, parent);查找指定数据的结点 for(k=0;k<DEGREE;k+) (if (parentNode->childrenk=NULL)(parentNode->chiIdrenk=node;break;)return root;void preorderTree(CTreeNode *ctroot)遍历每个节点的操作就是输出该结点的data域 (CTreeNode *ctchild;int i;9cout«ctroot->data«/z ； 先遍历根结点for(i=0; iVDEGREE; i+) 依次先序遍历孩子结点 ctchild=ctroot->childreni;if(ctchild=NULL)break;孩子结点遍历结束，退出elsepreorderTree(ctchild) "/递归先序遍历)树队列结构体类型typedef struct nodeCTree(CTreeNode *CTreeArray MAX_NODE_NUM;结构体指针数组，存放结点的地址 /struct nodeCTree *next;int CTreeFront, CTreeRear;QueueCTree;二叉树队列结构类型typedef struct nodeBTree(BTreeNode *BTreeArray MAX_NODE_NUM;结构体指针数组，存放结点的地址 /struct nodeBTree *next;int BTreeFront, BTreeRear;QueueBTree;初始化树队列void initQueueCTree(QueueCTree *&q)(q= (QueueCTree *)malloc(sizeof(QueueCTree);q->CTreeFront=q->CTreeRear=0;)初始化二叉树队列void initQucucBTrcc(QucucBTrcc *&q)(q= (QueueBTree malloc(sizeof(QueueBTree);q->BTreeFront=q->BTreeRear=0;10树队列元素入队int addQueueCTree (QueueCTree *&q, CTreeNode *ctroot) (if (q->CTreeRear+l) %MAX_NODE_NUM=q->CTreeFront) 队满 return 0;q->CTreeRear=(q->CTreeRear+l)%MAX N0DE_NUM;q->CTreeArrayq->CTreeRear=ctroot;return 1;入队列)二叉树队列元素入队int addQueueBTree (QueueBTree *&q, BTreeNode *btroot) (if (q->BTreeRear+l) %MAX_N0DE_NUM=q->BTreeFront) 队满 return 0;q->BTreeRear=(q->BTreeRear+l)%MAX_NODE_NUM;q->BTreeArrayq->BTreeRear=btroot;return 1;入队列)树的队列判空int QueueCTreeEmpty(QueueCTree *q) (return (q->CTreeFront=q->CTreeRear);)二叉树队列判空int QucucBTreeEmpty(QueueBTree *q)( return (q->BTreeFront=q->BTreeRear);树队列元素出队CTreeNode *delQueueCTree(QueueCTree *&q) (CTreeNode *ctroot;if (q->CTreeFront=二q->CTreeRcar) 队空return NULL;返回空指针q->CTreeFront=(q->CTreeFront+l)%MAX_NODE_NUM;ctroot=q->CTreeArrayq->CTreeFront;return ctroot;返回结点11二叉树队列元素出队BTreeNode *delQueueBTree(QueueBTree *&q) (BTreeNode *btroot;if (q->BTreeFront =二q->BTreeRear) 队空return NULL;返回空指针q->BTreeFront=(q->BTreeFront+l)%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; i<DEGREE; i +) 访问结点所有的孩子节点 if (ctnode->childreni二二 NULL) 孩子结点访问完毕 break;p= (BTreeNodemalloc(sizeof (BTreeNode);分配二叉树结点12p->data=ctnode->chiIdreni->data;p->lchild=p->rchild=NULL;if (i=0)btnode->12(1邛;长子，作为父结点的做孩子else151$让1打8->1'(±11(1书；作为上一个兄弟结点的右孩子LastSibling=p;addQueueCTree (VisitedCTreeNodes, ctnode->chi 1 dreni) ;/树节点进队列 addQueueBTree (VisitedBTreeNodes, p);二叉树节点进门队列)void Preorder(BTreeNode *T)(if(T)cout«T->data«zz ；Preorder(T->lchild);Preorder(T->rchild);)int main ()(CTreeNode *Tree;BTreeNode *BTree;cout<<创立一棵树;Tree=CreateSTree();cout« 树的先序遍历结果为：；preorderTree(Tree);cout«/zn，z«endl;TreeToBTree(Tree, BTree);cout<<转换后的二叉树，先序遍历的结果为:<<endl;Preorder(BTrcc);cout<<z，n，z<<encll;return 0;)134测试4.1测试数据根据树与二叉树的的转换，创立一个树，输入树的结点的数目7,然后输入 树根结点的数据a,再依次输入各个孩子结点的数据以及父亲结点的数据ba, ca, da, eb, fc, gc,即可推出树的结构图如图4. 1. 1所示:4. 2测试结果分析根据提示，输入数据创立一棵树，输入树的结点的数量为：7输入根结点的数据为：a输入2个孩子结点的数据及其父亲结点的数据：ba 输入3个孩子结点的数据及其父亲结点的数据：ca 输入4个孩子结点的数据及其父亲结点的数据：da 输入5个孩子结点的数据及其父亲结点的数据：eb 输入6个孩子结点的数据及其父亲结点的数据：fc 输入7个孩子结点的数据及其父亲结点的数据：gc 如图4. 2. 1所示：14E:DLY1avDebugaw. exe数数数数数期 A3 iALJi2,1 iA“ .JLLFi -iL>i 点点点点点点 士 6 士 6 士 6 士 6士6 ± ci数数数数数期 A3 iALJi2,1 iA“ .JLLFi -iL>i 点点点点点点 士 6 士 6 士 6 士 6士6 ± cit=WWW 三至七七Rm uh、 W ?7- pci pci 知及及及及及及 好in 削a数数数数数数 .& :勺勺勺勺勺勺 点点点点点点 Z教士 6士 6 士 6士 6士 6士 ci 扉子子子子子子 噩孩孩孩孩孩孩 果和个个个个个个 来-4 234567 -1 AlAlAlAJAlAJA建创主DE主DE主DC主R主DC主GC主DE图4.2. 1输入结果图输入数据后，就能得到树的先序遍历结果和二叉树的先序遍历结果，如图4. 2. 2 所7Ko专换后的二叉树，先序遍历的结果为:I b e c £ g d专换后的二叉树，先序遍历的结果为:I b e c £ g diess any key to continue*E:DLYla>Debugar. exe*Ca a a b c C b c d e f 9 g:g:§:§:g:§: 数数数数数数d -£, f&H *ftX I&M -/Y*t -Z¥"T 点点点点点点g 士！i士 4士6士 6士 4 ± 6 夕，夕一夕“夕一2一2”£ ->1 Jr 1二 I，及及及及及及融nib 烬 a数数数数数数 a AHH :勺 : 京、.&MM -dlL &MM 源点点点点点点h 入-x娄士呈口士呈口士呈口导/ A2 J AZ / Az J Az J J2 一士口 第子子子子子子型 靠序 一JAJAJAlAJAJAJA先 建I 三 31- - n- - 31- - - 31- - - 31- - - 31- - - 31- .图4. 2. 2测试结果图那么树的先序遍历结果为：a b e c f g d转换后的二叉树，先序遍历的结果为：a b e c f g d155总结通过本次课程设计，我发现，有关一个课题的所有知识不仅仅是在课本上， 多查阅一些资料能够更好地完成课题，这就需要一种能力，即自学能力。本次选 的课题是树与二叉树的转换，通过书本知识和查阅相关资料，经过慢慢的调试， 最终调试成功。这次课程设计丰富了我的数据结构知识，扩展了我的知识面，使 我更加熟练的掌握各种方法。同时，我也认识到自己的缺乏，以后会更加努力的 学习数据结构。16题目树与二叉树的转换考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:参考文献1数据结构（C语言版）严蔚敏清华大学出版社20022数据结构-C语言描述王路群中国水利水电出版社2007数据结构实验教程（C语言版）王国钧 清华大学出版社20094数据结构题集严蔚敏，吴伟民编 清华大学出版社2002171课程设计目标与任务11.1 课程设计目的11.2 课程设计目标11. 3课程设计要求12分析与设计22.1题目需求分析22. 2存储结构设计22. 3算法分析42.4程序流程图73程序清单84测试144. 1测试结果144. 2测试结果分析145总结16参考文献171课程设计目标与任务1.1 课程设计目的通过本课程设计，在数据结构的选择和应用、算法的设计与实现方面得到训 练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机 操作方面受到比拟系统严格的训练，培养软件工作所需要的动手能力。1.2 课程设计目标在设计中逐步提高程序设计能力培养科学的软件工作方法，通过数据结构课 程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算 法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决 问题的有效算法；（2）通过上机实习，验证自己设计的算法的正确性，学会有效利用基本调试 方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进 一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来,将复杂的运行过程以动态方式显示出来,获得算法的直观感受。1. 3课程设计要求设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2分析与设计2.1题目需求分析本程序的主要功能是进行树与二叉树的转换，其中包含树的结构体的建立， 树队列的结构体的建立，以及对树和二叉树的遍历，包含递归算法的使用，还有 树队列和二叉树队列的初始化、判空、入队和出队等操作，队列能为二叉树遍历 提供先进先出的访问条件。2. 2存储结构设计二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后 继。它可采用顺序存储结构和链式存储结构。1 .顺序存储结构二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。如图ABCDEFABCDEF2. 2. 1 一棵完全二叉树2. 2. 2顺序存储结构2 .链式存储结构二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素 的逻辑关系。如下图：头指针I_2. 2. 3 一棵二叉树2. 2. 3 一棵二叉树22.2. 4二叉链表存储结构3 .将树转换成二叉树：（1）加线：在兄弟之间加一连线；（2）抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系;（3）旋转：以树的根结点为轴心，将整树顺时针转45。如下图:图2.2. 5将树转换成二叉树4 .将二叉树转换成树：（1）加线：假设P结点是双亲结点的左孩子，那么将P的右孩子，右孩子的右孩子沿分支找到的所有右孩子，都与P的双亲用线连起来；（2）抹线：抹掉原二叉树中双亲与右孩子之间的连线；（3）调整：将结点按层次排列，形成树结构。如下图:图2. 2. 6将二叉树转换成树2. 3算法分析1 .存储结构:typedef struct stl/树结点的类型(char data;/数据域，采用char星struct stl *childrenDEGREE;指向孩子结点的指针域CTreeNode;typedef struct st2char data;/数据域struct st2 *lchild, *rchild;左右孩子结点的指针BTreeNode;存储结构图如图2. 3. 1所示：图2.3. 1存储结构图2 .树队列结构体类型typedef struct nodeCTreeCTreeNode *CTreeArray MAX_NODE_NUM; 结构体指针数组，存放 结点的地址/struct nodeCTree *next;int CTreeFront, CTreeRear;QueueCTree;3 .二叉树队列结构类型 typedef struct nodeBTree(BTreeNode *BTreeArray MAX_NODE_NUM; 结构体指针数组，存放 结点的地址/struct nodeBTree *next;int BTreeFront, BTreeRear;QueueBTree;4 .树队列元素入队int addQueueCTree(QueueCTree *&q, CTreeNode *ctroot)(if (q->CTreeRear+l) %MAX_NODE_NUM=q->CTreeFront) /队满return 0;q->CTreeRear= (q->CTreeRear+l)%MAX_N0DE_NUM;q->CTreeArrayq->CTreeRear=ctroot;return 1;/入队列5 .二叉树队列元素入队int addQueueBTree(QueueBTree *&q, BTreeNode *btroot)if (q->BTreeRear+l) %MAX_NODE_NUM=q->BTreeFront) /队满return 0;q->BTreeRear= (q->BTreeRear+l)%MAX_NODE_NUM;q->BTreeArrayq->BTreeRear=btroot;return 1;/入队列6 .树队列元素出队CTreeNode *delQueueCTree (QueueCTree *&q)CTreeNode *ctroot;if (q->CTreeFront =二 q->CTreeRear) 队空return NULL;返回空指针q->CTreeFront= (q->CTreeFront+l)%MAX_NODE_NUM;ctroot=q->CTreeArrayq->CTreeFront;return ctroot;/返回结点7 .二叉树队列元素出队BTreeNode *delQueueBTree (QueueBTree *&q)BTreeNode *btroot;if (q-BTreeFront=q->BTreeRear) 队空return NULL;返回空指针q->BTreeFront= (q->BTreeFront+l)%MAX_NODE_NUM;btroot=q->BTreeArrayq->BTreeFront;return btroot;/返回节点