求无向连通图的生成树
一、实验目的
⑴掌握图的逻辑结构
⑵掌握图的邻接矩阵存储结构
⑶验证图的邻接矩阵存储及其遍历操作的实现
二、实验容
（1）建立无向图的邻接矩阵存储
（2）对建立的无向图，进行深度优先遍历
（3）对建立的无向图进行广度优先遍历
三、设计与编码
（1）本实验用到的理论知识
（2）算法设计
（3）编码
// 图抽象类型及其实现.cpp : Defines the entry point for the console application.
//
#include"stdafx.h"
#include"Graph.h"
#include"iostream.h"
int Graph::Find(int key,int &k)
{
int flag=0;
for(int i=0;i if(A[i].data.key==key){k=i;flag=1;break;}; return flag; }; int Graph::CreateGraph(int vertexnum,Edge *E,int edgenum) { //由边的集合E(E[0]~E[VertexNum-1])，生成该图的邻接表表示 if(vertexnum<1)return(-1);//参数vertexnum非法 int i,front,rear,k; Enode *q; //先生成不带边表的顶点表--即顶点为孤立顶点集 A=new Vnode[vertexnum]; if(!A)return(0);//堆耗尽 for(i=0;i { A[i].data.key=i; A[i].tag=0; A[i].data.InDegree=A[i].data.OutDegree=A[i].tag=0; A[i].first=0; }; VertexLen=vertexnum; //在生成边表 if(edgenum<0)return(1);//无边的图 for(i=0;i { front=E[i].Head;rear=E[i].Tail; if(!Find(rear,k) || !Find(front,k))return(-2);//参数E非法 q=new Enode; if(!q)return(0); q->key=front; q->Weight=E[i].weight; q->next=A[rear].first; A[rear].first=q; A[rear].data.OutDegree++; A[front].data.InDegree++; if(Type>2) { q=new Enode; if(!q)return(0); q->key=rear; q->next=A[front].first; A[front].first=q; q->Weight=E[i].weight; }; }; return(1); }; void Graph::Dfs(int key,int &flag) { //static run=1; Enode *w; A[key].tag=flag; if(Type>2)cout<<"连通分量="< cout<<"顶点键值="< for(w=A[key].first;w ;w=w->next) if(!A[w->key].tag)Dfs(w->key,flag); }; int Graph::DfsDravers(int v0) //从指定顶点深度遍历 { int i,k,componentnum=1; //if(Type<3)return(-1);//不考虑由向图 //cout<<"begain....\n"; if(!(Find(v0,k))){cout<<"find=="< if(Type>2)cout<<"---连通分量"< Dfs(k,componentnum); componentnum++; for(i=0;i { if(!A[i].tag){ if(Type>2)cout<<"---连通分量 "< Dfs(i,componentnum);componentnum++; }; }; return(componentnum-1); }; int Graph::Bfs() { int i,comp=1; //comp=连通分量的标记，、、... struct queue{int key;queue * next;}; Enode *pe; queue *f,*r,*q,*p=new queue; if(!p)return(-1); //堆耗尽 p->next=0;f=r=p; //生成空队列 for(i=0;i for(i=0;i { if(A[i].tag==0) { A[i].tag=comp; //入队该顶点的key p=new queue; if(!p)return(-1); p->key=A[i].data.key; p->next=0; f->next=p;r=p; while(f->next)//当队非空时 {//出队一顶点 q=f->next; if(Type>2)cout<<"连通分量"< cout<<"顶点键值="< f->next=q->next; if(q==r)r=f; //与q连接的未访问的顶点入队 pe=A[q->key].first; while(pe) { if(A[pe->key].tag==0) {//入队 if(!(p=new queue))return(-1); A[pe->key].tag=comp; p->key=pe->key; p->next=0; if(f==r)f->next=p; r->next=p;r=p; }; pe=pe->next; };//end of (pe) delete q; };//end of (f->next) comp++; };//enf of if }; //释放队列 while(f){p=f->next;delete f;f=p;}; return comp-1; //返回连通分量数 }; /* int Graph::TopoSort(int *que,int &num) { //que顺序队列保存了拓扑排序的结果，f和r为que的头尾指示；loop用于判有无环 int i,f=0,r=0,index,loop=1; Enode *pe; num=0; for(i=0;i for(i=0;i if(loop)return(0); while(f {//栈未处理完 index=que[f++]; for(pe=A[index].first;pe;pe=pe->next) { A[pe->key].tag--; if(A[pe->key].tag==0){que[r++]=pe->key;A[pe->key].tag=-1;} ; }; }; num=r; if(r return 1; }; int main(int argc, char* argv[]) { Graph g1(1); int num=5,temp=1; int *stack=new int[5]; Edge b[12]; b[0].Head=1;b[0].Tail=0;b[0].weight=1; b[1].Head=3;b[1].Tail=1;b[1].weight=1; b[2].Head=0;b[2].Tail=2;b[2].weight=1; b[3].Head=1;b[3].Tail=4;b[3].weight=1; b[4].Head=4;b[4].Tail=2;b[4].weight=1; b[5].Head=4;b[5].Tail=3;b[5].weight=1; // b[6].Head=0;b[6].Tail=1;b[6].weight=1; b[7].Head=1;b[7].Tail=3;b[7].weight=1; b[8].Head=2;b[8].Tail=0;b[8].weight=1; b[9].Head=4;b[9].Tail=1;b[9].weight=1; b[10].Head=2;b[10].Tail=4;b[10].weight=1; b[11].Head=3;b[11].Tail=2;b[11].weight=1; //b=={{1,0,1},{3,1,1},{0,2,1},(1,4,1},{4,2,1},{2,3,1}}; g1.CreateGraph(num,b,6); if(g1.GetType()>2)cout<<"连通分量数 ="< cout<<"--------------"< if(g1.GetType()>2)cout<<"连通分量数="< if(g1.GetType()<3) { if(g1.TopoSort(stack,temp))cout<<"拓扑排序成功！\n"; else cout<<"该图有环！\n"; cout<<"部分或全部的拓扑序列为：(顶点总数 ="< for(int i=0;i }; delete[5]stack; //printf("Hello World!\n"); return 0; } 四、运行与调试 运行结果为： 该图有环！ 部分或全部拓扑序列为：<顶点总数=5> 2 0 已排序顶点数目=2 Press any key to continue 五、总结与心得 实验报告 课程名称数据结构 实验项目实验三--创建一个二叉树并输出三种遍历结果 系别■计算机学院 _________________ 专业_______________ 班级/学号_____________ 学生姓名___________ 实验日期— 成绩______________________________ 指导 教师 实验题目：实验三创建一个二叉树并输出三种遍历结果 实验目的 1）掌握二叉树存储结构； 2）掌握并实现二叉树遍历的递归算法和非递归算法; 3）理解树及森林对二叉树的转换; 4）理解二叉树的应用一哈夫曼编码及WPL计算。 实验内容 1）以广义表或遍历序列形式创建一个二叉树，存储结构自选； 2）输出先序、中序、后序遍历序列； 3）二选一应用题：1）树和森林向二叉树转换；2）哈夫曼编码的应用问题。 题目可替换上述前两项实验内容） 设计与编码 1）程序结构基本设计框架 （提示：请根据所选定题目，描述程序的基本框架，可以用流程图、界面描述图、 框图等来表示） 2）本实验用到的理论知识遍历二叉树，递归和非递归的方法 （应用型 (提示：总结本实验用到的理论知识，实现理论与实践相结合。总结尽量简明扼要，并与本次实验密切相关，要求结合自己的题目并阐述自己的理解和想法) 3) 具体算法设计 1) 首先，定义二叉树的存储结构为二叉链表存储，每个元素的数 据类型Elemtype,定义一棵二叉树，只需定义其根指针。 2) 然后以递归的先序遍历方法创建二叉树，函数为CreateTree()，在输 入字符时要注意,当节点的左孩子或者右孩子为空的时候,应当输入一 个特殊的字符(本算法为“ #”),表示左孩子或者右孩子为空。 3) 下一步,创建利用递归方法先序遍历二叉树的函数,函数为 PreOrderTreeQ,创建非递归方法中序遍历二叉树的函数，函数为 InOrderTree()，中序遍历过程是：从二叉树的根节点开始，沿左子树 向下搜索，在搜索过程将所遇到的节点进栈；左子树遍历完毕后，从 栈顶退出栈中的节点并访问；然后再用上述过程遍历右子树，依次类 推，指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的 函数，函数为LaOrderTree()。 (提示：该部分主要是利用C、C++ 等完成数据结构定义、设计算法实现各种操作，可以用列表分步形式的自然语言描述，也可以利用流程图等描述) 4) 编码 #include 用邻接表存储的无向图的深度优先生成树，树结点用孩子兄弟结构保存。下面是代码view plain 1.#include 41. tail->next=tail; 42. } 43. 44.bool empty() 45. { 46.return (tail->next==tail); 47. } 48. 49.void push(T d) 50. { 51. Node 数学与计算机学院 课程设计说明书 课程名称: 数据结构与算法课程设计 课程代码: 6014389 题目: 图的遍历和生成树求解实现 年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日 完成时间: 2012 年 12 月 26 日 课程设计成绩： 指导教师签名：年月日 目录 摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26) 摘要 《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。 因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。 关键词：计算机；图；算法。 实习三求无向连通图的生成树 1?需求分析 问题描述： 若要在n个城市之间建设通信网络，只需要架设n-1条路线即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。 基本要求： (1) 利用克鲁斯卡尔算法求网的最小生成树，其中，以课本8.7节中的等 价类表示构造生成树过程中的连通分量。 (2) 利用普里姆算法求网的最小生成树。 (3) 以文本文件形式输出生成树中各条边以及他们的权值。 2.设计 (1) 设计思想：创建邻接矩阵存储结构。本程序主要分为两个模块：创建邻接矩阵模块，最小生成树模块。创建邻接矩阵模块：以邻接矩阵的存储形式创建无向网。最小生成树模块：生成最小生成树，输出其各条边及权值。 (2) 概要设计：int型LocateVex函数判断权值在矩阵的位置；声明CraeteGraph 函数创建邻接矩阵；声明kruskal函数用于生成最小生成树；声明main函数为程序调用步骤。 (3) 设计详细：a.将程序分为两个模块： B. 主函数流程图: C. 最小生成树流程图 (4) 调试分析：--变量没定义就使用 --子函数嵌套定义； --使用数组是越界； (5) 用户手册：a.主页面： 解决：定义完变量在使用。 解决：子函数单独定义，可调用。 解决：注意数组的值，注意不能越界 b.输入顶点数及边数的信息: d.输入顶点及权值 c.输入顶点信息 （6）测试结果：输出最小生成树及 权值 #i nclude /*实验三：二叉树遍历操作验证*/ #include if(T) //若非空 { if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); } } //递归方法中序遍历二叉树 void inOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); if(T->data) { //输出 printf("%c",T->data); } preOrderTraverse(T->rchild); } } //递归方法后序遍历二叉树 void postOrderTraverse(BiTree T) { if(T) //若非空 { preOrderTraverse(T->lchild); preOrderTraverse(T->rchild); if(T->data) { //输出 printf("%c",T->data); } } } //层序遍历二叉树 void LevelTraverse(BiTree T) { queue 数据结构课程设计 题目: 线索二叉树的生成及其遍历 学院： 班级： 学生姓名： 学生学号： 指导教师： 2012 年12月5日 课程设计任务书 摘要 针对以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。增设两个指针分别指示其前驱和后继，但会使得结构的存储密度降低；并且利用结点的空链域存放（线索链表），方便。同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p 指向当前访问的结点，则 pre指向它的前驱。由此得到中序遍历建立中序线索化链表的算法 本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历的效果。 关键词二叉树，中序线索二叉树，中序线索二叉树的遍历 目录 摘要 ............................................ 错误！未定义书签。第一章,需求分析................................. 错误！未定义书签。第二章,概要设计 (1) 第三章,详细设计 (2) 第四章,调试分析 (5) 第五章,用户使用说明 (5) 第六章,测试结果 (5) 第七章,绪论 (6) 第八章,附录参考文献 (7) 线索二叉树的生成及其遍历 第一章需求分析 以二叉链表作为存储结构时，只能找到结点的左、右孩子的信息，而得不到结点的前驱与后继信息，为了使这种信息只有在遍历的动态过程中才能得到。增设两个指针分别指示其前驱和后继，但会使得结构的存储密度降低；并且利用结点的空链域存放（线索链表），方便。同时为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p 指向当前访问的结点，则 pre指向它的前驱。由此得到中序遍历建立中序线索化链表的算法 本文通过建立二叉树，实现二叉树的中序线索化并实现中序线索二叉树的遍历。实现对已生成的二叉树进行中序线索化并利用中序线索实现对二叉树的遍历的效果。主要任务： 1.建立二叉树； 2.将二叉树进行中序线索化； 3.编写程序，运行并修改； 4.利用中序线索遍历二叉树 5.书写课程设计论文并将所编写的程序完善。 第二章概要设计 下面是建立中序二叉树的递归算法，其中pre为全局变量。 BiThrNodeType *pre; BiThrTree InOrderThr(BiThrTree T) { /*中序遍历二叉树T，并将其中序线索化，pre为全局变量*/ BiThrTree head; head=(BitThrNodeType *)malloc（sizeof（BiThrType））;/*设申请头结点成功*/ head->ltag=0;head->rtag=1;/*建立头结点*/ head->rchild=head;/*右指针回指*/ if(！T)head->lchild=head;/*若二叉树为空，则左指针回指*/ else{head->lchild=T;pre=head; InThreading(T);/*中序遍历进行中序线索化*/ pre->rchild=head; pre->rtag=1;/*最后一个结点线索化*/ head->rchild=pre; }; return head; } void InThreading(BiThrTree p) {/*通过中序遍历进行中序线索化*/ if(p) 叉树的随机生成及其遍历 张 zhaohan 10804XXXXX 2010/6/12 问题重述 利用随机函数产生50个(不大于1 00且各不相同的)随机整数，用这些整数来生成一棵二叉树，分别对二叉树 进行先根遍历，中根遍历和后根遍历并输出树中结点元素序列。 程序设计 (一) 需求分析： ?问题的定义与要求： 1 、产生50个不大于100且各不相同的随机整数 (由系统的随机函数生成并 对100取模)；2、先根遍历并输出结果；3、中根遍历并输出结果；4、后根遍历并输出结果；按层次浏览二叉树结 5、点； 6、退出程序。 ?俞入：所需功能，选项为1?6。 ?输出：按照用户功能选择输出结果。 ?限制：输入的功能选择在1?6之间，否则无回应。 ?模块功能及要求： RandDif(): 生成50个随机不大于100的整数，每次生成不同随机整数。 CreateBitree(): 给数据结点生成二叉树，使每个结点的左右儿子指针指向左右儿子。 NRPreOrder(): 非递归算法的先根遍历。 inOrderTraverse(): 递归算法的中根遍历。 P ostOrderTraverseO：递归算法的后根遍历。 Welcome(): 欢迎窗口。 Menu()：菜单。 Goodbye()：再见窗口。 (二) 概要设计： 首先要生成二叉树，由于是对随机生成的50个数生成二叉树，故可以采取顺序存储的方式，对结点的左右儿子进行赋值。生成的二叉树是完全二叉树。 先根遍历的非递归算法： 1、根结点进栈 2、结点出栈，被访问 3、结点的右、左儿子（非空）进栈 4、反复执行2、3 ，至栈空为止。 先根遍历的算法流程图：根结点进栈( a[0]=T->boot,p=a[0] ) 访问结点printf(*p) 右儿子存在则进栈a[i]=(*p).rchild; i++; 左儿子存在则进栈a[i]=(*p).rchild; i++; 栈顶降低top--：i--;p=a[i]; 栈非空while(i>-1) 返回 中根遍历的递归算法流程图： T为空 Return; inOrderTraverse(T->lchild) Printf(T->data) inOrderTraverse(T->rchild) 返回 7.4.1无向图的连通分量和生成树。 void DFSForest(Graph G,CSTree &T) //建立无向图G的深度优先生成森林的 //（最左）孩子（右）兄弟链表T。 { T=NULL; for(v=0;v 课程名称：数据结构实验 实验项目：二叉树的创建及遍历 姓名： 专业：计算机科学与技术 班级： 学号： 计算机科学与技术学院 20 17年11 月22 日 哈尔滨理工大学计算机科学与技术学院实验报告 实验项目名称：二叉树的建立及遍历 一、实验目的 1.熟悉掌握课本二叉树相关理论知识 2.实践与理论相结合，掌握二叉树的应用程序 3.学会二叉树的创建，遍历等其他基本操作的代码实现 二、实验内容 1.二叉树的创建代码实现 2.二叉树先序、中序、后序遍历代码实现 三、实验操作步骤 1.二叉树的建立 （1）树节点的定义 由于每个节点都由数据域和指左子树和右子树的指针，故结构体封装如下： typedef struct node { int data; struct node *left; struct node *right; }Tree,*bitree; （2）建立 采用递归的思想，先建立根再建立左子树，再建立右子树。递归截止条件子树为空，用-1代表树空 *T=(struct node *)malloc(sizeof(struct node)); (*T)->data=a; printf("%d的左节点",a); create(&(*T)->left); printf("%d的右节点",a); create(&(*T)->right); 2.三种遍历的实现 （1）先序遍历 依旧采用递归的思想，先遍历根后遍历左子树再遍历右子树。 printf("%d ",T->data); Pro(T->left); Pro(T->right); （2）中序遍历 先遍历左子树再遍历根最后遍历右子树 Mid(T->left); printf("%d ",T->data); Mid(T->right); （3）后序遍历 先遍历左子树再遍历右子树最后遍历根 Later(T->left); Later(T->right); printf("%d ",T->data); （4）按层遍历 按层遍历采用队列的思想，先将第一个节点入队然后在将其出队将其左右孩子入队。依 #include int *visit=(int *)malloc((n+1)*sizeof(int)); int **a=(int **)malloc((n+1)*sizeof(int*)); int e,f; for(e=0;e<=n;e++){ a[e]=(int *)malloc(sizeof(int)*(n+1)); } for(e=1;e<=n;e++) for(f=1;f<=n;f++) a[e][f]=0; for(e=1;e<=n;e++) visit[e]=0; for(i=1;i<=m;i++){ scanf("%d %d",&e,&f); a[e][f]=1; a[f][e]=1; } int k=0; int sum=0; int *b=(int *)malloc((n+1)*sizeof(int)); DFS(a,1,&k,n,visit); sum++; b[0]=k; e=1; int v; for(v=1;v<=n;v++){ k=0; if(visit[v]==0){ DFS(a,v,&k,n,visit); sum++; b[e]=k; e++; } } printf("%d\n",sum); int t; for(i=0;i 数据结构实验五 课程数据结构实验名称二叉树的建立及遍历第页 专业班级学号 姓名 实验日期:年月日评分 一、实验目的 １．学会实现二叉树结点结构和对二叉树的基本操作。 ２．掌握对二叉树每种操作的具体实现,学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3.整理并上交实验报告。 三、实验内容 1.编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树,采用三种递归遍历算法（前序、中序、后序）对这棵二叉树进行遍历并计算出二叉树的高度。 2 .编写程序生成下面所示的二叉树,并采用先序遍历的非递归算法对此二叉 树进行遍历。 四、实验步骤 （描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的,发生的现象和中间结果) 第一题 #ｉnｃlude "sｔdafx.ｈ" #include＂ｉoｓtｒeam.h" #inclｕde"sｔｄliｂ.h" ＃incｌudｅ"ｓｔdiｏ.ｈ" #include 《数据结构》实验报告 实验内容：（一）判断一个图有无回路 （二）求一个无向图G的连通分量的个数 一、目的和要求（需求分析）： 1、了解图的定义和图的存储结构。 2、熟悉掌握图的邻接矩阵和邻接表。 3、理解图的遍历算法---深度优先搜索和广度优先搜索。 4、学会编程处理图的连通性问题。 二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 判断一个图有无回路： 在程序设计中，先必须确定所要创建的图是有向还是无向，是图还是网，其次再根据各自的特点，用连接表来实现创建。 在有向图中，先找出入度为0的顶点，删除与这个顶点相关联的边（出边），将与这些边相关的其它顶点的入度减1，循环直到没有入度为0的顶点。如果此时还有未被删除的顶点，则必然存在环路，否则不存在回路。 无向图则可以转化为： 如果存在回路，则必然存在一个子图，是一个回路。因此回路中所有定点的度>=2。 第一步：删除所有度<=1的顶点及相关边，并将另外与这些边相关的其它顶点的度减1。 第二步：将度数变为1的顶点排入队列，并从该队列中（使用栈）取出一个顶点，并重复步骤一。 如果最后还有未删除的顶点，则存在回路，否则没有。 求一个无向图G的连通分量的个数： 用连接表创建图，对于非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。所以在设计中，为了统计出无向图中的连通分量个数，则因在其深度优先所搜无向图时对函数DFSTraverse(ALGraph G)调用DFS次数进行统计，其结果便为无向图中连通分量个数。 三、调试和运行程序过程中产生的问题及采取的措施： 在调试和运行求一个无向图G的连通分量的个数程序时，由于执行语句块 void DFSTraverse(ALGraph G)先于void DFS(ALGraph G,int v)， 而void DFSTraverse(ALGraph G)内调用了DFS( )，因此计算机无法正确运行，将两者顺序进行了交换，程序便实现了其功能，且运行正常。 四、源程序及注释： 《数据结构》第六次实验报告 学生姓名 学生班级 学生学号 指导老师 一、实验内容 1) 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序 以及按层次遍历的操作，求所有叶子及结点总数的操作。 2) 输出树的深度，最大元，最小元。 二、需求分析 遍历二叉树首先有三种方法，即先序遍历，中序遍历和后序遍历。 递归方法比较简单，首先获得结点指针如果指针不为空，且有左子，从左子递归到下一层，如果没有左子，从右子递归到下一层，如果指针为空，则结束一层递归调用。直到递归全部结束。 下面重点来讲述非递归方法： 首先介绍先序遍历： 先序遍历的顺序是根左右，也就是说先访问根结点然后访问其左子再然后访问其右子。具体算法实现如下：如果结点的指针不为空，结点指针入栈，输出相应结点的数据，同时指针指向其左子，如果结点的指针为空，表示左子树访问结束，栈顶结点指针出栈，指针指向其右子，对其右子树进行访问，如此循环，直至结点指针和栈均为空时，遍历结束。 再次介绍中序遍历： 中序遍历的顺序是左根右，中序遍历和先序遍历思想差不多，只是打印顺序稍有变化。具体实现算法如下：如果结点指针不为空，结点入栈，指针指向其左子，如果指针为空，表示左子树访问完成，则栈顶结点指针出栈，并输出相应结点的数据，同时指针指向其右子，对其右子树进行访问。如此循环直至结点指针和栈均为空，遍历结束。 最后介绍后序遍历： 后序遍历的顺序是左右根，后序遍历是比较难的一种，首先需要建立两个栈，一个用来存放结点的指针，另一个存放标志位，也是首先访问根结点，如果结点的指针不为空，根结点入栈，与之对应的标志位也随之入标志位栈，并赋值0，表示该结点的右子还没有访问，指针指向该结点的左子，如果结点指针为空，表示左子访问完成，父结点出栈，与之对应的标志位也随之出栈，如果相应的标志位值为0，表示右子树还没有访问，指针指向其右子，父结点再次入栈，与之对应的标志位也入栈，但要给标志位赋值为1，表示右子访问过。如果相应的标志位值为1，表示右子树已经访问完成，此时要输出相应结点的数据，同时将结点指针赋值为空，如此循环直至结点指针和栈均为空，遍历结束。 三、详细设计 源代码： 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z， 〉，Z是整数集， 定义为x xy=xy, ?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 二叉树的创建与遍历 一、实验目的 1．学会实现二叉树结点结构和对二叉树的基本操作。 2．掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。 二、实验要求 1．认真阅读和掌握和本实验相关的教材内容。 2．编写完整程序完成下面的实验内容并上机运行。 3．整理并上交实验报告。 三、实验内容 1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归和非递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历。 四、实验步骤 源程序代码1 #include 求无向连通图的生成树 ————————————————————————————————作者：————————————————————————————————日期: 求无向连通图的生成树 一、实验目的 ⑴掌握图的逻辑结构 ⑵掌握图的邻接矩阵存储结构 ⑶验证图的邻接矩阵存储及其遍历操作的实现 二、实验内容 （1)建立无向图的邻接矩阵存储 (2)对建立的无向图,进行深度优先遍历 (3)对建立的无向图进行广度优先遍历 三、设计与编码 (1)本实验用到的理论知识 （2)算法设计 (３)编码 ／/ 图抽象类型及其实现．cpｐ : Defｉnes ｔhe enｔry poiｎt for the coｎｓｏle aｐplication. /／ #include"ｓtdafｘ.ｈ" #ｉｎclude"Graｐh.h" #incluｄe"ｉｏｓtream．h＂ int Grａｐｈ：:Ｆinｄ(int keｙ,int &ｋ) { ?iｎt flａg＝0; ?foｒ(iｎt i=0;i＜VｅrtexLｅn;ｉ++) ?if(Ａ[ｉ].ｄata.kｅy＝=ｋeｙ){k=ｉ;flaｇ=1;bｒeａk;}; ｒetuｒn fｌag; }; int Graｐh::CｒeａteGraph(inｔ vertexnuｍ,Edgｅ *E,inｔ edgeｎum) ｛／/由边的集合E(E[0]~Ｅ［VｅrtｅｘNum-1]）,生成该图的邻接表 表示 if(veｒtｅxnum<１）reｔurｎ(－１）;//参数vｅrtｅxnum非法ｉnt i,frｏｎt，reａr,k； ?Eｎode *ｑ; ?//先生成不带边表的顶点表--即顶点为孤立顶点集 ?A=newＶnode［verｔexnuｍ］; if(!A)return（0）;//堆耗尽 ?fｏｒ(i=０;i 求无向连通图得生成树 一、实验目得 ⑴掌握图得逻辑结构 ⑵掌握图得邻接矩阵存储结构 ⑶验证图得邻接矩阵存储及其遍历操作得实现 二、实验内容 (１)建立无向图得邻接矩阵存储 (2)对建立得无向图,进行深度优先遍历 (３)对建立得无向图进行广度优先遍历 三、设计与编码 (１)本实验用到得理论知识 (2)算法设计 (３)编码 ／/ 图抽象类型及其实现、ｃpp : Defiｎｅs the ｅntｒy poｉnt ｆor the cｏｎｓoｌe apｐｌicａtｉon、 // #incluｄｅ”stｄafx。h” #include”Gｒaph.h＂ ＃inｃlude”ioｓｔrｅaｍ。h” inｔＧraｐh::Fｉnd(int key,ｉnt＆ｋ) ｛ iｎt flag=0; fｏr(intｉ=０;i〈ＶertｅxＬeｎ;ｉ+＋) ?iｆ(A[ｉ］、dａta。kｅy==key){k＝i;fｌag=１;breａk;｝; ?return flag; ｝; int Gｒapｈ::CreateGraph(ｉnt verｔexnuｍ,Ｅdｇe ＊E,int edge ｎｕｍ) {?/／由边得集合E(E[0]~E［VertexNum—1]),生成该图得邻接表表示?if(veｒｔexｎｕm<1)reｔurn(—１);//参数verｔｅxnuｍ非法 ?ｉnt i,ｆronｔ,rｅar,k; Enode *ｑ; //先生成不带边表得顶点表-—即顶点为孤立顶点集 A=ｎew Vnｏde[vertexnｕm］; ?if(!Ａ)return(0);/／堆耗尽 for(ｉ=０;ｉ〈ｖｅrtexnum;ｉ++) { ?A[i］、data、kｅy＝i; ?A[i]、tａg=0; ??A［i]、ｄata.ＩｎDegree＝A[i]、ｄatａ。OutＤegｒee=A[i]、ｔaｇ＝0; ?A[i]、firｓt=０; ｝; VerｔexLen=veｒｔｅxｎum; ／/在生成边表 ?iｆ(edgenum〈0)return(1);//无边得图 for(i＝0;i＜edｇenuｍ;i++) { ? front＝E［i]。Heaｄ;ｒｅaｒ＝E[i]。Taｉl; ?iｆ(!Ｆiｎd(reaｒ,ｋ) ｜｜!Find(front,k))ｒeｔurn(－2);//参数E非法 ?q=new Enoｄｅ; ?if(！q)return(０); ??q-＞ｋｅy=frｏnt; q->Weigｈt=Ｅ[i]、weｉgｈt; ? q—>next=A［rear］。first; A［rear]、ｆｉｒsｔ=q; Ａ［rear]、data.ＯuｔＤegreｅ++; ? A［fｒｏnt］、datａ。InＤeｇreｅ＋+; if(Ｔype>2) ?｛ ?q=ｎew Enode; if(!q)retuｒn(０); ??q—〉key=ｒear; ???q-〉nexｔ=A［fｒｏnt]、ｆirst; ??A［fｒont］。fｉrst=ｑ;创建一个二叉树并输出三种遍历结果
无向图的深度优先生成树
数据结构课程设计图的遍历和生成树求解
实习三--求无向连通图的生成树
数据结构——二叉树的操作(遍历及树形输出)
数据结构课程设计_线索二叉树的生成及其遍历
二叉树的随机生成及其遍历
7.4.1无向图的连通分量和生成树
数据结构二叉树的创建及遍历
数据结构编程——求无向图连通子图
二叉树的建立及遍历
求一个无向图G的连通分量的个数
数据结构实验报告-二叉树的实现与遍历
1一个连通的无向图G
C++二叉树的创建与遍历实验报告
求无向连通图的生成树
求无向连通图的生成树
相关主题
文本预览