Arboles

Definición
Formalmente, podemos definir un árbol de la siguiente forma:

• Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja).

• Un nuevo árbol a partir de un nodo n_r y k árboles de raíces con elementos cada uno, puede construirse estableciendo una relación padre-hijo entre n_r y cada una de las raíces de los k árboles. El árbol resultante de nodos tiene como raíz el nodo n_r, los nodos son los hijos de n_r y el conjunto de nodos hoja está formado por la unión de los k conjuntos hojas iniciales. A cada uno de los árboles A_i se les denota ahora subárboles de la raíz.

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel n + 1 (a distancia n + 1 aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos típicos del árbol son preorden, postorden e inorden:

• El recorrido en preorden, también llamado orden previo consiste en recorrer en primer lugar la raíz y luego cada uno de los hijos en orden previo.
• El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A₁, luego la raíz y luego cada uno de los hijos en orden simétrico.
• El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos en orden posterior y por último la raíz.

Tipos de arboles

• Árboles Binarios
  • Árbol de búsqueda binario auto-balanceable
    • Árboles AVL
    • Árboles Rojo-Negro
    • Árbol AA
• Árboles Multicamino
• Árboles B (Arboles de búsqueda multicamino autobalanceados)
• Árbol-B+
• Árbol-B*

Las operaciones comunes en árboles son:

• • Enumerar todos los elementos.
  • Buscar un elemento.
  • Dado un nodo, listar los hijos (si los hay).
  • Borrar un elemento.
  • Eliminar un subárbol (algunas veces llamada podar).
  • Añadir un subárbol (algunas veces llamada injertar).
  • Encontrar la raíz de cualquier nodo.
  Por su parte, la representación puede realizarse de diferentes formas. Las más utilizadas son:
  
  • Representar cada nodo como una variable en el heap, con punteros a sus hijos y a su padre.
  • Representar el árbol con un array donde cada elemento es un nodo y las relaciones padre-hijo vienen dadas por la posición del nodo en el array

Recorridos

Al visitar los nodos de un árbol existen algunas maneras útiles en las que se pueden ordenar sistemáticamente los nodos de un árbol.

Los ordenamientos más importantes son llamados: preorden, post-orden y en-orden y se definen recursivamente como sigue:

Si un árbol T es nulo, entonces, la lista vacía es el listado preorden, post-orden y en-orden del árbol T.

Si T consiste de un sólo nodo n, entonces, n es el listado preorden, post-orden y en-orden del árbol T.

Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes:

• visitar el nodo raíz

• recorrer el subárbol izquierdo

• recorrer el subárbol derecho

Estas tres acciones llevadas a cabo en distinto orden proporcionan los distintos recorridos del árbol.

Recorrido en PRE-ORDEN:

• Visitar el raíz

• Recorrer el subárbol izquierdo en pre-orden

• Recorrer el subárbol derecho en pre-orden

Recorrido EN-ORDEN

• Recorrer el subárbol izquierdo en en-orden • Visitar el raíz • Recorrer el subárbol derecho en en-orden

Recorrido en POST-ORDEN

• Recorrer el subárbol izquierdo en post-orden

• Recorrer el subárbol derecho en post-orden

• Visitar el raíz

Clases de arbol

Con la clase JTree, se puede mostrar un árbol de datos. JTree realmente no contiene datos, simplemente es un vista de ellos. Aquí tienes una imagen de un árbol.

Como muestra la figura anterior, JTree muestra los datos verticalmente. Cada fila contiene exactamente un ítem de datos (llamado un nodo). Cada árbol tiene un nodo raíz (llamado Root en la figura anterior, del que descienden todos los nodos. Los nodos que no pueden tener hijos se llaman nodos leaf (hoja). En la figura anterior, el aspecto-y-comportamiento marca los nodos hojas con un círculo.
Los nodos que no sean hojas pueden  tener cualquier número de hijos, o incluso no tenerlos. En la figura anterior, el aspecto-y-comportamiento marca los nodos que no son hojas con un carpeta. Normalmente el usuario puede expandir y contraer los nodos que no son hojas -- haciendo que sus hijos sena visibles o invisibles -- pulsando sobre él. Por defecto, los nodos que no son honas empiezan contraidos.
Cuando se inicializa un árbo, se crea un ejemplar de TreeNode para cada nodo del árbol, incluyendo el raíz. Cada nodo que no tenga hijos es una hoja. Para hacer que un nodo sin hijos no sea una hoja, se llama al método setAllowsChildren(true) sobre él.