Grafos Y Árbol

ARBOL.
Los árboles representan las estructuras no lineales y dinámicas de datos más importantes en computación. Dinámicas porque las estructuras de árbol pueden cambiar durante la ejecución de un programa. No lineales, puesto que a cada elemento del árbol pueden seguirle varios elementos.
La definición de árbol es la siguiente: es una estructura jerárquica aplicada sobre una colección deelementos u objetos llamados nodos; uno de los cuales es conocido como raíz. Además se crea una relación o parentesco entre los nodos dando lugar a términos como padre, hijo, hermano, antecesor, sucesor, ancestro, etc.
Formalmente se define un árbol de tipo T como una estructura homogénea que es la concatenación de un elemento de tipo T junto con un número finito de árboles disjuntos, llamadossubárboles. Una forma particular de árbol puede ser la estructura vacía.

La representación gráfica de un árbol binario es la siguiente:

Los árboles tienen una gran variedad de aplicaciones. Por ejemplo, se pueden utilizar para representar fórmulas matemáticas, para organizar adecuadamente la información, para construir un árbol genealógico, en la toma de decisiones, para el análisis de circuitoseléctricos y para numerar los capítulos y secciones de un libro.
A los árboles ordenados de grado dos se les conocen como árboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de los árboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintospuntos.

En ciencias de la computación, un árbol es una estructura de datos comúnmente usada que emula la estructura de un árbol con un conjunto de nodos conectados. Cada nodo tiene cero o más nodos hijos, que están por debajo de él (en ciencias de la computación, al contrario que en la naturaleza, los árboles crecen hacia abajo, no hacia arriba), El nodo del cual un nodo es hijo es llamado su nodopadre. Un hijo tiene como máximo un padre; un nodo sin padre es llamado nodo raíz (o simplemente raíz). Los nodos sin hijos son llamados hojas.

Características y propiedades de los árboles.

Las siguientes son las características y propiedades más importantes de los árboles en general:

a) Todo árbol que no es vacío, tiene un único nodo raíz.
b) Un nodo X es descendiente directo de unnodo 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 es 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 tieneramificaciones (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 del árbol es el máximo grado de todos los nodos del árbol, es decir, el grado más alto entre todos los nodos.
h) Nivel es el número de arcos que deben serrecorridos para llegar a un determinado nodo. Por definición la raíz tiene nivel 1.
i) Altura del árbol es el máximo número de niveles de todos los nodos del árbol.
Operaciones comunes en árboles son:

* Enumerar todos los elementos
* Buscar un elemento
* Añadir un nuevo ítem en una cierta posición del árbol
* Borrar un elemento
* Eliminar una sección completa de un árbol(llamado podar);
* Añadir una sección completa a un árbol (llamado injertar);
* Encontrar la raíz de cualquier nodo

ÁRBOLES BINARIOS DE BÚSQUEDA
¿Qué son los árboles binarios de búsqueda?

Empezaremos recordando lo que son los árboles. Un árbol es una colección de nodos que puede estar vacía o no.

Si no está vacía, el árbol estará formado por un nodo raíz y cero o más subárboles que...