讲解(第三、四、五、六章).ppt

[解题思路3] 对树做层次遍历，每遍历一层树的深度+1. 关键在于如何判断本层遍历的结束。 解决方法：可将队列中的结点结构变为(结点，该结点的层数i) 。 * 算法Depth(t. d) //t指向与树自然对应的二叉树的根 D1 [判断t是否为NULL] IF t=NULL THEN ( d← -1 . RETURN ) D2 [创建辅助队列, 根结点入队] CREATE(Q). Q ?( t, 0) . d←0. D3 [利用队列Q遍历第d层结点] WHILE NOT (IsEmpty(Q)) DO ( (p, d) ? Q . WHILE p≠NULL DO ( IF FirstChild(p)≠NULL THEN Q?(FirstChild(p),d+1) p←NextBrother(p) .) ) ▌ 树的层次遍历 A C B G D F E * 4-12 请构造权值为{ 5,13,21, 7,18,30,41}的哈夫曼树。 * 4-12 首先，在森林中取权值最小的两个根结点s和n，合成一棵二叉树，新生成的结点T1，作为这两个结点的父结点，T1的权值是两个子结点的权值之和； 对新的森林重复上一步操作，直至森林中只有唯一的根结点时，终止操作。 * { 5，13，21，7，18，30，41 } 25 80 55 135 12 41 39 30 5 13 7 18 21 * 5-7 用邻接矩阵存储一个包含1000个顶点和1000条边的图，则该图的邻接矩阵中有多少元素？有多少非零元素？该矩阵是否为稀疏矩阵？ * １）矩阵中元素个数：1000000 ２）若图为有向图： 　　非零元素的个数：1000 　　若图为无向图： 　　非零元素的个数：2000 ３）该矩阵是稀疏矩阵 5-7 * 5-12 设计一个算法，检测采用邻接表方法存储、具有n个顶点的有向图中是否存在从顶点v到顶点u的路径，若存在路径，算法给出信息TRUE，否则，给出信息FALSE . * 算法Pathornot (Head, v, visited. visited) BFS1. [初始化] CREATQ(Q). // 创建队列 Q FOR i = 1 TO n DO visited[i] ? 0. PRINT(v) . visited[v] ? 1. Q ? v. BFS2. [广度优先遍历] WHILE Q 非空 DO ( v ? Q. p?adjacent(Head[v]) . WHILE p?? DO ( IF visited[VerAdj(p)] = 0 THEN IF (VerAdj(p)=u) THEN RETURN TRUE ELSE ( Q?VerAdj(p). PRINT(VerAdj(p)) . visited[VerAdj(p)]?1.). p ? link(p). ) ) RETURN FALSE.? * 5-13 设G＝（V,E）是有向图，请给出算法，判 断G中是否有回路，并要求算法的复杂性为 O（n+e）。 书中P146，拓扑排序算法： void Graph :: TopoOrder( ) { Stack S; for ( int i=0 ; in ; i + + ) if ( count[i] = = 0 ) { S.push(i) ; } * for ( int i=0 ; in ; i + + ) if ( S. StackEmpty ) //检测图中是否有回路 { cout There is a cycle in network ! endl ;  return ; } else { int j= S.pop() ; coutjendl ; //输出栈顶j Edge *p = head[j].Adjacent ; while( p != NULL ) //把j的所有邻接顶点的入度减1 { int k=p-VerAdj ; if ( --count[k]= = 0 )