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.

See the gist on github.

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:

See the gist on github.

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í:

See the gist on github.

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.

See the gist on github.

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.

See the gist on github.

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í:

See the gist on github.

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:

See the gist on github.

Puedes ejecutar el código en este enlace, y leer más sobre ANSI C en mi blog.