Algoritmos de Árboles Binarios: Recorridos y Operaciones en C

Ejercicio 3: Recorrido Inorden No Recursivo

Implementar una función no recursiva para recorrer un árbol binario en inorden.

void inordenNR(ArbolB T, void (*EscribirElemento)(void *), int tamaño) {
  NodoB nodoActual, aux;
  void *et;
  Pila p;
  int fin;
  int faltaHD; /* Indica si falta el hijo derecho */

  p = CrearPila(sizeof(NodoB));
  et = malloc(tamaño);

  if (!et) {
    /* Error: Sin memoria */
    return;
  }

  aux = NODOB_NULO;
  Push(&aux, p);
  nodoActual = RaizB(T);
  fin = 0;

  while (!fin) {
    while (nodoActual != NODOB_NULO) {
      Push(&nodoActual, p);
      nodoActual = HijoIzqdaB(nodoActual, T);
    }
    Tope(&nodoActual, p);
    Pop(p);
    if (nodoActual != NODOB_NULO) {
      EtiquetaArbolB(et, nodoActual, T);
      (*EscribirElemento)(et);
      nodoActual = HijoDrchaB(nodoActual, T);
    } else {
      fin = 1;
    }
  }
  free(et);
  DestruirPila(p);
}

Ejercicio 2: Reconstrucción de Árboles Binarios

El recorrido en preorden de un determinado árbol binario es: GEAIBMCLDFKJH y en inorden: IABEGLDCFMKHJ.

• A) Dibujar el árbol binario.
• B) Dar el recorrido en postorden.
• C) Diseñar una función para obtener el recorrido en postorden dado el recorrido en preorden e inorden y escribir un programa para comprobar el resultado del apartado anterior.

Respuesta

B) El recorrido en postorden es: IBAEDLFCHJKMG.

C) El código solución al tercer apartado es el siguiente:

/* Fichero: comprobar.c */
char *preorden = "GEAIBMCLDFKJH";
char *inorden = "IABEGLDCFMKHJ";
char *postorden;

void post(char *pre, char *in, char *pos, int n) {
  int longIzqda;
  if (n != 0) {
    pos[n - 1] = pre[0];
    longIzqda = strchr(in, pre[0]) - in;
    post(pre + 1, in, pos, longIzqda);
    post(pre + 1 + longIzqda, in + 1 + longIzqda, pos + longIzqda, n - 1 - longIzqda);
  }
}

Ejercicio 5: Reflexión de un Árbol Binario

Escribir una función que realice la reflexión (espejo) de un árbol binario.

void Refleja(ArbolB T) {
  ArbolB Ti, Td;
  if (T != ARBOLB_VACIO) {
    Ti = PodarHijoIzqdaB(RaizB(T), T);
    Td = PodarHijoDrchaB(RaizB(T), T);
    Refleja(Ti);
    InsertarHijoDrchaB(RaizB(T), Ti, T);
    Refleja(Td);
    InsertarHijoIzqdaB(RaizB(T), Td, T);
  }
}

Ejercicio 6: Conteo de Nodos en un Árbol Binario

Escribir una función recursiva que encuentre el número de nodos de un árbol binario.

int numero(NodoB n, ArbolB T) {
  if (n == NODOB_NULO)
    return 0;
  else
    return 1 + numero(HijoIzqdaB(n, T), T) + numero(HijoDrchaB(n, T), T);
}

Para calcular el número de nodos de un árbol T se haría mediante la llamada: numero(RaizB(T), T).

Ejercicio 7: Altura de un Árbol Binario

Escribir una función recursiva que encuentre la altura de un árbol binario.

#define MAXIMO(a, b) ((a) < (b) ? (b) : (a))

int altura(NodoN n, ArbolB T) {
  if (n == NODOB_NULO)
    return -1;
  else
    return 1 + MAXIMO(altura(HijoIzqdaB(n, T), T), altura(HijoDrchaB(n, T), T));
}

Recorrido en Amplitud (BFS)

Consiste en ir visitando el árbol por niveles. Primero se visitan los nodos de nivel 1 (la raíz), después los nodos de nivel 2, y así sucesivamente hasta que ya no queden más.

Si se realiza el recorrido en amplitud del árbol de ejemplo, se visitarían los nodos en este orden: a, b, c, d, e, f.

En este caso, el recorrido no se realizará de forma recursiva sino iterativa, utilizando una cola como estructura de datos auxiliar. El procedimiento consiste en encolar (si no están vacíos) los subárboles izquierdo y derecho del nodo extraído de la cola, y seguir desencolando y encolando hasta que la cola esté vacía.

En la codificación que viene a continuación no se implementan las operaciones sobre colas.

void amplitud(tarbol *a) {
  tCola cola; /* Las claves de la cola serán de tipo árbol binario */
  arbol *aux;
  if (a != NULL) {
    CrearCola(cola);
    encolar(cola, a);
    while (!colavacia(cola)) {
      desencolar(cola, aux);
      visitar(aux);
      if (aux->izq != NULL) encolar(cola, aux->izq);
      if (aux->der != NULL) encolar(cola, aux->der);
    }
  }
}