树与二叉树转换实现10.docx

河南工程学院数据结构与算法课程设计成果报告树与二叉树转换实现2. 4程序流程流程图可以给我们清楚的展示一些复杂的程序流程，帮助我们分析更加清楚 明了。掌握流程图的画法和能够清晰地用流程图表示我们编程思路尤为重要。树 与二叉树流程图2-5如下图：图2-5流程图72. 5测试程序此次程序是树与二叉树转换的相关函数库，及在程序设计中调用，最主要的 是实现树与二叉树的转换。编译运行程序，根据提示输入结点个数、根结点的数据，以根结点的数据为 依据依次输入第二个结点树和其根节点数据、第三个结点树和其根节点数据、第 四个、第五个、第六个直到与初始节点个数相同为止。给出假设干实例演示， 通过调用自己所写的数据使程序来实现相关问题的求解。将程序运行结果和预想的结果相比拟,分析程序中缺乏之处,查找问题所在, 致力改良程序，使程序更加合理。3程序清单树与二叉树的转换的主要程序如下所示：/*树和二叉树的结构体*/typedef struct stl树节点的类型char data;数据域,采用char型struct stl *childrenDEGREE;指向孩子节点的指针域 CTreeNode;typedef struct st2char data;数据域struct st2 *lchild,*rchild;左右孩子节点的指针 BTreeNode;/*入队列*/树队列元素入队int addQ.ueueCTree(QueueCTree *&q,CTreeNode *ctroot)/(if(q->CTreeRear+l)%MAX_NODE_NUM=q->CTreeFront)/|3Aw return 0;q->CTreeRear=(q->CTreeRear+l)%MAX_NODE_NUM;q->CTreeArrayq->CTreeRear=ctroot;return 1;入队列)二叉树队列元素入队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;入队列)/*出队列*/树队列元素出队CTreeNode *delQueueCTree(QueueCTree *&q)CTreeNode *ctroot;if(q->CTreeFront =q->CTreeRear) 队空return NULL;返回空指针q->CTreeFront=(q->CTreeFront+l)%MAX_NODE_NUM;ctroot=q->CT reeArrayq->CT reeFront;return ctroot;返回节点 二叉树队列元素出队BTreeNode *delQueueBTree(Q.ueueBTree *&q)BTreeNode *btroot;if(q->BTreeFront =二q->BTreeRear) 队空return NULL;返回空指针9q->BTreeFront=(q->BTreeFront+l)%MAX_NODE_NUM;btroot=q->BTreeArrayq->BTreeFront;return btroot;返回节点)/*树转化为二叉树*/void TreeToBTree(CTreeNode *ctroot,BTreeNode *&btroot)树转化为二叉树 ctroot指向树的根节点，btroot,指向二叉树的跟QueueCTree *VisitedCTreeNodes;QueueBTree * Visited BTreeNodes; 辅助队歹 UinitQueueCTree(VisitedCTreeNodes);initQueueBTree(VisitedBTreeNodes);/初始化队歹UCTreeNode *ctnode;BTreeNode *btnode/*p,*LastSibling;int i;btroot=(BTreeNode *)malloc(sizeof(BTreeNode);添力口开辟内存空 间语句btroot->data=ctroot->data; 树的根节点作为二叉树的根节点 btroot->lchild=btroot->rchild=NULL;addQueueCTree(VisitedCTreeNodesctroot);/树的金艮节 点入队addQueueBTree(VisitedBTreeNodes,btroot);/二叉树的品艮节 点入队 while(!QueueCTreeEmpty(VisitedCTreeNodes)ctnode=delQueueCTree(VisitedCTreeNodes);/树节点出队 btnode=delQueueBTree(VisitedBTreeNodes);/二叉树节点 出队for(i=0;i<DEGREE;i+) 访问节点所有的孩子节点 (if(ctnode->childreni=NULL) 孩子节点访问完 毕break;p=(BTreeNode *)malloc(sizeof(BTreeNode);分 配二叉树节点p->data=ctnode->childreni->data;p->lchild=p->rchild=NULL;if(i=0)btnode->lchild二p;长子，作为父节点的做孩子 elseLastSibling->rchild=p; 作为上一个兄弟节点的右孩子LastSibling=p;addQueueCTree(VisitedCTreeNodeS,Ctnode>childreni);/树节点进队歹(JaddQueueBTree(VisitedBTreeNodes'p); 二叉树节点进门 队列)10/*主函数调用*/ int main()CTreeNode *Tree;BTreeNode *BTree;printf("创立一棵树n")；T ree=CreateST ree();printf(',树的先序遍历结果为preorderT ree(T ree);printf("n");T reeToBT ree(T ree,BT ree);printf。1转换后的二叉树，先序遍历的结果为Preorder(BTree);pnntf("n");return 0;ii4测试按照程序内部的结构对程序进行测试，通过测试来检查是否按照设计要求的 规定形式运行。对程序或者函数输入一定参数值，为了确保程序的正确性，可以 多输入几组数据，生成测试数据，取得程序运行时的真实情况、动态情况，进而 进行分析。4.1测试结果分析开始测试程序，编译运行，初始界面如下列图4-1所示：'E:shixuntreeDebugzhang.exe*图4-1界面图按提示要求输入结点数，如输入结点数为50,点击Enter键，那么提示下一步输入根结点的数据。如图4-2所示：12图4-2结点图输入根结点数据如“23”，生成如下列图4-3所示:图4-3根结点图13依次按提示输入第二个结点数如“12”及其父节点数“23”，Enter键那么输出图4-4所小界面： E:shixuntreeDebugzhang.exe*图4-4第二个结点图根据提示那么依次输入第三个，第四个，第五个直到到达其节点数目。145总结通过本次程序设计，让我更深入地了解到了树的各种函数的运用，如何运用 各种存储结构创立树，以及在试验中涉及到递归的运用，省去了复杂的算法设 计。在程序运行中不可防止出现各种大大小小的问题，在调试运行时，通过查阅 课本和同学间的讨论，不仅使问题得到了解决，更重要的是使我更透彻地领悟各 种算法的灵活运用。同时在编程的过程中让我对上学期学习的有关c方面的知识 加以复习和捡漏，对所学知识有一个更系统的复习。15参考文献严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社殷人昆.数据结构（第二版）.清华大学出版社赵坚，姜梅.数据结构（C语言版）.中国水利水电出版社赵坚，姜梅.数据结构学习指导与习题解答（C语言版）.中国水利水电出 版社16题目树与二叉树转换实现考核工程考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、 基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答下列问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总评成绩指导教师评语:日期:目录1课程设计目标与任务11.1课程设计目标11. 2课程设计任务1L3课程设计目的12分析与设计22.1题目分析22. 2存储结构32. 3算法描述52. 4程序流程72.5测试程序83程序清单94.1测试数据4测试12错误!未定义书签。错误!未定义书签。15164. 2测试结果分析5总结参考文献1课程设计目标与任务1.1课程设计目标数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践是软 件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本 技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法 学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算 法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决 问题的有效算法；（2）通过上机实习，验证自己设计的算法的正确性，学会有效利用基本调试 方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进 一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来,将复杂的运行过程以动态方式显示出来，获得算法的直观感受。 1. 2课程设计任务设计树与二叉树转换的相关函数库，以便在程序设计中调用，要求：（1）实现树与二叉树的转换；（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图 形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出假设干例程，演示通过调用自己所缩写程序来实现相关问题的求解。L3课程设计目的通过本次课程设计，使我们在数据结构的选择与应用、算法的设计与实现方 面得到很好训练，加深对数据结构基本内容的理解和灵活应用。在程序设计方法 及上机操作方面受到比拟系统的、严格的训练，培养我们软件工作时所需要的动 手能力。同时，数型结构是一类重要的非线性数据结构，其中树和二叉树最为常 用，所以掌握好树与二叉树的各种函数及其相互间的转换非常重要。2分析与设计数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种 或多种特定关系的数据元素的集合。树是数据结构中比拟重要的结构之一，是一 种重要的非线性数据结构，直观地看，它是数据元素(在树中称为结点)按分支 关系组织起来的结构，很像自然界中的树那样。树结构不仅在客观世界中广泛存 在，在计算机领域中也得到广泛应用。一切具有层次关系的问题都可用树来描述。2.1题目分析树是一种重要的非线性数据结构，掌握二叉树的两种基本的存储结构，及各 种操作的算法实现(建立、遍历)以及应用是非常重要的。树结构的特点是：它的每一个结点都可以有不止一个直接后继，除根结点外 的所有结点都有且只有一个直接前趋。二叉树的特点是：每个结点至多有两棵子树(即二叉树中不存在度大于2 的结点)，并且，二叉树的子树有左右之分，其次序不能颠倒。(1)树转换成二叉树如果F=T1,T2,.,Tm是森林，那么可按如下规那么转换成一棵二叉树B= (root, LB, RB) o假设F为空，即m=0,那么b树为空树；假设F非空，即m!=0,那么B的根root即为森林中第一棵树的根root (T1)； B的左子树LB是从T1中根结点的子树森林Fl= T11,T22,转换而成的二 叉树；其右子树RB是从森林I =T1,T2,.,Tm转换而成的二叉树。(2)二叉树转换成森林如果B= (root, LB, RB) F=T1,T2,.,Tm是一棵二叉树，那么可按如下规那么转 换成森林 F=Tl,T2/-.Jmo假设B为空，那么F为空。假设B非空，那么F中第一棵树T1的根ROOT(Tl)即为二叉树的B的根root； T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除tl之外 的其余树组成的森林F' =T1,T2,.,Tm是由B的右子树RB转换而成的森林。运用递归定义容易写出相关转换的递归算法。2. 2存储结构1 .树的存储结构有很多种形式。下面介绍常用的三种常用的存储结构：（1）双亲数组表示法这种存储结构是利用每个结点（根结点除外）只有唯一双亲的特点，用一维 数组来存储一棵一般的树。，如图1-1 > 1-2即为一棵树及其双亲表示。在这 种结构中，寻找一个结点双亲的时候，只要访问它的parent域，即可得到它的 双亲的存储位置。但是，要寻找一个结点的孩子时，那么需遍历整个数组。A-1B0C0D0E1F1G3H515J5012345-6789图2-1双亲表示图2-2树（2）结点定长的孩子链表表示法如下列图2-3所示，一个三叉树，可以用三叉链表储存。其结构特点是：一个 数据域和三个指针域，指针域用于指向节点的各个孩子节点。图2-3孩子链图(3)孩子一兄弟二叉链表表示法孩子一兄弟链表作为存储结构，其特点是：一个数据域和两个指针域。其中一个指针指向它的第一个孩子节点，另一个指向它的兄弟结点。如图2-4所示:图2-4孩子-兄弟图2 .二叉树的存储结构也有好多种，下面介绍几种常用的二叉树的存储结构(1)二叉树得顺序存储结构是将二叉树的所有结点，按照一定的次序，存 储到一片连续的存储单元中。因此，必须将结点排成一个适当的线性序列，使 得结点在这个序列中的相应位置能反映出结点之间的逻辑关系。这种结构特别 适用于近似满二叉树。在一棵具有n个结点的近似满二叉树中，我们从树根起, 自上层到下层，逐层从左到右给所有结点编号，就能得到一个足以反映整个二叉 树结构的线性序列。(2)二叉树的二叉链表存储适用于普通二叉树，每个结点除了数据外，还 有分别指向左右孩子结点的指针，存储n个结点有n+1个空指针域，存储密度小 于顺序存储，但是适用范围广，缺陷是正常遍历只能从双亲向孩子，退回来一般 需要借助栈。typedef int TEIemType;typedef struct BiTNode TEIemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;被封装好的每个节点，都有一个数据域data和两个指针域*lchild,*rchild分 别指向左右子树。（3）二叉树的三叉链表同样适用于普通二叉树，结点除了数据外，还有左 右孩子与双亲的指针，存储密度低于二叉链表，但是可以非常方便地在二叉树中 遍历，不需要其他辅助工具。树是对数据进行的一种抽象的描述，具体的实现方法是链表，计算机本身的 存储构造就是开辟一个新空间，连续的，或者不连续的，然后我们就要思考如何 合理的利用这些空间，节约空间或者节约时间。而现在这种存储方法用二叉树的 这种抽象形式表现出来，容易让人容易理解一些而已，所以对于二叉树一般采用 二叉链表这样的存储方式。2. 3算法描述树的初始化函数（双亲法和孩子结点法两种），建树函数，输出树函数，输 得遍历（递归和非递归两种）。引入头文件：#include<stdio.h>#include<malloc.h>设置常量：# define DEGREES树的高度#define NULLO# define QUEUESIZE 10# define MAX_NODE_NUM 100树转换成二叉树的方法。一般是把树当前结点的的孩子当成左子树（或右子 树），层层转换而得到一个新的二叉树。根据树（森林）转换二叉树的方法，逆向 回去，就可以得到二叉树转换树的算法。先构建树和二叉树的结构体，数据域采用char类型。查找树的结点数，如 果访问为空那么返回NULL,负责放回data。输入数的结点数量、跟结点的数据及 结点数据和其父结点数据，构建一个有具体数据的树。根据递归先序遍历树，存 入栈、出栈方式储数中的数据。运用相关函数将树转换为二叉树。void TreeToBTree（CTreeNode *ctroot,BTreeNode *&btroot）树转化为二叉树ctroot指向树的根节点，btroot,指向二叉树的根。QueueCTree *VisitedCTreeNodes;QueueBTree * Visited BTreeNodes;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;依次数的根结点入队、处队，继而访问所有的孩子结点，孩子结点访问完毕， 树转换成二叉树把树当前结点的的孩子当成左子树（或右子树），层层转换而得到 一个新的二叉树。具体实施如下代码所示：for(i=0;i<DEGREE;i+) if(ctnode->childreni=NULL) break;p=(BTreeNode *)malloc(sizeof(BTreeNode);p->data=ctnode->childreni->data; p->lchild=p->rchild=NULL;if(i=0)btnode->lchild=p;elseLastSibling->rchild=p;LastSibling=p;addQueueCTree(VisitedCTreeNodes,ctnode->childreni);addQueueBTree(VisitedBTreeNodeszp); ）最后在main。函数中使用指针实现函数的调用，打印名称，返回先序遍历和 转化为二叉树后先序遍历的结果。