二叉树的建立与先序,中序,后序,层次遍历,图的深度优先搜索和广度优先搜索 实验报告.doc

树和图的遍历实验报告 2011-4-9实验题目：树和图的遍历实验目的：1.实现二叉树的建立与先序，中序，后序，层次遍历2.选择建立图的类型；根据所选择的类型用邻接矩阵的存储结构构建图；对图进行深度优先搜索和广度优先搜索；实验内容:1、 算法描述： （1）二叉树的建立 要建立一棵树就要有根节点和两棵子树。两棵子树的建立同样需要这样的过程。建立二叉树的过程也是遍历树的过程，实验要求以前序遍历的方式输入数据，因此我们也应按前序遍历的顺序，动态申请存储空间的方式建立这棵树并返回根节点的指针。BiTNode *CreateBiTree(BiTNode *T)char ch;if(ch=getchar()= ) 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(BiTree 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);PostOrderTraverse(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;rear=(rear+1)%Maxlength;左孩子入队if(p-rchild)Qrear=p-rchild;rear=(rear+1)%Maxlength;右孩子入队（3）图的建立图的种类分为有向图、有向网、无向图和无向网，虽然都可用邻接矩阵表示，但不同种类的图其数组元素的值是不同的。在图中，顶点相邻接可用“1”表示，不邻接用“”表示；在网中，邻接可用其权值表示。但在具体操作中，“无向图（网）”的弧只需赋值相同值即可，“有向图（网）”的弧不同方向是不同的值，这就要求有向和无向的弧数算法不一样。所以在建立图时，注意到上述要求就可方便的建图。1. 判断欲建图的类型；2. 输入欲建图的顶点数和弧数；3. 输入顶点元素；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!=INFINITY &!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的每个可能