Arbol trie ayuda plis java
Tengo que hacer un proyecto en java, es el siguiente:
Desarrollar un TAD (clase) en java que implemente un árbol jd, se emplea cuando la información almacenada en los nodos tiene más de una dimensión, en nuestro caso se almacenaran ristras de caracteres (alfabeto español), así las dimensiones serán todos y cada uno de los caracteres del alfabeto, y para cada ristra almacenada, el valor de cada dimensión sera la frecuencia de aparición de cada carácter. En el árbol hay dos tipos de nodos, unos internos, que discriminan para la ordenación y que almacenan el carácter empleado para discriminar y un vector de 10 enlaces, correspondiendo a las frecuencias de 0 a 9 de dicho carácter y un vector de 10 enlaces que apuntan, si es necesario, a una lista simplemente encadenada con las palabras almacenadas ( nodos de información).
Mi pregunta es la siguiente, voy a utilizar un árbol Tríe, dicho árbol Tríe esta compuesto por dos nodos, un nodo Desviación y un Nodo Información. Ambos nodos los defino de la siguiente manera:
Private class NodoDesviación extends NodoTrie {
NodoTrie enlaces[*,0,1,2,3,4,5,6,7,8,9];
NodoTrie fin;
Public NodoDesviación () {
super();
enlaces = new NodoTrie[ 10];
}
}
Private class NodoInformación extends NodoTrie {
Object elemento;
Public NodoInformación ( Object e) {
super();
elemento = e;
}
}
La duda es que no se definir un árbol Tríe, he estado buscando pero no se definir la Clase Árbol Tríe.
Desarrollar un TAD (clase) en java que implemente un árbol jd, se emplea cuando la información almacenada en los nodos tiene más de una dimensión, en nuestro caso se almacenaran ristras de caracteres (alfabeto español), así las dimensiones serán todos y cada uno de los caracteres del alfabeto, y para cada ristra almacenada, el valor de cada dimensión sera la frecuencia de aparición de cada carácter. En el árbol hay dos tipos de nodos, unos internos, que discriminan para la ordenación y que almacenan el carácter empleado para discriminar y un vector de 10 enlaces, correspondiendo a las frecuencias de 0 a 9 de dicho carácter y un vector de 10 enlaces que apuntan, si es necesario, a una lista simplemente encadenada con las palabras almacenadas ( nodos de información).
Mi pregunta es la siguiente, voy a utilizar un árbol Tríe, dicho árbol Tríe esta compuesto por dos nodos, un nodo Desviación y un Nodo Información. Ambos nodos los defino de la siguiente manera:
Private class NodoDesviación extends NodoTrie {
NodoTrie enlaces[*,0,1,2,3,4,5,6,7,8,9];
NodoTrie fin;
Public NodoDesviación () {
super();
enlaces = new NodoTrie[ 10];
}
}
Private class NodoInformación extends NodoTrie {
Object elemento;
Public NodoInformación ( Object e) {
super();
elemento = e;
}
}
La duda es que no se definir un árbol Tríe, he estado buscando pero no se definir la Clase Árbol Tríe.
1 Respuesta
Respuesta de krlosnow
1
Echa un vistazo a esta clase. De todas formas, lo que he podido ver de árboles tríe hace referencia a 26 enlaces ( las letras del alfabeto), y no 10. A no ser que lo que te interese sea guardar palabras que exclusivamente se compongan de caracteres numéricos.
Tienes razón, me he equivocado en esa línea de código, en realidad es 26 ya que lo que quiero guardar es letras del abecederario o palabras, no caracteres numéricos.
La cosa es, si por ejemplo yo tengo la palabra "ALA", y según dice el enunciado del proyecto, cuenta las veces que se repite un carácter y a la salida del nodo de información me devuelve la palabra o la clave y su dirección. Lo que no se, es como enfocar la clase Árbol, ¿me podrías poner un ejemplo en base a mi proyecto por favor?, gracias por la página que me has mandado, pero soy novato y me pierdo...
Gracias
La cosa es, si por ejemplo yo tengo la palabra "ALA", y según dice el enunciado del proyecto, cuenta las veces que se repite un carácter y a la salida del nodo de información me devuelve la palabra o la clave y su dirección. Lo que no se, es como enfocar la clase Árbol, ¿me podrías poner un ejemplo en base a mi proyecto por favor?, gracias por la página que me has mandado, pero soy novato y me pierdo...
Gracias
Lo de contar las veces que se repite un carácter no lo entiendo. No tiene nada que ver con un árbol Tríe: La clase NodoTrie que yo crearía es:
import java.util.Hashtable;
public class NodoTrie {
private String palabra;
private Hashtable<String, NodoTrie> ramas;
private String caracter;
public static final String CARACTER_FIN = "$";
private static NodoTrie nodoRaiz = null;
public static NodoTrie getNodoRaiz(){
if (nodoRaiz==null){
nodoRaiz = new NodoTrie(null);
}
return nodoRaiz;
}
public NodoTrie(String caracter){
this.palabra = null;
this.ramas = new Hashtable<String, NodoTrie>();
this.caracter = caracter;
}
}
Lo que falta por implementar son los métodos de insertaPalabra() y buscaPalabra().
La idea es que un NodoTrie contiene una palabra válida cuando la variable carácter vale CARACTER_FIN. Si no, tan solo forma parte del camino a una palabra.
Como comprenderás, tampoco me puedo dedicar a implementar toda la lógica. La idea es que si tienes que insertar la palabra "ALA", primero deberás crear la rama "A" en el nodo raíz, e insertar en esa rama un NodoTrie con el carácter "A". Después, en el nodo recién creado, tendrás que crear la rama "L", e insertar un nuevo NodoTrie. En el nuevo NodoTrie, tendrás que crear la rama "A", con otro NodoTrie. Por último, tendrás que crear la rama "$" (CARACTER_FIN) e insertar un NodoTrie, que será el que almacene la palabra. Este último NodoTrie no tendrá ramas, y almacenará el carácter "$" y la palabra.
import java.util.Hashtable;
public class NodoTrie {
private String palabra;
private Hashtable<String, NodoTrie> ramas;
private String caracter;
public static final String CARACTER_FIN = "$";
private static NodoTrie nodoRaiz = null;
public static NodoTrie getNodoRaiz(){
if (nodoRaiz==null){
nodoRaiz = new NodoTrie(null);
}
return nodoRaiz;
}
public NodoTrie(String caracter){
this.palabra = null;
this.ramas = new Hashtable<String, NodoTrie>();
this.caracter = caracter;
}
}
Lo que falta por implementar son los métodos de insertaPalabra() y buscaPalabra().
La idea es que un NodoTrie contiene una palabra válida cuando la variable carácter vale CARACTER_FIN. Si no, tan solo forma parte del camino a una palabra.
Como comprenderás, tampoco me puedo dedicar a implementar toda la lógica. La idea es que si tienes que insertar la palabra "ALA", primero deberás crear la rama "A" en el nodo raíz, e insertar en esa rama un NodoTrie con el carácter "A". Después, en el nodo recién creado, tendrás que crear la rama "L", e insertar un nuevo NodoTrie. En el nuevo NodoTrie, tendrás que crear la rama "A", con otro NodoTrie. Por último, tendrás que crear la rama "$" (CARACTER_FIN) e insertar un NodoTrie, que será el que almacene la palabra. Este último NodoTrie no tendrá ramas, y almacenará el carácter "$" y la palabra.
