《数据结构》课程实验指导书

I求右深度hr-TreeDepth(T->rchild);max=hl>hr? hl:hr,//取左右深度的最大值NodeNum=NodeNum+1;/求结点数if(hl==0&&hr==0)leaf-leaf+1：I/若左右深度为0，即为叶子。return(max+1)1else return(0);31/主函数void mainOBinTree root,int i,depth;printf("n");printf("Creat Bin_Tree;Inputpreorder:");//输入完全二叉树的先序序列，I用#代表虚结点，如ABD###CE##F##root=CreatBinTreeO;//创建二叉树，返回根结点dotI/从菜单中选择遍历方式，输入序号。print(“"l*素***** select *******(n");printf("t1: Preorder Traversalln");printf("It2: Iorder Traversal\n"),printf("lt3: Postorder traversalln");printf("lt4: PostTreeDepth,Node number,Leaf numberln");printf("Ito: Exit)n");printf("\t***************事***n");scanf("%d",&i);//输入菜单序号（0-4)switch (i)case I: printf("Print Bin_tree Preorder: ");I1先序遍历Preorder(root);break,case 2: printf("Print Bin_ Tree Inorder: ");1/中序遍历Inorder(root);break,case 3: printf("Print Bin_Tree Postorder:");1/后序遍历Postorder(root),break,case 4: depth=TreeDepth(root);/求树的深度及叶子数printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);printf("BinTree Leaf number-%d",leaf);break,case 5:printf("LevePrint Bin Tree:");1/按层次遍历Levelorder(root),break,default: exit(1),1printf("In");6

6 hr=TreeDepth(T->rchild); //求右深度 max=hl>hr? hl:hr; //取左右深度的最大值 NodeNum=NodeNum+1; //求结点数 if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为 0，即为叶子。 return(max+1); } else return(0); } //主函数 void main(){ BinTree root; int i,depth; printf("\n"); printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列， // 用#代表虚结点，如 ABD###CE##F## root=CreatBinTree(); //创建二叉树，返回根结点 do{ //从菜单中选择遍历方式，输入序号。 printf("\t********** select ************\n"); printf("\t1: Preorder Traversal\n"); printf("\t2: Iorder Traversal\n"); printf("\t3: Postorder traversal\n"); printf("\t4: PostTreeDepth,Node number,Leaf number\n"); printf("\t0: Exit\n"); printf("\t*******************************\n"); scanf("%d",&i); //输入菜单序号（0-4） switch (i){ case 1: printf("Print Bin_tree Preorder: "); Preorder(root); //先序遍历 break; case 2: printf("Print Bin_Tree Inorder: "); Inorder(root); //中序遍历 break; case 3: printf("Print Bin_Tree Postorder: "); Postorder(root); //后序遍历 break; case 4: depth=TreeDepth(root); //求树的深度及叶子数 printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum); printf(" BinTree Leaf number=%d",leaf); break; case 5: printf("LevePrint Bin_Tree: "); Levelorder(root); //按层次遍历 break; default: exit(1); } printf("\n");

while(il=0);1实验三图的遍历操作实验目的（1）掌握图的邻接矩阵和邻接表的存储结构。（2）掌握图的两种常用存储结构下的深度优先搜索和广度优先搜索操作的实现。基本要求分别采用邻接矩阵和邻接表存储结构，完成图的深度优先遍历（DFS）和广度优先遍历（BFS）的操作。搞清楚BFS算法中队列的作用。实验内容分别用图的邻接矩阵和邻接表的存储结构实现下列基本运算：（1）创建图；（2）深度优先遍历图；（3）广度优先遍历图。算法实现程序（源程序代码）（1）邻接矩阵作为存储结构#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum100//定义最大顶点数typedef struct!/顶点表char vexs[MaxVertexNum];int edges[MaxVertexNum][MaxVertexNum];邻接矩阵，可看作边表int n,e;//图中的顶点数n和边数e)MGraph;/用邻接矩阵表示的图的类型1/建立邻接矩阵void CreatMGraph(MGraph *G)int i.j,k,char a,printf("Input VertexNum(n) and EdgesNum(e):");1/输入顶点数和边数scanf("%d.%d"&G->n.&G->e)scanf("%c",&a);printf("Input Vertex string:"),for(i=0,i<G->n;i++)(scanf("%c",&a),G->vexs[i]=a,//读入顶点信息，建立顶点表1for(i=0;i<G->n;i++)for(i=0;j<G->n;j++)G->edges[i][i]=0;1初始化邻接矩阵printf("Input edges,Creat Adjacency Matrixln");/读入e条边，建立邻接矩阵for(k=0;k<G->e;k++)(scanf("%d%d"&i,&i);1/输入边（V，V）的顶点序号G->edges[i][i]=1;G->edges[il[i]=1;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句7

7 }while(i!=0); } 实验三 图的遍历操作 实验目的 （1）掌握图的邻接矩阵和邻接表的存储结构。 （2）掌握图的两种常用存储结构下的深度优先搜索和广度优先搜索操作的实现。 基本要求 分别采用邻接矩阵和邻接表存储结构，完成图的深度优先遍历（DFS）和广度优先遍历（BFS）的 操作。搞清楚 BFS 算法中队列的作用。 实验内容 分别用图的邻接矩阵和邻接表的存储结构实现下列基本运算：（1）创建图；（2）深度优先遍历图； （3）广度优先遍历图。 算法实现程序（源程序代码） （1）邻接矩阵作为存储结构 #include"stdio.h" #include"stdlib.h" #define MaxVertexNum 100 //定义最大顶点数 typedef struct{ char vexs[MaxVertexNum]; //顶点表 int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表 int n,e; //图中的顶点数 n 和边数 e }MGraph; //用邻接矩阵表示的图的类型 //建立邻接矩阵 void CreatMGraph(MGraph *G){ int i,j,k; char a; printf("Input VertexNum(n) and EdgesNum(e): "); scanf("%d,%d",&G->n,&G->e); //输入顶点数和边数 scanf("%c",&a); printf("Input Vertex string:"); for(i=0;i<G->n;i++){ scanf("%c",&a); G->vexs[i]=a; //读入顶点信息，建立顶点表 } for(i=0;i<G->n;i++) for(j=0;j<G->n;j++) G->edges[i][j]=0; //初始化邻接矩阵 printf("Input edges,Creat Adjacency Matrix\n"); for(k=0;k<G->e;k++){ //读入 e 条边，建立邻接矩阵 scanf("%d%d",&i,&j); //输入边（Vi，Vj）的顶点序号 G->edges[i][j]=1; G->edges[j][i]=1;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句 }