Árboles binarios

Árboles binarios

Vuelvo a consultar en mi cd-rom de prácticas realizadas en mis tiempos universitarios, con una estructura que será muy útil para vosotros: árbol binario en inorden, y que podéis descargar bien desde éste mismo artículo de mi blog personal o bien de mi repositorio de github.

En el vais a encontrar los ficheros necesarios para utilizar ésta práctica libería en C. Vamos a comenzar con el fichero .h:

#ifndef AB_CHAR_TYPO

#define AB_CHAR_TYPO

struct ab_char_typo   {
	char cadena [20];
	struct ardi_int_rep *punt_arr;
    };

typedef struct ab_char_ele *ab_char;

// ------------------------------------------------------------------------

ab_char ab_char_nuev (void);
int ab_char_vacio (ab_char a);
void ab_char_raiz (ab_char a, struct ab_char_typo *e);
void ab_char_mete (ab_char *a, struct ab_char_typo e,
		int (*cmp_char) (const void *, const void *));
void ab_char_saca (ab_char *a, struct ab_char_typo *e,
		int (*cmp_char) (const void *, const void *));
void ab_char_dest (ab_char *a);
void ab_char_copy (ab_char a, ab_char *d);
ab_char ab_char_find (ab_char a, struct ab_char_typo *e,
		int (*cmp_char) (const void *, const void *));
void ab_char_printf (ab_char a, int posicion);
void ab_char_glosario (FILE *fp, ab_char a);

#endif

Continuamos con el desarrollo de la funcionalidad de todas éstas funciones en el fichero .c:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "arbbinar.h"
#include "arrdina.h"

struct ab_char_ele    {
	struct ab_char_typo val;
	struct ab_char_ele *izq, *der;
    };

// ------------------------------------------------------------------------
//			FUNCIONES PRIVADAS
// ------------------------------------------------------------------------

void ab_char_error (char primit [20], int error)    {
	switch (error)    {
		case 1:	fprintf (stderr, "\n\t %s: No hay suficiente memoria.\n", primit);
			break;
		case 2: fprintf (stderr, "\n\t %s: El arbol binario esta vacio.\n", primit);
			break;
	  }
   }

// ------------------------------------------------------------------------
//			FUNCIONES PUBLICAS
// ------------------------------------------------------------------------

ab_char ab_char_nuev ()   {

	return (NULL);
   }

// ------------------------------------------------------------------------

int ab_char_vacio (ab_char a)   {

	return (a == NULL);
    }

// ------------------------------------------------------------------------

void ab_char_raiz (ab_char a, struct ab_char_typo *e)   {

	if (!a)    {
		ab_char_error ("ab_char_raiz", 2);
		exit (1);
	   }

	*e = a -> val;
    }

// ------------------------------------------------------------------------

void ab_char_mete (ab_char *a, struct ab_char_typo e,
		int (*cmp_char) (const void *, const void *))   {

	if (!*a)   {
		*a = (struct ab_char_ele *) malloc (sizeof (struct ab_char_ele));
		if (!*a)    {
			ab_char_error ("ab_char_mete", 1);
			exit (1);
		    }
		(*a) -> izq = (*a) -> der = NULL;
		(*a) -> val = e;
	  }
	else   {
		if (cmp_char (&amp;(*a) -> val, &amp;e) > 0)
		     ab_char_mete (&amp;(*a) -> izq, e, cmp_char);
		else if (cmp_char (&amp;(*a) -> val, &amp;e) < 0)
			  ab_char_mete (&amp;(*a) -> der, e, cmp_char);
	 }
    }

// ------------------------------------------------------------------------

void ab_char_saca (ab_char *a, struct ab_char_typo *e,
		int (*cmp_char) (const void *, const void *))     {
	ab_char *corr, viejo;

	if (!*a)    {
		ab_char_error ("ab_char_saca", 2);
		exit (1);
	    }
	else  {
		if (cmp_char (&amp;(*a) -> val, e) > 0)
		    ab_char_saca (&amp;(*a) -> izq, e, cmp_char);
		else if (cmp_char (&amp;(*a) -> val, e) < 0)
		    ab_char_saca (&amp;(*a) -> der, e, cmp_char);
		else   {
			*e = (*a) -> val;
			  // Destruimos el tipo de dato que almacena
			ardi_int_dest (&amp;(*a) -> val.punt_arr);
			corr = &amp;(*a) -> der;
			if (*corr)    {
				while ((*corr) -> izq)
					corr = &amp;(*corr) -> izq;
				(*a) -> val = (*corr) -> val;
				viejo = *corr;
				*corr = (*corr) -> der;
				free (viejo);
			   }
			 else  {
				viejo = *a;
				*a = (*a) -> izq;
				free (viejo);
			   }
		   }
	    }
     }

// ------------------------------------------------------------------------

void ab_char_dest (ab_char *a)   {


	if (*a)   {
	      ab_char_dest (&amp;(*a) -> izq);
	      ab_char_dest (&amp;(*a) -> der);
	      // Destruimos el tipo de dato que almacena
	      ardi_int_dest (&amp;(*a) -> val.punt_arr);
	      free (*a);
	      *a = NULL;
	 }
    }

// ------------------------------------------------------------------------

void ab_char_copy (ab_char a, ab_char *d)    {
	int prim = 0, count;

	if (a)   {
		*d = (struct ab_char_ele *) malloc (sizeof (struct ab_char_ele));
		if (!*d)    {
			ab_char_error ("ab_char_copy", 1);
			exit (1);
		    }

		  // Copiamos el tipo de dato que almacena
		strcpy ((*d) -> val.cadena, a -> val.cadena);
		count = ardi_int_tamlog (a -> val.punt_arr);
		(*d) -> val.punt_arr = ardi_int_copy (a -> val.punt_arr, prim, count);

		ab_char_copy (a -> der, &amp;(*d) -> der);
		ab_char_copy (a -> izq, &amp;(*d) -> izq);
	    }
	 else *d = NULL;
    }

// ------------------------------------------------------------------------

ab_char ab_char_find (ab_char a, struct ab_char_typo *e,
		int (*cmp_char) (const void *, const void *))    {

	if (!a) return (NULL);
	if (cmp_char (&amp;a -> val, e) > 0)
	      return (ab_char_find (a -> izq, e, cmp_char));
	else if (cmp_char (&amp;a -> val, e) < 0)
	      return (ab_char_find (a -> der, e, cmp_char));
	else    {
		*e = a -> val;
		return (a);
	 }
   }

// ------------------------------------------------------------------------

void ab_char_printf (ab_char a, int posicion)     {

	if (a) {
		ab_char_printf (a -> der, posicion + 6);
		printf ("%*s \n", posicion, a -> val.cadena);
		ab_char_printf (a -> izq, posicion + 6);
	   }
    }

// -------------------------------------------------------------------------

void ab_char_glosario (FILE *fp, ab_char a)   {
	struct ardi_int_typo e, d;
	int tam, i;

	if (a)    {
	      ab_char_glosario (fp, a -> izq);
              tam = ardi_int_tamlog (a -> val.punt_arr);
              fprintf (fp, "%s", a -> val.cadena);
              fprintf (fp, "%c", ':');
              d.x = 0;
	      for (i = 0; i < tam; i++)   {
		     ardi_int_obti (a -> val.punt_arr, i, &amp;e);
                     if (d.x != e.x)    {
                          fprintf (fp, "%c", ' ');
		          fprintf (fp, "%d", e.x);
                          fprintf (fp, "%c", ',');
                       }
                     d.x = e.x;
		 }
	      fprintf (fp, "%c", '\n');
	      ab_char_glosario (fp, a -> der);
	  }
   }

Aún para los menos observadores, es necesario implementar una librería auxiliar necesaria para esta estructura de datos. Veamos las cabeceras de las funciones y procedimientos en el fichero .h:

#ifndef ARDI_INT_TYPO

#define ARDI_INT_TYPO

struct ardi_int_typo  {
	int x;
   };

typedef struct ardi_int_rep *ardi_int;

//  ---------------------------------------------------------------------

ardi_int ardi_int_nuev (void);
ardi_int ardi_int_const (int tamano, struct ardi_int_typo valorinicial);
ardi_int ardi_int_copy (ardi_int a, int prim, int count);
int ardi_int_tamfis (ardi_int a);
int ardi_int_tamlog (ardi_int a);
int ardi_int_infe (ardi_int a);
int ardi_int_supe (ardi_int a);
void ardi_int_obti (ardi_int a, int i, struct ardi_int_typo *e);
void ardi_int_asig (ardi_int a, int i, struct ardi_int_typo e);
void ardi_int_aumd (ardi_int a, struct ardi_int_typo e);
void ardi_int_disd (ardi_int a, struct ardi_int_typo *e);
void ardi_int_dest (ardi_int *a);
void ardi_int_swap (ardi_int a, int l, int r);
int ardi_int_bbin (ardi_int a, struct ardi_int_typo e,
	int (*cmp_int) (const void *, const void *));
int ardi_int_bsecd (ardi_int a, struct ardi_int_typo e,
	int (*cmp_int) (const void *, const void *));
int ardi_int_bseci (ardi_int a, struct ardi_int_typo e,
	int (*cmp_int) (const void *, const void *));
void ardi_int_qsort (ardi_int a, int (*cmp_int) (const void *, const void *));

#endif

Seguidamente os dejo el fichero .c con las implementaciones de cada uno de los procedimientos y funciones de ésta estructura de datos:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include "arrdina.h"

struct ardi_int_rep   {
	int tamfis;
	int tamlog;
	struct ardi_int_typo *arr;
   };

//  ---------------------------------------------------------------------
//               	FUNCIONES PRIVADAS
//  ---------------------------------------------------------------------

void ardi_int_error (int error, char prim [20])     {

	switch (error)    {
		case 1: fprintf (stderr, "\n\t%s: Error, no hay memoria suficiente.\n", prim);
			break;
		case 2: fprintf (stderr, "\n\t%s: Error, el array no existe.\n", prim);
			break;
		case 3:	fprintf (stderr, "\n\t%s: Error, el array esta vacio.\n", prim);
			break;
		case 4:	fprintf (stderr, "\n\t%s: Error, tama¤o < 1.\n", prim);
			break;
		case 5:	fprintf (stderr, "\n\t%s: Error, prim < 0.\n", prim);
			break;
		case 6:	fprintf (stderr, "\n\t%s: Error, count > elementos del array.\n", prim);
			break;
		case 7:	fprintf (stderr, "\n\t%s: Error, fuera de rango del array.\n", prim);
			break;
	  }
    }

//  ---------------------------------------------------------------------

struct ardi_int_typo *ardi_int_aloarr (int tamano)   {
	struct ardi_int_typo *arr;

	if (tamano == 0) return (NULL);
	else   {
		arr = (struct ardi_int_typo *) malloc (sizeof (struct ardi_int_typo) * tamano);
		if (arr == NULL)   {
		     ardi_int_error (1, "ardi_int_aloarr");
		     exit (1);
		   }
		return (arr);
	  }
   }

//   -------------------------------------------------------------------

ardi_int ardi_int_alo (int tamano)    {
	ardi_int p;

	p = (ardi_int) malloc (sizeof (struct ardi_int_rep));
	if (p == NULL)   {
	     ardi_int_error (1, "ardi_int_alo");
	     exit (1);
	   }

	p -> arr = ardi_int_aloarr (tamano);
	p -> tamfis = tamano;
	p -> tamlog = 0;
	return (p);
   }

//   -------------------------------------------------------------------

void ardi_int_daloarr (struct ardi_int_typo *arr)   {

	if (arr)   free (arr);
   }

//   -------------------------------------------------------------------

void ardi_int_dalo (ardi_int *p)    {

	if (*p != NULL)   {
	      ardi_int_daloarr ((*p) -> arr);
	      free (*p);
	      *p = NULL;
	 }
   }

//  ---------------------------------------------------------------------
//  		               	FUNCIONES PUBLICAS
//  ---------------------------------------------------------------------

ardi_int ardi_int_nuev ()  {
	ardi_int x;

	x = ardi_int_alo (0);
	return (x);
  }

//  ---------------------------------------------------------------------

ardi_int ardi_int_const (int tamano, struct ardi_int_typo valorinicial)   {
	ardi_int x;
	int i = 0, tamfis;

	if (tamano < 1)   {
		ardi_int_error (4, "ardi_int_const");
		exit (1);
	    }

	tamfis = (int) pow (2, ceil (log (tamano) / log (2)));
	x = ardi_int_alo (tamfis);
	while (i < tamano)     *(x -> arr+i++) = valorinicial;
	x -> tamlog = tamano;

	return (x);
  }

//  ---------------------------------------------------------------------

ardi_int ardi_int_copy (ardi_int a, int prim, int count)  {
	ardi_int x;
	int tamfis;

	if (!a)   {
		ardi_int_error (2, "ardi_int_copy");
		exit (1);
	   }
	if ((prim < 0) || (prim > a -> tamlog - 1))   {
		ardi_int_error (5, "ardi_int_copy");
		exit (1);
	   }
	if (count + prim - 1 > a -> tamlog - 1)   {
		ardi_int_error (6, "ardi_int_copy");
		exit (1);
	   }

	tamfis = (int) pow (2, ceil (log (count) / log (2)));
	x = ardi_int_alo (tamfis);
	memcpy (x -> arr, a -> arr + prim, count * sizeof (struct ardi_int_typo));
	x -> tamlog = count;

	return (x);
  }

//  ---------------------------------------------------------------------

int ardi_int_tamfis (ardi_int a)  {

	if (!a)   {
		ardi_int_error (2, "ardi_int_tamfis");
		exit (1);
	   }
	return (a -> tamfis);
   }

//  ---------------------------------------------------------------------

int ardi_int_tamlog (ardi_int a)  {

	if (!a)   {
		ardi_int_error (2, "ardi_int_tamlog");
		exit (1);
	   }
	return (a -> tamlog);
   }

//  ---------------------------------------------------------------------

int ardi_int_infe (ardi_int a)   {

	if (!a)   {
		ardi_int_error (2, "ardi_int_infe");
		exit (1);
	   }
	return (0);
   }

//  ---------------------------------------------------------------------

int ardi_int_supe (ardi_int a)   {

	if (!a)   {
		ardi_int_error (2, "ardi_int_supe");
		exit (1);
	   }
	return (a -> tamlog - 1);
   }

//  ---------------------------------------------------------------------

void ardi_int_obti (ardi_int a, int i, struct ardi_int_typo *e)     {

	if (!a)   {
		ardi_int_error (2, "ardi_int_obti");
		exit (1);
	   }
	if ((i < 0) || (i > a -> tamlog - 1))   {
		ardi_int_error (7, "ardi_int_obti");
		exit (1);
	   }

	*e = a -> arr [i];
  }

//  ---------------------------------------------------------------------

void ardi_int_asig (ardi_int a, int i, struct ardi_int_typo e)    {

	if (!a)   {
		ardi_int_error (2, "ardi_int_asig");
		exit (1);
	   }
	if (i < 0 || i > a -> tamlog - 1)   {
		ardi_int_error (7, "ardi_int_asig");
		exit (1);
	   }

	a -> arr [i] = e;
   }

//  ---------------------------------------------------------------------

void ardi_int_aumd (ardi_int a, struct ardi_int_typo e)   {
	struct ardi_int_typo *b;

	if (!a)   {
		ardi_int_error (2, "ardi_int_aumd");
		exit (1);
	   }

	if (!a -> tamlog)    *(a -> arr) = e;
	else if ((a -> tamlog) < (a -> tamfis))    a -> arr [a -> tamlog] = e;
	else   {
		b = ardi_int_aloarr (a -> tamfis * 2);
		memcpy (b, a -> arr, a -> tamfis * sizeof (struct ardi_int_typo));
		b [a -> tamlog] = e;
		ardi_int_daloarr (a -> arr);
		a -> arr = b;
		a -> tamfis *= 2;
	  }
	a -> tamlog++;
   }

//  ---------------------------------------------------------------------

void ardi_int_disd (ardi_int a, struct ardi_int_typo *e)   {
	struct ardi_int_typo *b;

	if (!a)   {
		ardi_int_error (2, "ardi_int_disd");
		exit (1);
	   }
	if (!a -> tamlog)   {
		ardi_int_error (3, "ardi_int_disd");
		exit (1);
	   }

	*e = a -> arr [a -> tamlog - 1];
	a -> tamlog--;

	if (a -> tamlog < (a -> tamfis / 2))   {
		b = ardi_int_aloarr (a -> tamfis / 2);
		memcpy (b, a -> arr, (a -> tamfis / 2) * sizeof (struct ardi_int_typo));
		ardi_int_daloarr (a -> arr);
		a -> arr = b;
		a -> tamfis /= 2;
	   }
   }

//  ---------------------------------------------------------------------

void ardi_int_dest (ardi_int *a)   {

	if (!*a)   {
		ardi_int_error (2, "ardi_int_dest");
		exit (1);
	   }
	ardi_int_dalo (a);
   }

//  --------------------------------------------------------------------

void ardi_int_swap (ardi_int a, int l, int r)   {
	struct ardi_int_typo aux;

	if (!a)   {
		ardi_int_error (2, "ardi_int_swap");
		exit (1);
	   }
	if (!a -> tamlog)   {
		ardi_int_error (3, "ardi_int_swap");
		exit (1);
	   }
	if (l < 0 || l > a -> tamlog - 1 || r < 0 || r > a -> tamlog - 1)   {
		ardi_int_error (7, "ardi_int_swap");
		exit (1);
	   }
	aux = a -> arr [l];
	a -> arr [l] = a -> arr [r];
	a -> arr [r] = aux;
   }

//  ---------------------------------------------------------------------

int ardi_int_bbin (ardi_int a, struct ardi_int_typo e,
			int (*cmp_int) (const void *, const void *))   {
	struct ardi_int_typo *t;

	if (!a)   {
		ardi_int_error (2, "ardi_int_bbin");
		exit (1);
	   }
	if (!a -> tamlog)   {
		ardi_int_error (3, "ardi_int_bbin");
		exit (1);
	   }

	t = (struct ardi_int_typo *) bsearch (&amp;e, a -> arr, a -> tamlog,
		sizeof (struct ardi_int_typo), cmp_int);

	if (!t)   return (-1);
	else   return (t - a -> arr);
   }

//  ---------------------------------------------------------------------

int ardi_int_bsecd (ardi_int a, struct ardi_int_typo e,
			int (*cmp_int) (const void *, const void *))   {
	int i;

	if (!a)   {
		ardi_int_error (2, "ardi_int_bsecd");
		exit (1);
	   }

	if (a -> tamlog)
		for (i = a -> tamlog - 1; i >= 0; i--)
		      if (!cmp_int (&amp;(a -> arr [i]), &amp;e))    return (i);
	return (-1);
   }

//  ---------------------------------------------------------------------

int ardi_int_bseci (ardi_int a, struct ardi_int_typo e,
			int (*cmp_int) (const void *, const void *))    {
	int i;

	if (!a)   {
		ardi_int_error (2, "ardi_int_bseci");
		exit (1);
	   }

	if (a -> tamlog)
		for (i = 0; i <= a -> tamlog - 1; i++)
		      if (!cmp_int (&amp;(a -> arr [i]), &amp;e))    return (i);
	return (-1);
   }

//  ---------------------------------------------------------------------

void ardi_int_qsort (ardi_int a, int (*cmp_int) (const void *, const void *))   {

	if (!a)   {
		ardi_int_error (2, "ardi_int_qsort");
		exit (1);
	   }
	if (!a -> tamlog)   {
		ardi_int_error (3, "ardi_int_qsort");
		exit (1);
	   }

	qsort (a -> arr, a -> tamlog, sizeof (struct ardi_int_typo), cmp_int);
  }

Para finalizar, es necesario disponer de un programita de prueba en C que verifique que verdaderamente funcionan todos y cada uno de los procedimientos y funciones de ésta estructura de datos en C:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include "arbbinar.h"
#include "arrdina.h"

#define PAGINA 60

// ------------------------------------------------------------------------

int cmp_int (const void *a, const void *b)   {
	return (*((int *) a) - *((int *) b));
    }

// ------------------------------------------------------------------------

int cmp_char (const void *a, const void *b)   {
	return (strcmp ((char *) a, (char *) b));
   }

// ------------------------------------------------------------------------

void blancos (char cadena [25])    {
	int i;
	for (i = 0; i < strlen (cadena); i++)   cadena [i] = ' ';
   }

// ------------------------------------------------------------------------

int delimitador (char c)    {
        return ((strchr ("+-*/=%|!­¨?()[]{}#&amp;$.,:;<>§¦", c)) ? 1 : 0);
   }

// ------------------------------------------------------------------------

void fichero_arbol (char *argv [], ab_char *a)    {
    FILE *fp;
    char palabra [25];
    ab_char basura;
    struct ab_char_typo arbol;
    struct ardi_int_typo array;
    int linea = 1, pagina = 1, i = 0, aparicion;
    char c;

    if ((fp = fopen (argv [1], "rt")) == NULL)   {
	 fprintf (stderr, "Fichero_arbol: El fichero %s no existe.\n", argv [1]);
	 exit (1);
      }

    printf ("\n\n\n\t N£mero m ximo de apariciones permitidas para los t‚rminos: ");
    scanf ("%d", &amp;aparicion);

    basura = ab_char_nuev ();

    while ((c = fgetc (fp)) != EOF)    {
         if ((!delimitador (c)) &amp;&amp; (!isdigit (c)) &amp;&amp; (c != ' ') &amp;&amp;
             (c != '\n') &amp;&amp; (c != '"') &amp;&amp; (c != '\0'))   {
	        palabra [i] = c;
	        i++;
	    }
	 else     {
	      palabra [i] = '\0';
	      i = 0;
	      if (palabra [i] != '\0')    {
		   arbol.punt_arr = NULL;
		   strcpy (arbol.cadena, palabra);
		   array.x = pagina;

		   if (ab_char_find (basura, &amp;arbol, cmp_char) == NULL)   {
		       if (ab_char_find (*a, &amp;arbol, cmp_char) == NULL)   {
			    arbol.punt_arr = ardi_int_const (1, array);
			    ab_char_mete (a, arbol, cmp_char);
			 }
		       else  {
			    if (ardi_int_tamlog (arbol.punt_arr) < aparicion)
				  ardi_int_aumd (arbol.punt_arr, array);
			    else    {
				  ab_char_saca (a, &amp;arbol, cmp_char);
				  arbol.punt_arr = ardi_int_nuev ();
				  ab_char_mete (&amp;basura, arbol, cmp_char);
			      }
			 }
		     }
		   blancos (palabra);
		}
	   }

	 if (c == '\n')   linea++;
	 if (linea > PAGINA)    {
		linea = 1;
		pagina++;
	   }
      }

    fclose (fp);

    ab_char_dest (&amp;basura);
  }

// ------------------------------------------------------------------------
//			    PROGRAMA PRINCIPAL
// ------------------------------------------------------------------------

int main (int argc, char *argv [])   {
      FILE *fp;
      ab_char arbol;
      int pos = 0;

      if (argc != 3)    {
             fprintf (stderr, "\tError: N£mero de par metros incorrecto.\n");
             fprintf (stderr, "\tUso: programa <fichero entrada> <fichero glosario>\n");
             exit (1);
         }

      printf ("\n\n\t\t 'GENERACIàN DE UN GLOSARIO DE TRMINOS'\n\n");
      printf ("\n\t Espere un momento......");

      arbol = ab_char_nuev ();
      fichero_arbol (argv, &amp;arbol);

      clrscr ();
      ab_char_printf (arbol, pos);

      if ((fp = fopen (argv [2], "wt")) != NULL)
		ab_char_glosario (fp, arbol);
      else fprintf (stderr, "Ha ocurrido un error al abrir el fichero %s.\n", argv [2]);
      fclose (fp);

      ab_char_dest (&amp;arbol);
      return;
  }

Con la despedida habitual en ésta serie de artículos, dejo el canal de comentarios abierto para que me dejéis vuestras opiniones, aportaciones e, incluso, código fuente alternativo.

No Comments

Post a Comment