Altura de arbol binario

[l337*]

hola, me pasaron este metodo para calcular la altura de un BST.

Código (java) [Seleccionar] Expandir


protected int height(TreeNode tNode) //method that will return height of tree
{
if(tNode == null)   //if empty height 0
{
return 0;
}

else   
{
return 1 +(Math.max(height(tNode.getLeft()),height(tNode.getRight())));   //NO ENTIENDO ESTA PARTE, PORQUE EL MATH ???
}
}




Me podrian explicar la parte de return 1 + ....
??
gracias d antemano


saludz 

[Lu15_CL4]

^^
el math.max te regresa el valor maximo de los que le pases en este caso le estas pasando 2 valores la longitud del arbol por la derecha y la de su izquierda, solamente te da el mas grande
, nomas preguntaste por el math... ^^, todo el funcionamiento es recursivo es mucha explicacion ^^'...

[Ragnarok]

Para hallar la profundidad de cada nodo toma la profundidad máxima de sus hijos y le suma uno (correspondiente a ese nodo).

[l337*]

ahh ok maravilloso gracias


lo de recursividad si lo entiendo

saludz 

[imnohacker]

Hola se que tal vez es un poco tarde y ya te habras dado cuenta pero para futuras personas que vean este mensaje, les comento que el codigo que pones falla para un caso especial. En que el Nodo raiz no tenga ningun Hijo, para lo que el programa que has puesto dara altura 1 y debería ser 0

Les adjunto el codigo correcto en C estandar

#include "nodoarbol.h"
#include <stdlib.h>

// Funcion auxiliar para calculo del maximo
int max(int a,int b){
   if (a<b)
      return b;
   else
      return a;
}

// Funcion solicitada
int alturaMaxima(PNodoArbol raiz){
   if (raiz != NULL){
      // No Contabilizo los nodos Hoja
      if ((raiz->der==NULL) && (raiz->izq==NULL))
         return 0;
      else
      // Cada vez que avanzo por un hijo aumento altura
         return 1 + max(alturaMaxima(raiz->izq),alturaMaxima(raiz->der));
   }else
      return 0;
}

donde "nodoarbol.h" es:

struct NodoArbol {
int dato; //Almacena el dato
struct NodoArbol* izq; //Apunta al subarbol izquierdo (valores menores)
struct NodoArbol* der; //Apunta al subarbol derecho (valores mayores)
};

typedef struct NodoArbol TNodoArbol, *PNodoArbol;

Saludos.