Arbol

Un árbol es un tipo de grafo que no contiene ciclos, es decir es un grafo acíclico, pero a su vez es conexo. La diferencia entre los dos grafos es que en donde se puede notar que ninguno de los dos contiene repeticiones o ciclos.

Un árbol consta de un conjunto finito de elementos, llamados nodos y de un conjunto finito de líneas dirigidas, llamadas ramas, que conectan los nodos. El número de ramas asociado con un nodo es el grado del nodo.

Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas.

Un importante campo de esta aplicación es el análisis filogenético, que se aplica a la averiguación del parentesco entre especies, aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas.

Un árbol es un conjunto de uno o más nodos tales que:

1. Hay un nodo diseñado especialmente llamado raíz

2. Los nodos restantes se dividen en n >= 0 conjuntos distintos, T1 … Tn, tal que cada uno de estos conjuntos es un árbol. A T1 … Tn se les denomina subárboles del raíz

Si un árbol no está vació, entonces el primer nodo se llama raíz

Características y propiedades de los árboles.

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

· 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.

· Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. en ese caso es común utilizar la expresión X es padre de Y.

· Todos los nodos que son descendientes directos (hijos) de un mismo nodo (padre), son hermanos.

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

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

· Grado es el número de descendientes directos de un determinado nodo. Grado del árbol es el máximo grado de todos los nodos del árbol, es decir, el grado más alto entre todos los nodos.

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

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

RECORRIDOS DE UN ÁRBOL.

En una estructura lineal resulta trivial establecer un criterio de movimiento por la misma para acceder a los elementos, pero en un árbol esa tarea no resulta tan simple.

Existen distintos métodos útiles en que podemos sistemáticamente recorrer todos los nodos de un árbol. Los tres recorridos más importantes se denominan prefijo, infijo y posfijo, aunque hay otros recorridos como el recorrido por niveles.

Si consideramos el esquema general de un árbol tal como muestra la figura siguiente, los recorridos se definen como sigue:

En “prefijo” viaja a través del árbol binario desplegando el contenido en la raíz, después viaje a través del nodo izquierdo y después a través del nodo derecho.

El listado en prefijo es:

Si el árbol tiene un único elemento, dicho elemento es el listado en prefijo.

Si el árbol tiene más de un elemento, el listado en prefijo es listar el nodo raíz seguido del listado en prefijo de cada uno de los subárboles hijos de izquierda a derecha.

El “infijo” viaja a través del árbol binario desplegando el contenido en el nodo izquierdo después la raíz y finalmente viaja a través del nodo derecho.

El listado en infijo es:

Si el árbol tiene un único elemento, dicho elemento es el listado en infijo.

Si el árbol tiene una estructura, el listado en infijo es listar el subárbol A1 en infijo y listar el nodo raíz seguido del listado en infijo de cada uno de los subárboles hijos de izquierda a derecha restantes.

El “posfijo” viaja a través del árbol binario desplegando el contenido en el nodo izquierdo después el nodo derecho y finalmente viaja a través de la raíz.

El listado en posfijo es:

Si el árbol tiene un único elemento, dicho elemento es el listado en posfijo.

Si el árbol tiene una estructura, el listado en posfijo es listar en posfijo cada uno de los subárboles hijos de izquierda a derecha seguidos por el nodo raíz.

Tema opcional: Los bosques de árboles son un caso similar a los árboles, son acíclicos, pero no son conexos.

Tema opcional: Los Árboles Binarios son árboles ordenados de grado dos. En un árbol binario cada nodo puede tener como máximo dos subárboles y estos se distinguen entre sí como el subárbol izquierdo y el subárbol derecho, según su ubicación con respecto al nodo raíz.

Los árboles binarios tienen múltiples aplicaciones. Por ejemplo: para representar la solución de un problema, en el cual existen dos posibles alternativas; para representar un árbol genealógico, un árbol binario de búsqueda y un árbol binario que represente expresiones.

Existen tres tipos de árboles binarios

· Árboles binarios distintos: Cuando en sus estructuras la distribución de nodos y arcos son diferentes.

· Árboles binarios similares: Cuando sus estructuras son idénticas, pero la información que contienen sus nodos difiere entre sí.

· Árboles binarios equivalentes: Son aquellos que son similares y además los nodos contienen la misma información.