《二叉树的建立与先序,中序,后序,层次遍历,图的深度优先搜索和广度优先搜索 实验报告.doc》由会员分享,可在线阅读,更多相关《二叉树的建立与先序,中序,后序,层次遍历,图的深度优先搜索和广度优先搜索 实验报告.doc(4页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、树和图的遍历实验报告 2011-4-9实验题目:树和图的遍历实验目的:1.实现二叉树的建立与先序,中序,后序,层次遍历2.选择建立图的类型;根据所选择的类型用邻接矩阵的存储结构构建图;对图进行深度优先搜索和广度优先搜索;实验内容:一、 算法描述: (1)二叉树的建立 要建立一棵树就要有根节点和两棵子树。两棵子树的建立同样需要这样的过程。建立二叉树的过程也是遍历树的过程,实验要求以前序遍历的方式输入数据,因此我们也应按前序遍历的顺序,动态申请存储空间的方式建立这棵树并返回根节点的指针。BiTNode *CreateBiTree(BiTNode *T)char ch;if(ch=getchar()
2、= ) T=NULL;else if(ch!=n)if(!(T=(BiTNode *)malloc(sizeof(BiTNode) exit(1);T-data=ch;T-lchild=CreateBiTree(T-lchild);T-rchild=CreateBiTree(T-rchild);return T;(2)二叉树的遍历遍历作为二叉树所有操作的基础,因此我把它放在二叉树建立的前面。前序遍历:即按照根节点,左子树,右子树的顺序访问。具体操作:遇到节点,立即打印根节点的值,然后访问左子树,再访问右子树。对左子树和右子树的访问也进行相同的操作。void PreOrderTraverse(B
3、iTree T)if(T)putchar(T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild); 同理,易得中序遍历,后序遍历的操作。/中序遍历二叉树void InOrderTraverse(BiTree T)if(T)InOrderTraverse(T-lchild);putchar(T-data);InOrderTraverse(T-rchild);/后序遍历二叉树void PostOrderTraverse(BiTree T)if(T)PostOrderTraverse(T-lchild);PostOrderTrave
4、rse(T-rchild);putchar(T-data);层次遍历:先访问的节点,其孩子节点也必然优先访问,这就用到了队列的思想。void LevelTraverse(BiTree T)BiTree Q100;int front,rear;front=rear=0;队列置空BiTree p;if (T)Qrear=T;头结点入队rear=(rear+1)%Maxlength;while(front!=rear)p=Qfront;头元素出队front=(front+1)%Maxlength;putchar(p-data);打印节点数值if(p-lchild)Qrear=p-lchild;rea
5、r=(rear+1)%Maxlength;左孩子入队if(p-rchild)Qrear=p-rchild;rear=(rear+1)%Maxlength;右孩子入队(3)图的建立图的种类分为有向图、有向网、无向图和无向网,虽然都可用邻接矩阵表示,但不同种类的图其数组元素的值是不同的。在图中,顶点相邻接可用“1”表示,不邻接用“”表示;在网中,邻接可用其权值表示。但在具体操作中,“无向图(网)”的弧只需赋值相同值即可,“有向图(网)”的弧不同方向是不同的值,这就要求有向和无向的弧数算法不一样。所以在建立图时,注意到上述要求就可方便的建图。1. 判断欲建图的类型;2. 输入欲建图的顶点数和弧数;3
6、. 输入顶点元素;4. 构建顶点间的关系:有向图需区分起点、终点;有向网需区分起点、终点和权重,无向图只需输入相邻接的顶点,切忌重复输入;无向网还需输入权重。(4)关于图的深度优先搜索 深度优先搜索可以从图中的某个顶点V出发,访问此顶点,然后依次从V的未被访问过的邻接点出发深度优先遍历图,直至所有和V有路径相通的顶点都被访问过。void dfs1(MGraph *G,int i)int j;printf(%5s,G-vexsi);visitedi=1; /标记VI,表示其已被访问for(j=0;jvexnum;j+) /依次搜索VI的每个邻接点if(i!=j&G-arcsij.adj!=INF
7、INITY &!visitedj)dfs1(G,j); /递归调用(5)关于图的广度优先搜索 从图中某顶点V出发,在访问了V之后一次访问V的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问他们的邻接点,并使“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有被已访问的顶点的邻接点都被访问到。 void bfs1(MGraph *G,int i)int k,j;SqQueue Q;for(j=0;jvexnum;j+)visitedj=0; /初始化数组Initqueue_sq(&Q,G-vexnum);printf(n%5s,G-vexsi);visitedi=1;Enqueue_sq(&Q,i); /已访问过的初始点序号入队while(!Queueempty(Q)Dequeue_sq(&Q,&k); for(j=0;jvexnum;j+) /依次搜索VK的每个可能的邻接点if(k!=j&G-arcskj.adj!=INFINITY &!visitedj)printf(%5s,G-vexsj);visitedj=1;Enqueue_sq(&Q,j); /顶点序号J入队二、 运行结果(截图):