arboles

ARBOLES
DEFINICION
Los árboles son una clase de grafos.
Una de las estructuras de datos más importantes en programación es el árbol. Pueden usarse los árboles para representar la información enuna estructura jerárquica
Desde el punto de vista conceptual, un árbol es un objeto que comienza con una raíz y se extiende en varias ramificaciones o líneas, cada una de las cuales puede extenderseen ramificaciones hasta terminar, finalmente en una hoja.
Los árboles representan las estructuras no-lineales y dinámicas de datos más importantes en computación. Dinámicas, puesto que laestructura árbol puede cambiar durante la ejecución de un programa. No- lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.
Un árbol es un grafo T = (V,E) cíclico y conexo
Dadoque un árbol no puede tener ciclos, no podrá contener ni aristas múltiples ni bucles, por lo tanto cualquier árbol debe ser un grafo simple.


PROPIEDADES
1. Existe un único paseo entre dosvértices cualesquiera de un árbol.
2. El número de vértices es mayor en uno al número de aristas de un árbol.
3. Un árbol con dos o más vértices tiene al menos dos hojas.
4. Además, los árboles tienenlas siguientes propiedades:
5. Tienen un nodo al que se le llama raíz del árbol.
6. Todos los nodos, excepto la raíz, tienen una sola línea de entrada (el nodo raíz no tiene ninguna).
7. Existeuna ruta única del nodo raíz a todos los demás nodos del árbol.
8. Si hay una ruta , entonces a „b‟ se le denomina „hijo‟ de „a‟ y es el nodo raíz de un subárbol.
TIPOS
Arboles enraizados
Enciencias computacionales los árboles tienen muchas veces vértices principales que pueden utilizarse para dar a los árboles estructuras dirigidas. En general, se puede transformar cualquier grafo nodirigido en un grafo dirigido poniéndole flechas. Si el grafo es un árbol lo que se obtiene es un árbol dirigido. Si todas las flechas parten de un solo vértice se llama árbol enraizado. [Ross, 451]...