Tree Lattes -Árvore de palavras, bastante util para verficar se uma palavra existe. Essa árvore doi desenvolvida em Java
São 3 classe:
1- ITreeLattes - Essa é uma interface
2 - TreeLattes
3 -Link
public interface ITreeLattes {
/**
* Adiciona uma nova palavra no dicionario
* @param palavra
*/
public void adicionar(String palavra);
/**
* verifica se existe uma determinada palavra no dicionario
* @param palavra
* @return
*/
public boolean procurar(String palavra);
}
public class Link {
private char letra;//armazena uma letra
private Link[] links;//armazena vetores do tipo do no da arvore
private boolean fim;//determina o fim da palavra
/**
* Construtor
* @param letra
*/
Link(char letra)
{
this.letra = letra;
links = new Link[60];//pode possuir ate 60 nos
this.setFim(false);
}
/**
* Construtor
*/
Link()
{
this.letra = '\0';
links = new Link[260];
this.setFim(false);
}
public char getLetra(){
return letra;
}
public Link getLinks(int pos){
return links[pos];
}
public int LinkSize(){
return links.length;
}
public void setLinks(int pos, Link le){
links[pos] = le;
}
public boolean getFim() {
return fim;
}
public void setFim(boolean fim) {
this.fim = fim;
}
}
public class TreeLattes implements ITreeLattes{
private Link root;
/**
* Construtor
*/
public TreeLattes(){
root = new Link();
}
/**
* Adiciona uma nova palavra no dicionario
* @param palavra
*/
public void adicionar(String palavra){
char[] letras = palavra.toCharArray();//tranforma uma string em um vetor de char
Link aux = root; // recebe a raiz
int cont =0;
while ( cont < palavra.length()){
if (aux.getLinks(letras[cont]-97) == null){
aux.setLinks(letras[cont]-97,new Link(letras[cont]));
}
aux = aux.getLinks(letras[cont]-97);
cont++;
}
aux.setFim(true);
}
/**
* verifica se existe uma determinada palavra no dicionario
* @param palavra
* @return
*/
public boolean procurar(String palavra) {
if (root == null){//verifica se existe alguma palavra
return false;
}
else{
char[] letras = palavra.toCharArray();
int size = letras.length;
Link aux = root;
int cont = 0;
while (cont< size){
if (aux == null){
return false;
}
aux = aux.getLinks(letras[cont]-97);
cont++;
}
if (cont == size && aux == null){
return false;
}
else if (aux != null && aux.getFim() == false){
return false;
}
else{
return true;
}}}}