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 (&(*a) -> val, &e) > 0)
		     ab_char_mete (&(*a) -> izq, e, cmp_char);
		else if (cmp_char (&(*a) -> val, &e) < 0)
			  ab_char_mete (&(*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 (&(*a) -> val, e) > 0)
		    ab_char_saca (&(*a) -> izq, e, cmp_char);
		else if (cmp_char (&(*a) -> val, e) < 0)
		    ab_char_saca (&(*a) -> der, e, cmp_char);
		else   {
			*e = (*a) -> val;
			  // Destruimos el tipo de dato que almacena
			ardi_int_dest (&(*a) -> val.punt_arr);
			corr = &(*a) -> der;
			if (*corr)    {
				while ((*corr) -> izq)
					corr = &(*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 (&(*a) -> izq);
	      ab_char_dest (&(*a) -> der);
	      // Destruimos el tipo de dato que almacena
	      ardi_int_dest (&(*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, &(*d) -> der);
		ab_char_copy (a -> izq, &(*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 (&a -> val, e) > 0)
	      return (ab_char_find (a -> izq, e, cmp_char));
	else if (cmp_char (&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, &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 (&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 (&(a -> arr [i]), &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 (&(a -> arr [i]), &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 ("+-*/=%|!­¨?()[]{}#&$.,:;<>§¦", 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", &aparicion);
    basura = ab_char_nuev ();
    while ((c = fgetc (fp)) != EOF)    {
         if ((!delimitador (c)) && (!isdigit (c)) && (c != ' ') &&
             (c != '\n') && (c != '"') && (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, &arbol, cmp_char) == NULL)   {
		       if (ab_char_find (*a, &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, &arbol, cmp_char);
				  arbol.punt_arr = ardi_int_nuev ();
				  ab_char_mete (&basura, arbol, cmp_char);
			      }
			 }
		     }
		   blancos (palabra);
		}
	   }
	 if (c == '\n')   linea++;
	 if (linea > PAGINA)    {
		linea = 1;
		pagina++;
	   }
      }
    fclose (fp);
    ab_char_dest (&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, &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 (&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.

Dejar respuesta

Please enter your comment!
Please enter your name here