[C con Clase] Insertar en un árbol binario de búsqueda

[Salvador Pozo Coronado]

Hola:

Con fecha miércoles, 20 de junio de 2012, 20:44:13, escribió:

U> Perfecta explicación Salvador.

Me alegro que se haya aclarado algo. :)

U> ¿Podrías poner una implementación de la función fCompara?

Para  cada  tipo  de  dato  existirá,  en  principio,  una  función de
comparación diferente. Pondré un par de ejemplos.

Imaginemos un tipo de dato con esta definición:

----8<------
typedef struct fecha {
    int anno;
    int mes;
    int dia;
};
----8<------

Una función que compare fechas podría ser esta:

----8<------
int ComparaFechas(fecha* f1, fecha *f2) {
    if(f1->anno > f2->anno) return 1;
    else if(f1->anno < f2->anno) return -1;
    else if(f1->mes > f2->mes) return 1;
    else if(f1->mes < f2->mes) return -1;
    else if(f1->dia > f2->dia) return 1;
    else if(f1->dia < f2->dia) return -1;
    return 0;
}
----8<------

Verás  que  los  parámetros  de  la  función  son punteros a fecha, no
punteros  genéricos.  No  es  necesario  que sean genéricos, ya que el
compilador es capaz de hacer la conversión:

----8<------
#include <stdio.h>

typedef struct {
    int anno;
    int mes;
    int dia;
} fecha;

typedef int (*fCompara)(void*, void*);

int ComparaFechas(fecha* f1, fecha *f2);

int main()
{
    fCompara funcion;

    fecha f1 = {2012,6,26};
    fecha f2 = {2012,7,26};
    printf("%d\n", ComparaFechas(&f1, &f2));
    funcion = (fCompara)ComparaFechas;
    printf("%d\n", funcion(&f1, &f2));
    return 0;
}

int ComparaFechas(fecha* f1, fecha *f2) {
    if(f1->anno > f2->anno) return 1;
    else if(f1->anno < f2->anno) return -1;
    else if(f1->mes > f2->mes) return 1;
    else if(f1->mes < f2->mes) return -1;
    else if(f1->dia > f2->dia) return 1;
    else if(f1->dia < f2->dia) return -1;
    return 0;
}
----8<------

Para otro tipo de dato, por ejemplo:

----8<------
typedef struct {
    float x;
    float y;
} punto;
----8<------

Tenemos que elegir un criterio para decidir cuando un punto es "mayor"
o "menor" que otro. Podríamos ordenarlos por el valor de 'x', o por el
valor  de  'y'.  Para este ejemplo los ordenaremos por su distancia al
origen, cuanto más lejos estén del (0,0), mayores los consideraremos.

La distancia entre dos puntos (x1,y1), (x2,y2) se calcula como:
raiz_cuadrada((x1-x2)^2+(y1-y2)^2)

Si el punto 2 es el origen, la función se simplifica:
raiz_cuadrada(x1^2+y1^2)

Y   para   nuestros   propósitos,  podemos  optimizar  la  función  de
comparación,  y  no calcular la raíz cuadrada, ya que compararemos dos
distancias, el resultado es el mismo si comparamos el cuadrado de esas
distancias.

----8<------
int ComparaPuntos(punto* p1, punto *p2) {
    float d1, d2;

    d1 = p1->x*p1->x + p1->y*p1->y;
    d2 = p2->x*p2->x + p2->y*p2->y;

    if(d1 > d2) return 1;
    else if(d1 < d2) return -1;
    return 0;
}
----8<------

Y  así en general, para cada tipo de dato, habrá una o varias posibles
funciones de comparación.

Hasta pronto.
-- 
Saludos,
Salvador  mailto:salvador en conclase.net
Con Clase:  http://www.conclase.net