Programación General > C/C++

 Re: UN FAVOR, no tendran un algoritmo para encontrar la lon

(1/1)

brenda:

De Profundiis:
Hola,
se me ocurre una solución así a bote pronto en el caso de que tengas el árbol representado con memoria estática (un vector, por ejemplo).

Tal que así:

0  1 2 3  4 5 6 7 ... (indice del vector)
A  B C D E F G H ... (nodo)
-1 0 0 1 1 2 2 3 ...  (padre del nodo)

Entonces podrías recorrerlo del final hacia arriba buscando el padre y guardándote la profundidad. Por cierto, supongo que con longitud te refieres a la altura del árbol, ¿no?

Podría ser...
suponiendo el árbol representado en un vector V:

MaxProf = 0;
for(i = longitud(V); i > 0 ; i--){
  Profund = 0; j = longitud(V);
  while(j != -1) {
    i = V[ i ];
    Profund++;
  }
  if(Profund>MaxProf)MaxProf = Profund;
}
Altura = MaxProf;


Puff, si lo tienes con punteros... no se me ocurre cómo hacerlo, tendría que buscar en algún libro... siento no poder darte nada mejor:(

Bueno, un saludo.

Murciego:
Creo que se puede hacer de forma recursiva de la siguiente manera:

int alturaArbol(arbol a)
   {
   //Caso base: Estamos en una hoja;
   if (esHoja(a)) return 0;
   else
      {
       return 1+maximo(alturaArbol(a.hijoIzquierdo),alturaArbol(a.hijoDerecho));
      }
}

Espero que te sirva de ayuda. Tendrás que adaptar el codigo a tu caso concreto


Un saludo

Javier Murciego

Navegación

[0] Índice de Mensajes