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

User usuarioanonimomysql en gmail.com
Mie Jun 20 20:44:13 CEST 2012


Perfecta explicación Salvador.

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

¡Muchas gracias!

El 7 de junio de 2012 12:16, <salvador en conclase.net> escribió:

> El pasado 2012-06-06 21:57:45, User escribió:
>
> U> Hola,
> U> He visto el siguiente prototipo para la función en C de insertar en un
> U> árbol binario de búsqueda:
> U> int insertarDato(void * nuevoDato, ArbolBB** ParbolBB, int
> U> (*fCompara)(void*, void*));
> U> No entiendo bien la finalidad del último parámetro. Ni tampoco por qué
> usa
> U> un doble puntero en ArbolBB.
>
> Hola:
> El último parámetro es un puntero a una función que, viendo el nombre y
> los argumentos que tiene, compara dos valores y retorna un entero. La regla
> general para este tipo de funciones es retornar un valor menor que cero si
> el primer parámetro es menor que el segundo, cero si son iguales y un valor
> mayor que cero si el primero es mayor que el segundo.
>
> Supongo que esa función se usa para establecer el orden dentro del árbol
> ABB, de modo que el nuevo dato se inserte en la posición correcta.
>
> El uso del doble puntero en el segundo parámetro es necesario. Hay que
> tener en cuenta que un ArbolBB se puede definir de dos modos. Una, que es
> la que yo prefiero es un puntero a un nodo. Es decir, cada puntero a un
> nodo es, o puede ser, la raíz de un árbol completo.
>
> Según esto, la definición del tipo arbolBB debería ser:
>
> typedef struct TNodo* ArbolBB;
>
> y la de la función de inserción:
>
> int insertarDato(void * nuevoDato, ArbolBB* ParbolBB,
>   int (*fCompara)(void*, void*));
>
> La otra forma es la de tu ejemplo, en la que la definición de ArbolBB es
> igual que la del nodo, y por lo tanto, el puntero al ArbolBB se convierte
> en un puntero doble en la función de inserción. Lo malo de esta forma es
> que para manejar los árboles necesitarás punteros a ArbolBB, lo cual puede
> ser bastante equívoco.
>
> En cualquier caso, se necesita un puntero doble. Si partimos de la primera
> definición para ArbolBB, pasaremos un puntero a nuestro árbol porque
> tenemos que tener en cuenta que el nuevo dato puede ocupar la posición de
> la raíz del árbol después de insertarlo. Esto ocurrirá cuando insertemos un
> dato en un árbol vacío. Si sólo pasamos como parámetro el ArbolBB, por
> copia, los cambios que hagamos en ese caso no se transfieren en el retorno,
> y la inserción no se ejecuta, además de producirse una fuga de memoria.
>
> Si partimos de la segunda forma, el problema es análogo, aunque más
> difícil de explicar. :)
>
> Ahora nuestro árbol estará declarado como:
>
> ArbolBB *nuestroArbol;
>
> Si queremos insertar un dato nuevo tendremos que pasar un puntero a
> nuestroArbol, que será un puntero doble a un ArbolBB.
>
> U> He visto otros prototipos más sencillos como este:
> U> int insertarDato(int nuevoDato, ArbolBB ParbolBB)
>
> La diferencia entre esta versión de insertarDato y la otra es que en esta
> se asume que el dato es de tipo entero, y también se asume un orden
> concreto, por lo que no hay que proporcionar una función de comparación.
>
> U> ¿Podríais poner un ejemplo de implementación para este prototipo?
>
> Hay muchas posibles soluciones, pero básicamente es igual que para un tipo
> de dato concreto, aunque intentar lo mismo para datos genéricos complica un
> poco el código.
>
> Lo siento, pero usaré la definición de ArbolBB siguiente:
>
> ----8<------
> typedef struct TNodo {
>   void* dato;
>   struct TNodo* hijoIzdo;
>   struct TNodo* hijoDcho;
> } TNodo;
>
> typedef struct TNodo* ArbolBB;
>
> void insertarDato(void* dato, ArbolBB *ParbolBB,
>   int (*fCompara)(void*, void*)) {
>   TNodo* padre = NULL;
>   TNodo* actual = *ParbolBB;
>
>   /* Buscamos la posición del dato dentro del árbol: */
>   while(!Vacio(actual) && 0 != fCompara(dato, actual->dato)) {
>      padre = actual;
>      if(fCompara(dato, actual->dato)<0) actual = actual->hijoIzdo;
>      else if(fCompara(dato, actual->dato)>0) actual = actual->hijoDcho;
>   }
>
>   /* Si el dato está en el árbol, regresamos sin hacer nada */
>   if(!Vacio(actual)) return;
>   /* Si el árbol está vacío, creamos un árbol nuevo: */
>   if(Vacio(padre)) {
>      *a = (ArbolBB)malloc(sizeof(TNodo));
>      (*a)->dato = dato;
>      (*a)->hijoIzdo= (*a)->derecho = NULL;
>   } /* Si no, creamos un nodo y lo añadimos al árbol: */
>   else if(fCompara(dato, padre->dato) < 0) {
>      actual = (ArbolBB)malloc(sizeof(TNodo));
>      padre->hijoIzdo= actual;
>      actual->dato = dat;
>      actual->hijoIzdo= actual->hijoDcho= NULL;
>   }
>   else if(fCompara(dato, padre->dato) > 0) {
>      actual = (ArbolBB)malloc(sizeof(TNodo));
>      padre->hijoDcho= actual;
>      actual->dato = dat;
>      actual->hijoIzdo= actual->hijoDcho= NULL;
>  }
> }
> ----8<------
>
> Puede que haya algún error, ya que no lo he compilado...
>
> Hasta pronto.
> _______________________________________________
> Lista de correo Cconclase Cconclase en listas.conclase.net
> http://listas.conclase.net/mailman/listinfo/cconclase_listas.conclase.net
> Bajas: http://listas.conclase.net/index.php?gid=2&mnu=FAQ
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.conclase.net/pipermail/cconclase_listas.conclase.net/attachments/20120620/540f549c/attachment.html>


Más información sobre la lista de distribución Cconclase