BSTs en C (parte 1)

Vamos a crear un árbol binario de búsqueda en C, empezando por definir la estructura básica del nodo. Para ello, declaramos una estructura llamada nodo que contiene un valor entero y dos punteros, uno al hijo izquierdo y otro al derecho. Estos punteros apuntarán a otros nodos o serán NULL si no hay hijos. Esta definición recursiva nos permite representar el árbol completo a partir de un único nodo raíz.

typedef struct nodo {
    int valor;
    struct nodo* izquierdo;
    struct nodo* derecho;
} nodo;

En este enfoque, consideramos que un árbol es simplemente un puntero a un nodo raíz. Esto simplifica las operaciones, ya que podemos trabajar directamente con nodos para crear, insertar o destruir elementos sin necesidad de estructuras adicionales.

Para crear un nuevo nodo, implementamos una función que recibe un valor, reserva memoria dinámica para un nodo, asigna el valor y establece los punteros izquierdo y derecho a NULL:

#include <stdlib.h>

nodo* crearNodo(int valor) {
    nodo* nuevoNodo = (nodo*) malloc(sizeof(nodo));
    if (nuevoNodo == NULL) {
        // Manejo de error por falta de memoria
        return NULL;
    }
    nuevoNodo->valor = valor;
    nuevoNodo->izquierdo = NULL;
    nuevoNodo->derecho = NULL;
    return nuevoNodo;
}

Para liberar la memoria de un nodo, definimos una función que simplemente llama a free sobre el nodo recibido, asegurándonos antes de que sus punteros no apunten a nada relevante:

void destruirNodo(nodo* n) {
    if (n != NULL) {
        n->izquierdo = NULL;
        n->derecho = NULL;
        free(n);
    }
}

Al iniciar, podemos definir un árbol vacío simplemente asignando NULL a un puntero de tipo nodo*. La inserción de elementos en el árbol binario de búsqueda se realiza respetando la propiedad de que los valores menores van al subárbol izquierdo y los mayores al derecho.

La función para insertar un valor recibe un puntero al puntero del árbol, para poder modificar el árbol original cuando sea necesario. Si el árbol está vacío (NULL), se crea un nuevo nodo con el valor. Si no, se compara el valor a insertar con el valor del nodo raíz y se inserta recursivamente en el subárbol izquierdo o derecho según corresponda.

void insertar(nodo** arbol, int valor) {
    if (*arbol == NULL) {
        *arbol = crearNodo(valor);
        return;
    }
    if (valor < (*arbol)->valor) {
        insertar(&((*arbol)->izquierdo), valor);
    } else {
        insertar(&((*arbol)->derecho), valor);
    }
}

Para buscar si un valor existe en el árbol, implementamos una función que devuelve un entero que actúa como booleano: 1 si el valor está presente y 0 si no. La búsqueda también es recursiva y sigue la misma lógica que la inserción, comparando el valor buscado con el nodo actual y descendiendo por el subárbol correspondiente.

int existe(nodo* arbol, int valor) {
    if (arbol == NULL) {
        return 0;
    }
    if (arbol->valor == valor) {
        return 1;
    }
    if (valor < arbol->valor) {
        return existe(arbol->izquierdo, valor);
    } else {
        return existe(arbol->derecho, valor);
    }
}

Probamos estas funciones creando un árbol vacío y luego insertando varios valores, como 5, 10, 4, 9 y 15. Después, comprobamos la existencia de algunos valores para verificar que la búsqueda funciona correctamente.

#include <stdio.h>

void determinarExistencia(nodo* arbol, int valor) {
    if (existe(arbol, valor)) {
        printf("El nodo %d existe en el árbol.\n", valor);
    } else {
        printf("El nodo %d no existe en el árbol.\n", valor);
    }
}

int main() {
    nodo* arbol = NULL;

    insertar(&arbol, 5);
    insertar(&arbol, 10);
    insertar(&arbol, 4);
    insertar(&arbol, 9);
    insertar(&arbol, 15);

    determinarExistencia(arbol, 10);
    determinarExistencia(arbol, 3);
    determinarExistencia(arbol, 9);

    // Aquí podríamos liberar la memoria del árbol, pero lo veremos más adelante.

    return 0;
}

Este código nos permite gestionar un árbol binario de búsqueda básico en C, con creación dinámica de nodos, inserción y búsqueda de elementos. En próximas etapas, podemos implementar funciones para recorrer el árbol en preorden, inorden y postorden, lo que facilitará visualizar su estructura y trabajar con sus elementos de forma ordenada.