Java - implementacion de arboles

   
Vista:

implementacion de arboles

Publicado por Raidel (9 intervenciones) el 18/01/2016 22:33:20
Hola:
Quiero implemetar una clase Arbol y para eso cree una clase que implementara la interface Tree que está en el paquete sun.reflect.generics.tree. Pero resulta que esa interface no tiene ningún método definido. ¿Existe alguna otra interface que si tenga métodos definidos para árboles?¿Implemento mi clase sin tener en cuenta ninguna interfce? estoy usando NetBeans 7.3
Gracias
Valora esta pregunta
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

implementacion de arboles

Publicado por Marcelo (47 intervenciones) el 19/01/2016 02:00:01
Lo primero que estaría bueno saber es.... que tipo de árbol intentas crear?

Como sabrás hay unos cuantos tipos distintos de arboles con usos e implementaciones totalmente diversas (Árbol binario, binario de busqueda, AVL, Arbol n, etc.)

Dependiendo de lo que necesites quizás podamos orientarte mejor.

Saludos.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
2
Comentar

implementacion de arboles

Publicado por Raidel (9 intervenciones) el 19/01/2016 14:34:15
quiero implementar un árbol general, uno binario y uno binario de búsqueda
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

implementacion de arboles

Publicado por Marcelo (47 intervenciones) el 20/01/2016 12:51:22
La buena noticia es que se trata de los 3 arboles mas sencillos de implementar.... la mala notica es que vas a tener que programarlos tu mismo.

Sin embargo no te preocupes que puedo orientarte bastante.

Vamos por parte, el primero es el Arbol General( o Arbol N para algunos entendidos).

Si la memoria no me falla, el arbol General es aquel arbol que, cada nodo, puede tener tantos hijos como quieras.

La caracteristica de los nodos de este arbol es que tiene como atributo:
* Atributo de su mismo tipo que representa al primer hijo
* Atributo de su mismo tipo que representa al primer hermano
* Atributo del tipo correspondiente del dato a guardar(Aquí se puede utilizar Generics para almacenar cualquier tipo de objeto)

Por lo tanto, tu clase quedaría algo así(para no complicar el ejemplo asumiremos que nuestro árbol almacenara int):

1
2
3
4
5
public class NodoGeneral {
         private NodoGeneral primerHijo;
         private NodoGeneral primerHermano;
         private int dato;
}

La idea es que haya otra clase llamada, por ejemplo, ArbolGeneral que tenga como atributo un nodoGeneral que representa la raíz del árbol.

Ejemplo

1
2
3
4
5
public class ArbolGeneral{
         private NodoGeneral raiz;
 
         //Luego tienes que incluir en esta clase todos los métodos referente a la manipulación del árbol (Buscar, agregar, eliminar, modificar, etc.)
}

En otro comentario te explico los binarios
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
1
Comentar

implementacion de arboles

Publicado por Marcelo (47 intervenciones) el 20/01/2016 15:52:49
Me acabo de dar cuenta que erre al nombre del atributo hermamo. En realidad no es primerHermano, sino siguienteHermano

La clase quedaria

1
2
3
4
5
public class NodoGeneral {
         private NodoGeneral primerHijo;// Este atributo es utilizado para obtener el primer hijo del nodo y luego se recorren los hermanos
         private NodoGeneral siguienteHermano;// Este atributo es utilizado para lograr enganchar los hermanos del nodo
         private int dato;
}
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

implementacion de arboles

Publicado por Raidel (9 intervenciones) el 20/01/2016 15:58:38
si, ya me habia dado cuenta. Pero de todas formas lo que pienso hacer es tener en NodoGeneral una lista de hijos de ese nodo. Gracias
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

implementacion de arboles

Publicado por Marcelo (47 intervenciones) el 20/01/2016 16:24:27
Es una implementacion valida, pero tene cuidado porque se va a complicar un poco si lo recorres recursivamente (Dado que tendrías que variar la recorrida).
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

implementacion de arboles

Publicado por Marcelo (47 intervenciones) el 20/01/2016 13:25:23
Los arboles binario tiene como característica primaria que TODOS LOS NODOS TIENE COMO MÁXIMO 2 HIJOS.

Y la gran diferencia entre el árbol binario común y el de búsqueda es que el segundo esta optimizado para las búsquedas, por lo tanto, encontrar un nodo sera mucho mas rápido y fácil que en el árbol binario común.

Llevándolo a java la clase NodoBinario seria algo así (nuevamente asumamos que almacenaremos int para facilitar la idea):

1
2
3
4
5
public class NodoBinario{
          private NodoBinario hijoIzquierdo;
          private NodoBinario hijoDerecho;
          private int dato
}

Tal cual como en el árbol general, tendremos 2 clases. Una clase sera el ArbolBinario y la segunda (que perfectamente podría heredar de la primera o ambas heredar de un Binario General para reusar los atributos) ArbolBinarioBusqueda

1
2
3
4
public class ArbolBinario{
          private NodoBinario raiz;
          // Acá irían todos los nodos relacionados con el Árbol binario
}

1
2
3
4
public class ArbolBinarioBusqueda{
          private NodoBinario raiz;
          // Acá irían todos los nodos relacionados con el Árbol binario
}

Explicaciones rápidas sobre cada uno

Árbol Binario de Búsqueda (De este árbol no hay muchas variantes)
Este árbol tiene la característica que alacena los nodos con datos menores a la raíz a su izquierda mientras que los mayores a él en su derecha (en algunos casos cuando el dato es el mismo simplemente se ignora para no tener repetidos o reemplazarlo).

Por lo tanto un árbol valido podría ser el siguiente
4
3 5

Donde, como el 3 es menor que el 4, entonces debe ser almacenado a la izquierda del 4. El 5 es mayor que el 4 por lo tanto debe ser almacenado a la derecha del 4.

En caso de un árbol con muchos nodos, el algoritmo de inserción o búsqueda, deberá ir evaluando si el dato del nodo actual es mayor o menor al dato dado, para saber si continua su camino por el hijo izquierdo o derecho del nodo actual hasta que encuentre el dato o llegue hasta un nodo en null (osea que el dato no se encontró).

Árbol binario

De este Árbol puedes encontrar una cantidad bastante mayor de implementaciones dependiendo de las necesidades.

La mayor diferencia, a mi parecer, es la forma en la que se insertan los nodos, dado que podrías llegar a tener 3 variantes:

* La primera variante es indicar en el método de insertar el dato a insertar, el padre que tendrá y que hijo sera (si el derecho o izquierdo), esta no es la implementan mas popular pero se puede ver
* La segunda variante es indicar al método de insertar el dato a insertar y el padre del mismo, dejando al algoritmo decidir si lo inserta en el hijo izquierdo o derecho dependiendo de cual tenga libre
* La tercer variante y mas compleja, es indicar solo el dato a ingresar y permitir que el algoritmo de inserción vaya insertando nodos de tal forma que asegure que antes de comenzar a insertar en un nuevo nivel, haya completado los hijos de todos los nodos del nivel superior. Si tomamos el árbol binario anterior como ejemplo, hasta que el nodo 3 y 5 no tengan sus respectivos hijos no insertara un hijo a los "nietos" digamos.

Ejemplo de la tercera variante con números.

Si quisiéramos ingresar el 1, este seria hijo del 3 o del 5 dependiendo de como se implemente el algoritmo(asumamos que completamos primero el 3 y luego el 5).
Por lo tanto el hijo izquierdo del 3 sera el 1.

Luego intentamos insertar los datos 0, 6 , 7 y 8. Entonces el algoritmo asignara el 0 al hijo derecho del 3, el 6 al hijo izquierdo del 5, el 7 al hijo derecho del 5 y el 8 al Hijo izquierdo del 1 (nunca va asignar hijos al 1 sin terminar de asignarle hijos al 5).

Creo que con esto tienes bastante para empezar. A medida que vayas avanzando podemos ir profundizando en los algoritmos y las dudas que hayan.

Espero que sirva la explicación
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
1
Comentar

implementacion de arboles

Publicado por Raidel (9 intervenciones) el 20/01/2016 14:22:10
Muchas gracias. Ya estoy implementando las clases sin implemetar ninguna interface como me has recomendado.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

implementacion de arboles

Publicado por Tom (914 intervenciones) el 19/01/2016 10:17:04
Lo mejor es que uses tus propias clases, ya que en el JDK no hay nada genérico (salvo javax.swing.Tree que es una implementación bastante buena, pero en el paquete swing).
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
1
Comentar

implementacion de arboles

Publicado por Raidel (9 intervenciones) el 20/01/2016 14:25:19
Holoa. En javax.swing.Tree hay una clase JTree que debe ser a la que te refieres. Pero no hay ninguna interface. Así que me toca usar mis propias clases.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar