Estructuras de Datos Dinámicas en C: Pilas, Colas y Árboles Binarios

Estructuras de Datos Dinámicas en C

1. Pilas (LIFO: Last In, First Out)

Estructura de datos en la que el último elemento en entrar es el primero en salir.

Definición del nodo:

struct t_nodo {
    /* datos */
    int num;
    struct t_nodo *sig;
};

Operaciones con Pilas

• comp_vacia(struct t_nodo *pila): Comprueba si la pila está vacía.

  int comp_vacia(struct t_nodo *pila) {
      if (pila == NULL)
          return 1;
      else
          return 0;
  }

• inserta(struct t_nodo **ppila, int valor): Inserta un nuevo elemento en la cima de la pila.

  void inserta(struct t_nodo **ppila, int valor) {
      struct t_nodo *pilaux;
      pilaux = *ppila;
      *ppila = (struct t_nodo *)malloc(sizeof(struct t_nodo));
      (*ppila)->num = valor;
      (*ppila)->sig = pilaux;
  }

• elimina(struct t_nodo **ppila): Elimina el elemento situado en la cima de la pila.

  void elimina(struct t_nodo **ppila) {
      struct t_nodo *pilaux;
      pilaux = *ppila;
      (*ppila) = (*ppila)->sig;
      free(pilaux);
  }

• lista(struct t_nodo *pila): Recorre y muestra los elementos de la pila.

  void lista(struct t_nodo *pila) {
      while (pila != NULL) {
          printf("%d", pila->num);
          pila = pila->sig;
      }
  }

• borra: Vacía completamente la pila (equivalente a llamar repetidamente a elimina dentro de un bucle while mientras la pila no esté vacía).

2. Colas (FIFO: First In, First Out)

Estructura de datos donde el primer elemento en entrar es el primero en salir.

Definición de las estructuras:

struct t_nodo {
    int num;
    struct t_nodo *sig;
};

struct t_cola { struct t_nodo pri, ult; };

Operaciones con Colas

• comp_vacia(...): Comprueba si la cola no contiene elementos (por ejemplo, verificando si cola.pri == NULL).
• inserta(struct t_cola pcola, int valor): Inserta un elemento al final de la cola.

  void inserta(struct t_cola pcola, int valor) {
  if (comp_vacia(pcola)) {
  pcola->pri = (struct t_nodo )malloc(sizeof(struct t_nodo));
  pcola->ult = pcola->pri;
  pcola->pri->num = valor;
  pcola->pri->sig = NULL;
  } else {
  pcola->ult->sig = (struct t_nodo )malloc(sizeof(struct t_nodo));
  pcola->ult = pcola->ult->sig;
  pcola->ult->num = valor;
  pcola->ult->sig = NULL;
  }
  }

• elimina(struct t_cola pcola): Extrae el primer elemento de la cola.

  void elimina(struct t_cola pcola) {
  struct t_nodo colaux;
  colaux = pcola->pri;
  pcola->pri = pcola->pri->sig;
  free(colaux);
  }

• lista(struct t_cola cola): Recorre e imprime los elementos de la cola.

  void lista(struct t_cola cola) {
  while (cola.pri != NULL) {
  printf("%d", cola.pri->num);
  cola.pri = cola.pri->sig;
  }
  }

• borra: Vacía la cola por completo (equivalente a ejecutar elimina dentro de un bucle while mientras la cola no esté vacía).

3. Árboles Binarios

Conceptos clave:

• Árbol: Estructura de datos jerárquica compuesta por nodos dinámicos del mismo tipo.
• nodo_raiz: Es el nodo inicial del cual derivan todos los demás.
• nodo_terminal (hoja): Aquellos nodos que no tienen descendientes.
• altura: Cantidad de niveles de los que dispone el árbol.
• tipos: Binarios, ternarios... según el número máximo de descendientes permitidos (máximo 2, 3 descendientes, etc.).
• orden de recorrido: Preorden, inorden, postorden.

Definición del nodo del árbol binario:

struct t_nodo {
int num;
struct t_nodo izq, der;
};

Operaciones con Árboles

• inserta(struct t_nodo parbol, int valor): Inserta un nuevo valor en el árbol binario de forma ordenada.

  void inserta(struct t_nodo 

  parbol, int valor) { struct t_nodo paux, parbaux; int encontrado = 0; paux = (struct t_nodo *)malloc(sizeof(struct t_nodo)); paux->num = valor; paux->izq = paux->der = NULL;

  if (*parbol == NULL) {
      *parbol = paux;
  } else {
      parbaux = *parbol;
      while (!encontrado) {
          if (parbaux->num < valor) {
              if (parbaux->der == NULL) {
                  parbaux->der = paux;
                  encontrado = 1;
              } else {
                  parbaux = parbaux->der;
              }
          } else if (parbaux->izq == NULL) {
              parbaux->izq = paux;
              encontrado = 1;
          } else {
              parbaux = parbaux->izq;
          }
      }
  }

  }

• lista(struct t_nodo arbol): Recorrido en inorden para listar los elementos.

  void lista(struct t_nodo arbol) {
  if (arbol->izq != NULL)
  lista(arbol->izq);
  if (arbol != NULL)
  printf("%d", arbol->num);
  if (arbol->der != NULL)
  lista(arbol->der);
  }

• existe(struct t_nodo arbol, int valor): Busca recursivamente si un elemento se encuentra en el árbol.

  int existe(struct t_nodo arbol, int valor) {
  int existe_izq, existe_der;
  if (arbol != NULL) {
  if (arbol->num == valor)
  return 1;
  else {
  existe_izq = existe(arbol->izq, valor);
  existe_der = existe(arbol->der, valor);
  return existe_izq + existe_der;
  }
  } else {
  return 0;
  }
  }

• borra(struct t_nodo parbol): Libera recursivamente toda la memoria ocupada por el árbol.

  void borra(struct t_nodo 

  parbol) { if (parbol != NULL) { borra(&((parbol)->izq)); borra(&((parbol)->der)); free(parbol); *parbol = NULL; } }