¿Cómo saber la altura de un árbol binario?

Responder
Irenicus
Mensajes: 1238
Registrado: 19 Mar 2007 23:22

¿Cómo saber la altura de un árbol binario?

Mensaje por Irenicus »

Me interesa saber la altura máxima que puede tener un árbol binario (http://computacion.cs.cinvestav.mx/~aca ... dArbol.jpg).

Aunque me interese en C++, si sabéis algo en pseudocódigo me vendría perfecto. Sin embargo, lo máximo que he conseguido ha sido una extraña versión mejorada de calcular el número de nodos, os paso la versión más larga y más clara:

Nota: hi y hd devuelven el "hijo izquierdo" e "hijo derecho" respectivamente. es_nulo es un boolenado que devuelve si un árbol vacío.
Nota2: Se trata de árboles de enteros.

Código: Seleccionar todo

int altura(Arbol<int> &a) {
    int alt = 0;
    if (not a.es_nulo()) {
        Arbol<int> a1;
        Arbol<int> a2;
        a1.hi(a);
        a2.hd(a); // podríamos usar a.hd() para ahorrar memoria, pero así queda más claro; no busco rendimiento por ahora
        int y = altura(a1);
        int z = altura(a2);
        if (y > z) alt = 1 + y;
        else alt = 1 + z;
    }
    return alt;
}
Por ejemplo, si introduzco el árbol

Código: Seleccionar todo

    1
  1  1
0 0 0 0
debería devolver altura = 2; pero me devuelve altura = 3; ¿alguna idea?
Avatar de Usuario
SoTA
Mensajes: 3394
Registrado: 03 Feb 2007 12:25

Re: ¿Cómo saber la altura de un árbol binario?

Mensaje por SoTA »

Es que está mal pensado, si estás muy rayado intento explicarte porque está mal, si solo quieres hacerlo mira esto que busqué para no rayarme a arreglar la tuya:

int AlturaArbol(Arbol a, int *altura) {
*altura = 0; /* (1) */

auxAltura(a, 0, altura);
return *altura;
}

void auxAltura(pNodo nodo, int a, int *altura) {
/* (2) Cada vez que llamamos a auxAltura pasamos como parámetro a+1 */
if(nodo->izquierdo) auxAltura(nodo->izquierdo, a+1, altura); /* Rama izquierda */
if(nodo->derecho) auxAltura(nodo->derecho, a+1, altura); /* Rama derecha */
if(EsHoja(nodo) && a > *altura) *altura = a; /* Proceso (Postorden) (3) */
}


EDITO: Tu funcion está en general bien, pero estás contando la raiz del arbol en la última iteración y se la estas sumando a la altura real. Si sabes que nunca vas a tener un arbol vacio puedes simplemente restar uno al resultado final(fuera de tu funcion) en caso contrario puedes crear otra funcion como esa que simplemente llame a esa con los hijos de la raiz y luego se quede con la mayor de las 2.
Avatar de Usuario
Zoltelder
Mensajes: 4727
Registrado: 02 Feb 2007 19:59
Ubicación: Badajoz

Re: ¿Cómo saber la altura de un árbol binario?

Mensaje por Zoltelder »

En programación nunca llegué a dar los arboles, ni en la uni ni en el modulo, pero si que los he dado ahora para la academia (aunque más como teoría y ejemplos con numeros y recorridos).

Yo veo más factible el saber que la raiz no se cuenta
Icono de PC  PC Gamer Desplegar firma
  • Procesador
    Intel i5 750 3.8GHz
  • Placa base
    Asus P7P55D PRO
  • RAM
    GSkill Trident 4GB 1600Mhz
  • Tarjeta gráfica
    Gigabyte 5850
  • Disco Duro
    SSD Crucial M4 128GB / WD CB 1TB / WD CB 500GB
  • Unidad Óptica
    -
  • Refrigeración
    Noctua NH-U12P SE2
  • Fuente alimentación
    Corsair HX 650
  • Caja
    Antec Twelve Hundred
  • Sonido
    Creative X-Fi Titanium
  • Sistema operativo
    Windows 7 Ultimate 64 bits
  • Monitor
    LG W2453V-PF
  • Teclado
    Logitech Wave
  • Ratón
    Logitech G9x
  • Otros
    Sennheiser PC350
  • Otros
    -
Ocultar
Irenicus
Mensajes: 1238
Registrado: 19 Mar 2007 23:22

Re: ¿Cómo saber la altura de un árbol binario?

Mensaje por Irenicus »

SoTA escribió:EDITO: Tu funcion está en general bien, pero estás contando la raiz del arbol en la última iteración y se la estas sumando a la altura real. Si sabes que nunca vas a tener un arbol vacio puedes simplemente restar uno al resultado final(fuera de tu funcion) en caso contrario puedes crear otra funcion como esa que simplemente llame a esa con los hijos de la raiz y luego se quede con la mayor de las 2.
Pero es que al final de cada árbol siempre habrá, por cada nodo, dos árboles vacíos. Es decir, siempre tiene que terminar en 0 para señalar que el árbol ha acabado.

Esa nomenclatura me recuerda a la página CconClase, jejeje. Ya me parecía que necesitaba una función auxiliar. ¡Le voy a echar un vistazo, gracias!

Actualizado:

He puesto el código adaptándose a mis módulos, y tendría que quedar una cosa así:

Código: Seleccionar todo

void auxAltura(Arbol<int> &a, int aux, int &altura) {

    if(a.es_nulo()){
        if (aux > altura) altura = aux;
    }
    else {
        Arbol<int> a1;
        a1.hi(a);
        auxAltura(a1, aux+1, altura);
        a.hd();
        auxAltura(a, aux+1, altura);    
    }
}

int AlturaArbol(Arbol<int> &a) {
    int altura = 0;
    auxAltura(a, 0, altura);
    return altura;
}
Sigue haciendo lo mismo, hace exactamente lo mismo que mi código pero más lento, jajaja. ¿Me he equivocado traduciéndolo?
Avatar de Usuario
SoTA
Mensajes: 3394
Registrado: 03 Feb 2007 12:25

Re: ¿Cómo saber la altura de un árbol binario?

Mensaje por SoTA »

No te equivocaste traduciendo, de hecho, hiciste exactamente lo mismo que tenías pero con 2 funciones, y precisamente por eso te hace lo mismo.

Creo que no me entendiste:

Como tu dices, al llamar a la funcion de los nodos te devolverá 0, eso está bien. Lo que tienes mal es que el nodo raiz(el primer nodo de todos) tambien lo tienes en cuenta en la altura, cuando no debe ser así.

Con respecto a lo nuevo que hiciste, te estás liando. Ahora no tengo tiempo, en la noche te lo arreglo, asi lo verás mejor.
Irenicus
Mensajes: 1238
Registrado: 19 Mar 2007 23:22

Re: ¿Cómo saber la altura de un árbol binario?

Mensaje por Irenicus »

¡Soy idiota!

La función que yo tengo está bien, ¡el problema es como leo los árboles! Me explico:

Mi módulo árbol, los lee "de arriba abajo y después de izquierda derecha"; es decir, si introduzco el árbol

Código: Seleccionar todo

    1
  1  1
0 0 0 0
escrito 1 1 1 0 0 0 0 en el canal de entrada, lo que estoy haciendo es leer el árbol

Código: Seleccionar todo

    1
  1  0
1 0 0 0
con lo cual la altura es, efectivamente, 3.

He probado el caso de poner 1 1 0 0 1 0 0 (que correspondería al primer árbol) y efectivamente da 2.

Así que para quien la necesite, la función más óptima de altura que he sabido hacer es, aplicando los cambios necesarios para cada módulo, la siguiente:

Código: Seleccionar todo

int altura(Arbol<int> &a) {
    int alt = 0;
    if (not a.es_nulo()) {
        Arbol<int> a1;
        a1.hi(a);
        a.hd();
        int y = altura(a1);
        int z = altura(a);
        if (y > z) alt = 1 + y;
        else alt = 1 + z;
    }
    return alt;
}
:D
Avatar de Usuario
SoTA
Mensajes: 3394
Registrado: 03 Feb 2007 12:25

Re: ¿Cómo saber la altura de un árbol binario?

Mensaje por SoTA »

Pero si esos 2 arboles tienen altura 2.......

Esta vez te has liado por partida doble(y pensaba que ayer en el msn te habia quedado claro :roll: ), primero asegurate bien de saber cual es la altura:

Es el número de saltos que hay desde la raiz hasta la última hoja(la más alejada).
Irenicus
Mensajes: 1238
Registrado: 19 Mar 2007 23:22

Re: ¿Cómo saber la altura de un árbol binario?

Mensaje por Irenicus »

No, no, el primero es 2 y el segundo es 3 (se me ha olvidado poner los dos 0 debajo del último uno a la izquierda, pero se sobreentiende).

La idea inicial que tuve al hacer la función estaba bien, pero el módulo de árbol (que ya estaba implementado) lee primero todos los hijos hasta que sea posible; y luego pasa a la raíz de abajo a la izquierda si es posible; si no es posible, a la de la derecha; si no es posible, al "hermano" de la última raíz, y así hasta leerlo todo.

Yo pensaba que el que había hecho el módulo lo había hecho para que leyera así como iban entrando, leer un "nivel".

Ahora funciona perfecto.
Avatar de Usuario
SoTA
Mensajes: 3394
Registrado: 03 Feb 2007 12:25

Re: ¿Cómo saber la altura de un árbol binario?

Mensaje por SoTA »

Vale, yo entendía que los 0 y 1 eran valores cualesquiera de los nodos y la funcion es_nulo comparaba con NULL no con 0, ahora veo que los 1 son los nodos que tienen contenido y los 0 son los nodos que marca el fin de una rama.

Entonces si que está bien, pero ¿porque no me dijiste nada por el msn cuando te ponia los ejemplo con null? xD

Está bien el código, pero me descoloca el hecho que uses ceros para marcar el fin de las ramas, es ineficiente pues usa hasta 2 elevado a la altura del arbol nodos más de los necesarios, si os dijo el profesor que lo hicierais así pues ya está, pero si se te ocurrió a ti deberías cambiarlo, solo cambia una linea de tu código.
Irenicus
Mensajes: 1238
Registrado: 19 Mar 2007 23:22

Re: ¿Cómo saber la altura de un árbol binario?

Mensaje por Irenicus »

El módulo de árbol está hecho por la facultad.
Responder