Arboles en C [Parte I. Definición De Arbol y Estructura del Nodo]

Deseo reanudar la escritura de mi blog con un interesante articulo sobre arboles. Ya he escrito sobre otros temas como inteligencia artificial, o algoritmos genéticos sin haberme verme visto en la necesidad de implementar directamente los conceptos explicados, pero en esta ocasión deseo explicar un sub-area de la informática: Los arboles (que derivan de la teoría de los grafos) aplicando una metodología totalmente distinta.

Para muchos el concepto de árbol es difícil de comprender, al fin y al cabo cuando se nos introduce en la programación se nos enseña a pensar linealmente, esto es una perspectiva un tanto irreal del mundo que nos rodea,¿Como representar entonces modelos de datos no secuenciales?, como por ejemplo: la información de mapas. He aquí donde la teoría de grafos hizo su aparición. Y no quiero adentrarme mucho en ella puesto que me desviaría del tema que estoy tratando, pero para fines prácticos y sencillos, un grafo es un tipo de estructura de datos no lineal.

Y un árbol, es un tipo de grafo jerarquizado,una estructura de datos dinamica.
El Árbol este compuesto por Nodos. Un nodo es la unidad sobre la que se construye un árbol, (similar a los nodos con lo que se construye una pila, cola o lista dinámica).

Veamos algunas propiedades de los nodos.

• Un nodo puede tener o no hijos.
• Un nodo sin hijos se conoce como nodo hoja.
• Cada nodo de un árbol es un sub-árbol en si mismo.

 El hecho de que un nodo sea un sub-arbol en si mismo denota las propiedades recursivas de los arboles, y sera de ahora en adelante el elemento clave para tu trabajo.

Definición de un nodo en C.

#define MAX_HIJOS 2

struct nodo_tree {
     <tipo_de_dato> info;
     struct nodo_tree *hijos[MAX_HIJOS];
} nodo;

Como podemos observar la forma mas simple de construir un nodo en C es usando una estructura (struct) ... Podemos observar las caracteristicas esenciales de un nodo.

• Posee una parte de información que puede ser un tipo de dato simple o una estructura mas compleja.
• Posee un conjunto de punteros del tipo de la propia estructura.

Podemos mejorar nuestra estructura incluyendo una definición de tipos, creando un nuevo tipo de dato llamado nodo.

#define MAX_HIJOS 2

typedef struct _tree {
     int info;
     struct _tree *hijos[MAX_HIJOS];
} tnodo;

Ahora tenemos un nuevo tipo de dato llamado tnodo, y podemos crear variables del tipo tnodo (Esto nos simplificara mucho el trabajo de ahora en adelante). La estructura interna de tnodo es muy similar a la anterior, el campo de información para fines didácticos es de tipo entero (int) y el tipo tnodo contiene 2 punteros. Esto hace que el arbol que podamos construir usando este nodo sea un arbol binario (binario por que usa una pareja de apuntadores).

En la próxima entrega veremos nuestros primeros algoritmos relacionados a los arboles.