program treeHeigth !=========================================================================! ! Programa para calcular la altura de un arbol. El nodo inicial (del que) ! ! dependen todos los hijos, tiene por definicion altura = 1 ! ! La numeracion de los vertices se incrementa en cada nivel y dentro ! ! del nivel, de izq. a drcha. La estructura de datos para representar el ! ! arbol es una matriz. La primera fila contiene todos los vertices. Cada ! ! contiene los hijos del vertice del primer elemento de esa columna. ! ! ! ! El algoritmo consiste en recorrer de forma adecuada la matriz, tal que ! ! puedo determinar el nivel de cada vertice en base a los niveles ! ! gurdados en el recorrido hasta el momento. Empezando por la primera ! ! col. determino el nivel de los hijos del primer vertice (2) y guardo el ! ! resultado (en un vector de niveles para c/vertice). Luego en el paso K ! ! ,el nivel de los hijos del vertice K (nivel de K + 1) al recorrer la ! ! col. K. EL nivel de K ya fue guardado en el recorrido previo pues esta ! ! en alguna columna anterior. Finalmente del vector de niveles hallo el ! ! maximo y esa es la altura del arbol. ! !=========================================================================! integer,dimension(3,7) :: tree ! matriz q repr. el arbol integer,dimension(7) :: vertexLevels ! vector q contiene los niveles de c/vertice integer :: vertex,child,heigth,row,max !----- instancio las variables ------- tree(1,1:7) = (/1,2,3,4,5,6,7/) tree(2,1:7) = (/2,4,6,0,7,0,0/) tree(3,1:7) = (/3,5,0,0,0,0,0/) vertexLevels = (/0,0,0,0,0,0,0/) !----- el nivel del primer vertice es 1 ------ vertexLevels(1) = 1 ! ---- recorro c/vertice ------ do vertex = 1,7 print *, "========================" row = 2 ! para c/columna dada por "vertice", la recorro child = tree(row,vertex) ! empiezo por la segunda fila, determino el hijo print*, "vertice: ",vertex do while ((child /= 0).and.(row < 4)) ! continuo recorriendo las filas mientras que no sean print *, "hijo: ",child ! cero los hijos y actualizo en ese caso el nivel de vertexLevels(child) = vertexLevels(vertex) + 1 ! hijo encontrado row = row + 1 ! finalizo hasta encontrar un cero o si termina la if (row < 4) then ! matriz (maximo nro. de filas es 3) child = tree(row,vertex) end if end do end do ! ---- Encuentro el maximo de nivelesVertices, ese es la altura del arbol ---- max = vertexLevels(1) do i = 2,7 if (vertexLevels(i) > max) then max = vertexLevels(i) end if end do print *, print *, "La altura del arbol es: ",max end program treeHeigth