6.1          Conceptos básicos.

 

Las estructuras de datos llamadas árboles basan su idea en árboles verdaderos, los cuales constan de una raíz, tallo, ramas y hojas, la única diferencia radica en que por lo regular estas estructuras se representan gráficamente de forma inversa o dicho de otra forma se rota el árbol 180°, aunque se tiene que remarcar que la representación gráfica es solo eso una modelación por lo que para términos de almacenaje y uso no importa la forma en que se visualiza.

 

En la siguiente figura se muestra un gráfico de la representación de una de estas estructuras.

Ahora se procede a describir los conceptos básicos usados en este tipo de estructuras de datos.

 

Árbol. Es una estructura enlazada no lineal de dos dimensiones y consta de un conjunto infinito de elementos (denominados nodos, etc) como: raíz, nodos, ramas, niveles y grado;

 

Raíz. Se trata del primer nodo o y no le antecede otro. De este se pueden derivar otros nodos que se podrán denominar nodos hijo.

 

Nodos .También conocido como vértice tiene un objetivo simple llevar información asociada (a una arista); se denominan hojas; nodos sin hojas se llaman nodos  internos o terminales.

 

Ramas. A unas líneas dirigidas se les llama ramas (como la de árboles de verdad).

 

Nivel. El nivel de un nodo es su distancia al raíz. El raíz tiene una distancia cero de sí misma, por lo que se dice que la raíz esta en el nivel cero (0). Los hijos en el nivel (1)y sus hijos en el nivel (2)y sus hijos de los hijos en nivel(3) y así sucesivamente.

 

Camino o ruta. Es la secuencia de nodos que se sigue para llegar de cierto nodo a otro en los que cada, nodo es adyacente al siguiente., por lo regular un camino o ruta se traza de la raíz a una hoja, pudiendo ser el origen la raíz o la hoja.

 

Altura o profundidad de un árbol: Es el nivel de la hoja del camino o ruta más largo desde la raíz más (+) uno.

 

En la siguiente figura se muestran estos conceptos dentro de una estructura de datos de árbol.

 

 

En la figura anterior se puede apreciar que a las hojas también se les llama hechos, este término se acuña para las aplicaciones dentro de la inteligencia artificial en cuanto a aplicación de reglas se refiere.

 

Si se observan las ramas se puede apreciar que dichas ramas tienen flechas que en términos generales sólo indican  que el recorrido podrían ser en esa dirección, aunque se debe aclarar que dependiendo la aplicación de la estructura del árbol puede ser bidireccional. Se puede decir que esas ramas solo indican relación directa entre esos nodos.

 

Se ha presentado los conceptos básicos de los árboles, pero aun falta el más importante ¿Para sirven?, ¿Qué pueden almacenar?, ¿Cómo se pueden implantar?

 

¿Para qué sirven?

En  lo sucesivo a las estructuras de los árboles se les llamará solo árboles.

Los árboles tienen aplicaciones en diferentes ámbitos como por ejemplo: Diseño de compiladores, sistemas expertos, sistemas evolutivos, sistemas conscientes, manejo de directorios por ejemplo Mi PC dentro de Windows. Representación de un árbol genealógico. índices de bases de datos y mucha más

 

Sin lugar tiene muchas aplicaciones, aunque su implementación no es tan usada como las base de datos tradicionales, pero actualmente existen modelos mediante los cuales un árbol puede ser representado en una lista dinámica simplemente o doblemente ligada, este modelo se presentará posteriormente.

 

¿Qué pueden almacenar?

Si los árboles se implantan en estructuras de datos dinámicas, pueden contener los que se requiera, aunque también se pueden implantar en arreglos estáticos.

 

Por ejemplo si se usa el lenguaje C y se opta por estructuras dinámicas en especial por la lista doblemente ligada, se puede definir un objetos llamado nodo de la siguiente forma:

 

class nodo

{

 public:

 //A continuacion los datos necesario para la propuesta(tonahtiu,2009) tipo de implantacion

 int padre, id;

 nodo *anterior, *siguiente;

 // A continuación los datos u objetos que se quieran almacenar en nodo

 int algun_dato;

};

 

Como se puede apreciar en el programa anterior de agrega el dato algun_dato se aquí se pueden definir cualquier tipo y cantidad de datos que se requieran o bien otros objetos. Por lo cual se puede adaptar perfectamente a las necesidades del problema.

 

 

¿Cómo se pueden implantar?

Existen tantas manera de representar estructuras de árbol como ideas surjan, por lo cual aquí solo se presenta una propuesta que considero que es sencilla y sirven para árboles de diversos niveles, grados de árbol y que puede cargarse en una lista simplemente ligada, misma que ya se ha presentado.

 

Como primer paso se presenta un esquema general del procedimiento de carga y uso de una estructura de esta naturaleza en la siguiente figura:

 

 

En el diagrama de flujo anterior se puede, apreciar 5 elementos:

 

La idea de esta propuesta consiste en que el usuario pueda capturar y esto se vaya almacenando en la lista simplemente ligada, esto es con el fin de que las operación se vayas llevando a cabo en la memoria de la computadora en lugar de el disco por cuestión de velocidad, posterior a ello es importante que dicha estructura dinámica de árbol modelada en la lista simplemente ligada puede ser guardada a disco para poder ser retomada en otra ocasión.

 

Y finalmente un módulo que permita visualizar recorridos, en esta propuesta se puede apreciar que todo se centra en el sistema de manejo de archivos este tendrá las funciones de: