En este post te mostraré cómo implementar la estructura de datos de árbol binario en ANSI C en donde el dato de cada nodo o rama será una cadena.

Te enseñaré cómo agregar un struct de nodo de árbol cuyo dato es char*, elegir si el nodo va a la izquierda o derecha (comparando cadenas) , recorrer el árbol en preorden, inorden y postorden y también hacer una búsqueda en el mismo.

Me estoy basando en el tutorial de árboles binarios en C que presenté anteriormente, solo que en aquel entonces fue con un tipo de dato entero, ahora lo haré con strings.

Nota: nodo y rama serán usados como sinónimos a lo largo de este post.

Nodo o rama

Comencemos viendo el struct. Básicamente tiene un struct que apunta a dos nodos: izquierda y derecha, pero también tiene el dato de tipo cadena.

#define MAXIMA_LONGITUD_CADENA 100

struct nodoCadena
{
    // El verdadero dato
    char cadena[MAXIMA_LONGITUD_CADENA];
    // Las ramas
    struct nodoCadena *izquierda;
    struct nodoCadena *derecha;
};

En este caso tenemos apuntadores a la izquierda y derecha, que son recursivamente otros nodos. Y esos nodos a su vez pueden tener otro nodo a la izquierda o derecha.

Para solicitar memoria y agregar un nuevo nodo al árbol tenemos la siguiente función que regresa un apuntador a la rama:

struct nodoCadena *nuevoNodo(char cadena[MAXIMA_LONGITUD_CADENA])
{
    // Solicitar memoria
    size_t tamanioNodo = sizeof(struct nodoCadena);
    struct nodoCadena *nodo = (struct nodoCadena *)malloc(tamanioNodo);
    // Asignar el dato e iniciar hojas
    strcpy(nodo->cadena, cadena);
    nodo->izquierda = nodo->derecha = NULL;
    return nodo;
}

Estamos invocando a malloc para que nos dé memoria suficiente que pueda albergar un nodo, luego de eso inicializamos el nodo junto con sus respectivas ramas.

En este caso no estoy manejando el escenario de que no haya memoria, puedes hacerlo comprobando si nodo (línea 5) es NULL.

Agregar nodo

Para agregar un dato al árbol hay que indicar la raíz, después se busca el lugar óptimo para la rama dependiendo de la cadena. Como estamos trabajando con cadenas en C, si la cadena es menor o igual (lexicográficamente) la vamos a colocar a la izquierda, y si es mayor, a la derecha.

Comparamos las cadenas con strcmp, y la función queda así:

void agregar(struct nodoCadena *nodo, char *cadena)
{
    if (strcmp(cadena, nodo->cadena) > 0)
    {
        if (nodo->derecha == NULL)
        {
            nodo->derecha = nuevoNodo(cadena);
        }
        else
        {
            agregar(nodo->derecha, cadena);
        }
    }
    else
    {
        if (nodo->izquierda == NULL)
        {
            nodo->izquierda = nuevoNodo(cadena);
        }
        else
        {
            agregar(nodo->izquierda, cadena);
        }
    }
}

Recuerda que esta función utiliza la recursión, pues no se sabe cuándo habrá espacio disponible en un nodo.

Básicamente se comprueba si la cadena va a la derecha o izquierda del nodo actual, y después de decidir eso, se intenta colocar en ese lugar. En caso de que el lugar esté ocupado se invoca a la función dentro de sí misma pero ahora pasando el nodo hijo.

Llegará algún momento en que haya un espacio disponible dentro de algún lugar profundo del árbol, y ahí es en donde la función se detiene.

Recorrido del árbol

Llegamos a la parte que más me gusta: la de recorrer el árbol. Existen 3 recorridos, el que me agrada más es el inorden pues recorre los datos de manera ordenada (para este caso, estarán ordenados alfabéticamente).

Todas las funciones del recorrido de árboles en ANSI C reciben un nodo. La primera vez será la raíz, pero para las siguientes veces será una rama. Igualmente vamos a usar recursividad.

void preorden(struct nodoCadena *nodo)
{
    if (nodo != NULL)
    {
        printf("%s,", nodo->cadena);
        preorden(nodo->izquierda);
        preorden(nodo->derecha);
    }
}

void inorden(struct nodoCadena *nodo)
{
    if (nodo != NULL)
    {
        inorden(nodo->izquierda);
        printf("%s,", nodo->cadena);
        inorden(nodo->derecha);
    }
}

void postorden(struct nodoCadena *nodo)
{
    if (nodo != NULL)
    {
        postorden(nodo->izquierda);
        postorden(nodo->derecha);
        printf("%s,", nodo->cadena);
    }
}

Fíjate en que solo cambia el tiempo en el que se visita el nodo. Con visitar, aquí, me refiero a imprimir el valor. En el preorden primero visitamos, luego vamos a la izquierda y finalmente a la derecha.

Para el caso de inorden primero vamos a la izquierda, luego visitamos y finalmente vamos a la derecha.

En postorden primero vamos a la izquierda, luego visitamos y finalmente vamos a la derecha.

Búsqueda en árbol binario de C

Pasemos a la búsqueda dentro del árbol. Recuerda que la búsqueda es muy rápida pues se aplica una búsqueda binaria ya que los datos están ordenados desde que se han insertado.

Esta función de ANSI C va a regresar un apuntador al nodo en caso de que encuentre lo que se busca, o NULL en caso contrario.

struct nodoCadena *buscar(struct nodoCadena *nodo, char *cadena)
{
    if (nodo == NULL)
    {
        return NULL;
    }
    if (strcmp(cadena, nodo->cadena) == 0)
    {
        return nodo;
    }
    else if (strcmp(cadena, nodo->cadena) > 0)
    {
        return buscar(nodo->derecha, cadena);
    }
    else
    {
        return buscar(nodo->izquierda, cadena);
    }
}

Como puedes ver, la función recibe un nodo desde donde buscar, que al principio será la raíz. Luego de eso va a usar recursividad. Ya para la búsqueda lo que hace es comparar la cadena actual; en caso de que sea igual que la búsqueda regresa el nodo pues lo ha encontrado.

En caso de no encontrar lo que se busca, compara la cadena para saber si debe buscar a la derecha o a la izquierda.

Finalmente, si llega a un nodo nulo, es que no encontró el valor, así que igualmente regresa NULL.

Modo de uso

Ahora veamos una implementación de éste árbol. Recuerda que puedes adaptarlo, modificarlo, agregar más datos al struct, etcétera. Eres libre de tomar el código. En mi caso lo he usado así:

int main(int argc, char const *argv[])
{
    // Declarar raíz
    struct nodoCadena *raiz = NULL;
    // También podría ser:
    // struct nodoCadena *raiz = nuevoNodo("Dato");
    // La primera vez hay que comprobar si la raíz es NULL
    if (raiz == NULL)
    {
        raiz = nuevoNodo("Luis");
    }
    // Agregar varias cadenas
    agregar(raiz, "Marijo");
    agregar(raiz, "Dennis");
    agregar(raiz, "Taylor");
    agregar(raiz, "Guido");
    agregar(raiz, "Andrew");
    agregar(raiz, "Leon");
    agregar(raiz, "Jack");
    agregar(raiz, "Aloy");
    printf("\nInorden: \n");
    inorden(raiz);
    printf("\nPostorden: \n");
    postorden(raiz);
    printf("\nPreorden: \n");
    preorden(raiz);
    printf("\n");
    // Mostrar búsqueda
    char busqueda[MAXIMA_LONGITUD_CADENA] = "Chris";
    struct nodoCadena *apuntador = buscar(raiz, busqueda);
    if (apuntador == NULL)
    {
        printf("%s no existe en el árbol\n", busqueda);
    }
    else
    {
        printf("%s sí existe en el árbol\n", busqueda);
    }
    // Otra búsqueda con alguien que sabemos que sí existe
    char otraBusqueda[MAXIMA_LONGITUD_CADENA] = "Guido";
    apuntador = buscar(raiz, otraBusqueda);
    if (apuntador != NULL)
    {
        printf("%s sí existe en el árbol\n", otraBusqueda);
    }
    else
    {
        printf("%s sí existe en el árbol\n", otraBusqueda);
    }

    return 0;
}

Esto lo he hecho para demostrar que sin importar cómo se agreguen los datos, serán ordenados de manera alfabética. También estoy demostrando los tres recorridos y la búsqueda en el árbol.

Poniendo todo junto

El código completo queda como se ve a continuación:

// https://parzibyte.me/blog
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXIMA_LONGITUD_CADENA 100

struct nodoCadena
{
    // El verdadero dato
    char cadena[MAXIMA_LONGITUD_CADENA];
    // Las ramas
    struct nodoCadena *izquierda;
    struct nodoCadena *derecha;
};

struct nodoCadena *nuevoNodo(char cadena[MAXIMA_LONGITUD_CADENA])
{
    // Solicitar memoria
    size_t tamanioNodo = sizeof(struct nodoCadena);
    struct nodoCadena *nodo = (struct nodoCadena *)malloc(tamanioNodo);
    // Asignar el dato e iniciar hojas
    strcpy(nodo->cadena, cadena);
    nodo->izquierda = nodo->derecha = NULL;
    return nodo;
}

void agregar(struct nodoCadena *nodo, char *cadena)
{
    if (strcmp(cadena, nodo->cadena) > 0)
    {
        if (nodo->derecha == NULL)
        {
            nodo->derecha = nuevoNodo(cadena);
        }
        else
        {
            agregar(nodo->derecha, cadena);
        }
    }
    else
    {
        if (nodo->izquierda == NULL)
        {
            nodo->izquierda = nuevoNodo(cadena);
        }
        else
        {
            agregar(nodo->izquierda, cadena);
        }
    }
}

struct nodoCadena *buscar(struct nodoCadena *nodo, char *cadena)
{
    if (nodo == NULL)
    {
        return NULL;
    }
    if (strcmp(cadena, nodo->cadena) == 0)
    {
        return nodo;
    }
    else if (strcmp(cadena, nodo->cadena) > 0)
    {
        return buscar(nodo->derecha, cadena);
    }
    else
    {
        return buscar(nodo->izquierda, cadena);
    }
}
void preorden(struct nodoCadena *nodo)
{
    if (nodo != NULL)
    {
        printf("%s,", nodo->cadena);
        preorden(nodo->izquierda);
        preorden(nodo->derecha);
    }
}

void inorden(struct nodoCadena *nodo)
{
    if (nodo != NULL)
    {
        inorden(nodo->izquierda);
        printf("%s,", nodo->cadena);
        inorden(nodo->derecha);
    }
}

void postorden(struct nodoCadena *nodo)
{
    if (nodo != NULL)
    {
        postorden(nodo->izquierda);
        postorden(nodo->derecha);
        printf("%s,", nodo->cadena);
    }
}

int main(int argc, char const *argv[])
{
    // Declarar raíz
    struct nodoCadena *raiz = NULL;
    // También podría ser:
    // struct nodoCadena *raiz = nuevoNodo("Dato");
    // La primera vez hay que comprobar si la raíz es NULL
    if (raiz == NULL)
    {
        raiz = nuevoNodo("Luis");
    }
    // Agregar varias cadenas
    agregar(raiz, "Marijo");
    agregar(raiz, "Dennis");
    agregar(raiz, "Taylor");
    agregar(raiz, "Guido");
    agregar(raiz, "Andrew");
    agregar(raiz, "Leon");
    agregar(raiz, "Jack");
    agregar(raiz, "Aloy");
    printf("\nInorden: \n");
    inorden(raiz);
    printf("\nPostorden: \n");
    postorden(raiz);
    printf("\nPreorden: \n");
    preorden(raiz);
    printf("\n");
    // Mostrar búsqueda
    char busqueda[MAXIMA_LONGITUD_CADENA] = "Chris";
    struct nodoCadena *apuntador = buscar(raiz, busqueda);
    if (apuntador == NULL)
    {
        printf("%s no existe en el árbol\n", busqueda);
    }
    else
    {
        printf("%s sí existe en el árbol\n", busqueda);
    }
    // Otra búsqueda con alguien que sabemos que sí existe
    char otraBusqueda[MAXIMA_LONGITUD_CADENA] = "Guido";
    apuntador = buscar(raiz, otraBusqueda);
    if (apuntador != NULL)
    {
        printf("%s sí existe en el árbol\n", otraBusqueda);
    }
    else
    {
        printf("%s sí existe en el árbol\n", otraBusqueda);
    }
    return 0;
}

Puedes leer más sobre ANSI C en mi blog.