APLICACIONES DE ARBOL

 

 

 

METODO TREE JAVA

 

El JTree es el componente java visual (como los botoncitos, listas, menús, etc.) que nos permite visualizar un árbol. En él podemos ver el típico árbol de datos en el que podemos abrir cada uno de los nodos para ver qué tiene dentro, cerrarlos, etc. Similar al árbol de directorios que nos muestran algunas aplicaciones para elegir un fichero.

 

 

"Modelo de datos" :

Esta clase de java puede ser cualquier clase que implemente la interface TreeModel, pero java nos ofrece ya implementada la clase DefaultTreeModel. Esta clase es la que contiene los datos que queremos visualizar en "la vista". Contiene los datos que visualizaremos en el JTree.

 

 

¿Qué datos admite el DefaultTreeModel?

Puesto que vamos a hacer un árbol, admite datos que se puedan asociar entre sí como padres e hijos. No valen datos cualesquiera. Esos datos deben implementar la interface TreeNode. Cualquier clase que implemente esta interface, tendrá métodos para interrogarle sobre quién es su padre, si tiene hijos, etc.

MutableTreeNode:

Este es igual que el anterior, pero además tiene métodos para modificar las asociaciones entre padres e hijos. Permite añadir nuevos hijos a los padres, cambiar el padre de los hijos y cualquier otro tipo de indecencia que se nos ocurra.

DefaultMutableTreeNode:

Java nuevamente nos ofrece una clase que ya implementa MutableTreeNode y por tanto tiene todos los métodos necesarios para saber quién es hijo de quién y los métodos necesarios para cambiar estas asociaciones.

 

setUserObject():

Este método nos permite guardar dentro la información que queramos. Esta información será nuestro dato real, lo que realmente nos interesa. DefaultMutableTreeNode únicamente nos ahorrará escribir el código necesario para mantener asociaciones entre padres e hijos, además de hacer de almacén de nuestro dato.

 

 

El código quedaría así

DefaultMutableTreeNode abuelo = new DefaultMutableTreeNode("abuelo");
modelo = new DefaultTreeModel(abuelo);
JTree tree = new JTree(modelo)

 

En el árbol se mostrará el resultado de llamar a toString() de nuestro "user object". Como en nuestro caso es un simple String "abuelo", el método toString() de String devuelve "abuelo" y eso es lo que se verá como raíz del árbol.

Ahora sólo nos queda ir añadiendo el resto de los datos del árbol. Lo único que tenemos que hacer es ir creando los nodos, como DefaultMutableTreeNode. A cada uno de ellos meterle el dato que queramos, bien en el constructor, bien con el método setUserObject(). En nuestro caso usaremos un simple String con el texto que queremos que se muestre. Finalmente, hay que ir asociando estos datos.

El abuelo ya lo tenemos creado, así que el código de creación de los demás nodos puede ser este

 

DefaultMutableTreeNode padre = new DefaultMutableTreeNode("padre");

      DefaultMutableTreeNode tio = new DefaultMutableTreeNode("tio");
DefaultMutableTreeNode hijo=new DefaultMutableTreeNode("hijo");
DefaultMutableTreeNode hija=new DefaultMutableTreeNode("hija");

 

El código para estas asociaciones es sencillo:

modelo.insertNodeInto(padre,abuelo,0);
modelo.insertNodeInto(tio, abuelo, 1);
modelo.insertNodeInto(hijo, padre, 0);

modelo.insertNodeInto(hija, padre, 1);

 

 

 

APLICACION CON METODOS EN ARBOL
public class Arbol { class Nodo
{
int info;
Nodo izq, der;
}
Nodo raiz;
int cant;
int altura;
public Arbol() {
raiz=null;
}
public void insertar (int info) {
if (!existe(info)) {
Nodo nuevo;
nuevo = new Nodo ();nuevo.info = info;
nuevo.izq = null;
nuevo.der = null;
if (raiz == null)
raiz = nuevo;
else {
Nodo anterior = null, reco;
reco = raiz;
while (reco != null) {
anterior = reco;
if (info < reco.info)
reco = reco.izq;
else
reco = reco.der;
}
if (info < anterior.info)
anterior.izq = nuevo;
else
anterior.der = nuevo;
}
}
}
public boolean existe(int info) {
Nodo reco=raiz;
while (reco!=null) {
if (info==reco.info)
return true;
else
if (info>reco.info)
reco=reco.der;
else
reco=reco.izq;
}
return false;
}
private void imprimirEntre (Nodo reco) {
if (reco != null) {
imprimirEntre (reco.izq);
System.out.print(reco.info + " ");
imprimirEntre (reco.der);
}
}
public void imprimirEntre () {
imprimirEntre (raiz);
System.out.println();
}

private void cantidad(Nodo reco) {
if (reco!=null) {
cant++;
cantidad(reco.izq);
cantidad(reco.der);
}
}
public int cantidad() {
cant=0;
cantidad(raiz);
return cant;
}
private void cantidadNodosHoja(Nodo reco) {
if (reco!=null) {
if (reco.izq==null && reco.der==null)
cant++;
cantidadNodosHoja(reco.izq);
cantidadNodosHoja(reco.der);
}
}
public int cantidadNodosHoja() {
cant=0;
cantidadNodosHoja(raiz);
return cant;
}
private void imprimirEntreConNivel (Nodo reco,int nivel) {
if (reco != null) {
imprimirEntreConNivel (reco.izq,nivel+1);
System.out.print(reco.info + " ("+nivel+") - ");
imprimirEntreConNivel (reco.der,nivel+1);
}
}
public void imprimirEntreConNivel () {
imprimirEntreConNivel (raiz,1);
System.out.println();
}
private void retornarAltura (Nodo reco,int nivel) {
if (reco != null) {
retornarAltura (reco.izq,nivel+1);
if (nivel>altura)
altura=nivel;
retornarAltura (reco.der,nivel+1);
}
}
public int retornarAltura () {
altura=0;
retornarAltura (raiz,1);
return altura;
}
public void mayorValorl() {
if (raiz!=null) {
Nodo reco=raiz;
while (reco.der!=null)
reco=reco.der;
System.out.println("Mayor valor del įrbol:"+reco.info);
}
}
public void borrarMenor() {
if (raiz!=null) {
if (raiz.izq==null)
raiz=raiz.der;
else {
Nodo atras=raiz;
Nodo reco=raiz.izq;
while (reco.izq!=null) {
atras=reco;
reco=reco.izq;
}
atras.izq=reco.der;
}
}
}

MAIN
    public static void main (String [] ar)
{
Arbol abo = new Arbol ();
abo.insertar (100);
abo.insertar (50);
abo.insertar (25);
abo.insertar (75);
abo.insertar (150);
System.out.println ("Impresion entreorden: ");
abo.imprimirEntre ();
System.out.println ("Cantidad de nodos del įrbol:"+abo.cantidad());
System.out.println ("Cantidad de nodos hoja:"+abo.cantidadNodosHoja());
System.out.println ("Impresion en entre orden junto al nivel del nodo.");
abo.imprimirEntreConNivel();
System.out.print ("Artura del arbol:");
System.out.println(abo.retornarAltura());
abo.mayorValorl();
abo.borrarMenor();
System.out.println("Luego de borrar el menor:");
abo.imprimirEntre ();
}
}



Unidad III ARBOL BINARIO

MI ARBOL FAMILIAR

 

 

 

Concepto:

Un árbol binario es una estructura de datos de tipo árbol en donde cada uno de los nodos del árbol puede tener 0, 1, ó 2 subárboles llamados de acuerdo a su caso como:

1. Si el nodo raíz tiene 0 relaciones se llama hoja.
2. Si el nodo raíz tiene 1 relación a la izquierda, el segundo elemento de la relación es el subárbol izquierdo.
3. Si el nodo raíz tiene 1 relación a la derecha, el segundo elemento de la relación es el subárbol derecho

Árbol General :

 

ARBOL GENERAL A BINARIO

• Enlazar los hijos de cada nodo en forma horizontal las raíces de los distintos arboles generales. 
• Relacionar los hijos de cada nodo (los hermanos en forma horizontal).
• Enlazar en forma vertical el nodo Padre con el hijo que se muestra  mas a la izquierda . Además se debe eliminar el vinculo del padre con el resto de sus hijos.
• Rotar el diagrama resultante aproximadamente 45 grados hacia la izquierda y así obtendrá un árbol binario correspondiente.

 RECORRIDOS

 

 

 

RECORRIDO INORDEN (IZQUIERDO,RAIZ,DERECHO)

Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:

1. Atraviese el sub-árbol izquierdo 

 

 

RECORRIDO PREORDEN (RAIZ,IZQUIERDO,DERECHO)

Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:

1. Visite la raíz
2. Atraviese el sub-árbol izquierdo
3. Atraviese el sub-árbol derecho 

 

RECORRIDO POSORDEN(IZQUIERDO,DERECHO,RAIZ)

 Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:

1. Atraviese el sub-árbol izquierdo
2. Atraviese el sub-árbol derecho
3. Visite la raíz

 

 

 



Unidad III ESTRUCTURAS NO LINEALES

Definicion:

Estructura de Datos No Lineales:

 

• Se caracteriza por no existir una relación de sus elementos es decir que un elemento puede estar con cero uno o mas elementos.
• Las estructuras no lineales de datos mas general son los árboles donde no existe ninguna relación de orden Predefinida.
• Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos y tablas de contenido

Clasificación (altura, número de nodos)

 

Orden: es el número potencial de hijos que puede tener cada elemento de árbol.Un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.

 

Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol.

 

Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente.

Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodode un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar dealtura de ramas. ,

 

 

Si un grafo tiene un vértice Uo que solo contiene una diferente de Uo−U1 (a sí mismo) entonces es un árbol.

Altura = 3 (el nivel mas grande)

raíz = que no tiene padre (inicial)

padre = que tiene hijo(s)

hoja = no tiene hijo(s), tiene padre

Árbol ordenado: tiene nivel, los hijos de izquierda a derecha.

n-árbol: cuando cada padre tiene a lo más n hijos

árbol binario: cada padre tiene a lo más 2 hijos

Recursividad:

La recursividad es una técnica de programación importante. Se utiliza para realizar una llamada a una función desde la misma función. Como ejemplo útil se puede presentar el cálculo de números factoriales. Él factorial de 0 es, por definición,

Por ejemplo, para calcular fib (6), puede aplicarse la definición de manera recursiva para obtener:

Fib (6) = fib (4) + fib (5) = fib (2) + fib (3) + fib (5) = fib (0) + fib (1) + fib (3) + fib (5) = 0 + 1 fib (3) + fib (5)

 

 

Como ejemplo de cadena recursiva consideremos el siguiente grupo de definiciones:

 

•  Una expresión es un término seguido por un signo mas seguido por un término, o un término solo
• Un término es un factor seguido por un asterisco seguido por un factor, o un factor solo.
• Un factor es una letra o una expresión encerrada entre paréntesis.

 

 

Longitud de Camino Interno:

Se define la longitud de camino de nodo X como el número de arcos que se deben de recorrer  para llegar desde la raíz hasta el nodo  X. Por definición la raíz tiene longitud de camino 1, sus  descendientes directos longitud de camino 2 y así sucesivamente. Considerando la siguiente figura.

La longitud de camino interno (LCI) del árbol es la suma de las longitudes de camino de todos los  nodos del árbol. Se calcula de la siguiente fórmula:

Longitud de camino externo

Para definir la longitud de camino externo de un árbol es necesario definir los conceptos de árbol extendido y nodo especial.Un árbol extendido es aquel en el que el número de hijos de cada nodo es igual al grado del árbol. Si alguno de los nodos del  árbol no cumple con esta condición entonces debe incorporarse al  mismo tantos nodos especiales como se requiera para llegar a cumplirla.

 

 

 

 

La longitud de camino externo (LCE) de un árbol es la suma de las longitudes de camino de todos 

los nodos especiales del árbol. Se calcula de la siguiente forma:

LCE= 1 ∗ 2 + 1 ∗ 3 + 11 ∗ 4 + 12 ∗ 5 = 109