Aportación Java México - PCJ - Arboles

Un Árbol en Java es una estructura de datos no lineal que ejemplifica claramente una organización jerárquica. Los rasgos característicos de cada elemento es que pueden tener varios sucesores llamados hijos y todos los elementos excepto uno, llamado raíz, tienen un antecesor único. Los elementos de un árbol son llamados nodos, tecnicamente cada nodo es un elemento de un solo subárbol. Los nodos de un árbol, se subdividen en niveles y en el nivel más alto se encuentra en el mencionado nodo raíz. Un árbol es una estructura jerárquica que une nodos con otros nodos a lo largo de ramas que se originan desde la raíz.
Los árboles son un término común en la informática, dado que existen múltiples ejemplos de su uso en la vida diaria como:

- Los archivos de los sistemas informáticos son árboles.
- La estructura de herencia para las clases de Java es un árbol.
- El Sistema de tiempo de ejecución en la invocación de un método durante la ejecución de un programa en Java es un árbol también.
- La clasificación de tipos de Java.
- Y la propia definición sintáctica del lenguaje de programación de Java en sí forma un árbol.

La altura de un árbol es el número de nodos que contiene, pues mide la distancia mayor del nodo a un nodo hoja en el subárbol. Es importante mencionar que un nodo hoja tiene altura cero, y que la altura de un árbol es exactamente a misma al nodo raíz.

Por otro lado, existen también los Árboles Binarios, éste es aquel que a lo mucho sólo tiene dos hijos, y hace referencia a ellos de acuerdo a su posición usando right y left, haciendo referencia al hijo derecho e hijo izquierdo respectivamente.
La definición recursiva de un Árbol Binario se basa en dos puntos; el primero indica que el árbol no tiene nodos, es decir, es un árbol vacío o tiene a lo más dos subárboles.
La altura de un árbol binario, es la longitud del camino más largo desde la raíz hacía sus hojas. De la misma forma también podemos dar la definición recursiva. Sea TN, el subárbol con nodo raíz N, y TL y TR los subárboles de N, entonces:

altura(N) = altura(TN) = { -1 si TN es vacío y si TN no es vacío entonces 1+max( altura(TL), altura(TR) )

La densidad es una medida del tamaño de un árbol (número de nodos) con respecto a la altura de éste. Los árboles con densidad alta son útiles, porque pueden "empacar" muchos nodos cerca de la raíz. Los extremos de esta medida son los árboles binarios degenerados y los árboles binarios completos.
- Un árbol degenerado tiene una sola hoja, y todos sus nodos interiores tienen un solo hijo.
- Un árbol completo con altura h, es aquel en el cual para cada nivel desde 0 hasta h-1 tiene todos los nodos posibles. Y las hojas en el nivel h están llenas de izq. a derecha.

Dado que los árboles no son estructuras lineales, no podemos accesar cada nodo por su posición. Para ello existen tres tipos de recorridos. Estos se definen de manera recursiva:

- Recorrido inorder
Si existe, recorre el subárbol izquierdo inorder
Visita el nodo raíz del árbol
Si existe, recorre el subárbol derecho inorder

- Recorrido preorder
Visita el nodo raíz
Si existe, recorre el subárbol izquierdo en preorder
Si existe, recorre el subárbol derecho en preorder

-Recorrido postorder
Si existe, recorre el subárbol izquierdo en postorder
Si existe, recorre el subárbol derecho en postorde
Visita el nodo raíz

Les adjunto la clase arboles para ver su funcionamiento, al mismo tiempo que les agrego una prueba para ver como funcionan.

AdjuntoTamaño
Arboles.pdf22.81 KB
Prueba.pdf17.8 KB
DibujaArbol.pdf23.11 KB
TNode.pdf15.09 KB

Comentarios

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.
Imagen de ArenasMx

apliación

hace un par de años construí una pequeña aplicación sobre estructura de datos incluyendo arboles y árbol avl -creo-, el único detalle es que tenia un error al borrar el nodo raíz, pero bueno puede que sirva de ejemplo...

Imagen de ezamudio

PCJ

A qué te refieres con que el Sistema de tiempo de ejecución en la invocación de un método durante la ejecución de un programa en Java es un árbol? Espero que no sea la estructura para saber qué método llamó a cuál otro para saber luego a dónde regresar el control de un hilo, porque eso es un pila…