Arboles En Lenguaje C

Definición y uso

Los árboles son una de las estructuras de datos no lineales más utilizada. Sirve para representar estructuras de información jerárquicas y direcciones o etiquetas de una manera organizada.

Aplicaciones de los Árboles Generales

Por ejemplo:

* organizar tablas de símbolos en compiladores

* representar tablas de decisión

* asignar bloques de memoria de tamaño variable

* ordenar

* buscar

* solucionar juegos

* probar teoremas

Los árboles permiten representar situaciones de la vida diaria como son:

* organización de una empresa

* árbol genealógico de una persona

* organización de torneos deportivos

Características y propiedades de los arboles

a) Todo árbol que no es vacío, tiene un único nodo raíz.

b) Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por el nodo Y. En este caso es común utilizar la expresión X es hijo de Y.

c) Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. En este caso es común utilizar la expresión X es padre de Y.

d) Se dice que todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.

e) Todo nodo que no tiene ramificaciones (hijos), se conoce con el nombre de terminal u hoja.

f) Todo nodo que no es raíz, ni terminal u hoja se conoce con el nombre de interior.

g) Grado es el número de descendientes directos de un determinado nodo. grado de árbol, es el máximo grado de todos los nodos del árbol.

h) Nivel es el número de arcos que deben ser recorridos para llegar a un determinado nodo. Por definición, la raíz tiene en nivel 1.

i) Altura del árbol es el máximo número de niveles de todos los nodos del árbol.

Definiremos varios conceptos. En relación con otros nodos:

Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.

Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.

En cuanto a la posición dentro del árbol:

Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.

Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.

Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.

Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos árboles se conocen también como árboles binarios.

Ejemplos:

#define ORDEN 5

struct nodo \{

int dato;

struct nodo *rama[ORDEN];

};

----------------------------------------------------------------------------------------------

#define ORDEN 5

struct nodo \{

int dato;

struct nodo *rama[ORDEN];

};

Declaracion:

typedef struct _nodo \{

int dato;

struct _nodo *rama[ORDEN];

} tipoNodo;

typedef tipoNodo *pNodo;

typedef tipoNodo *Arbol;

Recorrido:

...