import java.util.HashMap;
import java.util.Map;
public class No {
char caractere; // o caractere do no
Map<Character, No> subnos; // o conjunto de subnos
boolean ehTerminal = false;
boolean ehRaiz = false;
int contPalavras = 0;
// construtor: criar o objeto
public No(char caractere){ // parametro caractere
this.caractere = caractere;
// HashMap: tabela hash (char: No)
this.subnos = new HashMap<Character, No>();
}
@Override
public String toString() {
// operador ternário
return caractere + (ehRaiz?"["+contPalavras+"]":"")+
"->" + subnos.values().toString().
replace('[', ' ').replace(']', ' ');
//+ " -> [" + subnos + "]";
}
// inserir palavra
public boolean inserirPalavra(String palavra){
if (possuiPalavra(palavra)){
System.out.println("Palavra jah existe na arvore!");
return false;
}
if (palavra.length() == 0){ // se a palavra estiver vazia
this.ehTerminal = true;
return true; } // retornar true (palavra inserida)
char letra = palavra.charAt(0); // obter a primeira letra
if (palavra.length() > 1){ // se o tamanho do restante da palavra for > 1
palavra = palavra.substring(1);}// atualizar a palavra (restante dos caracteres)
else { palavra = "";} // senao deixar a palavra vazia
No no = subnos.get(letra); // obter o no a partir da letra
if (no == null){ // se o nó não existir
no = new No(letra); // criar um novo nó
subnos.put(letra, no);// adicionar o novo nó na lista de subnos do no corrente
}
boolean res = no.inserirPalavra(palavra);// inserir o restante da palavra dentro do novo no
if (ehRaiz){
contPalavras++;
}
return res;
}
// obter no
// existe palavra
public boolean possuiPalavra(String palavra){
if (palavra.length() == 0){// se a palavra tiver tamanho zero (ACHOU!)
return (this.ehTerminal);// retorna se o no eh terminal ou nao
}
char letra = palavra.charAt(0);// obter o primeiro caractere
if (palavra.length() > 1){// se a palavra tiver tamanho superior a 1
palavra = palavra.substring(1);// remover a letra lida da palavra
} else {
palavra = "";}// senao atualizar a palavra para vazio
No no = subnos.get(letra);// obter o no a partir do caractere
if (no == null){ return false;}// se o no nao existir retornar falso
else {
return no.possuiPalavra(palavra);}// senao verificar a palavra a partir do no encontrado
}
}
package br.pit.aed2.arvoredigital;
public class ProgramaPrincipal {
public static void main(String[] args) {
// link No: http://pastebin.com/4cKNbn1q
// Criar uma lista de palavras para ser inserido
String [] palavras = {"casa", "coisa", "caderno", "porta"};
// criar o nó raiz da arvore digital
No raiz = new No('*'); raiz.ehRaiz = true;
System.out.println("Exibindo a AD criada: ");
System.out.println(raiz);// exibir a arvore
// inserir uma palavra de teste
System.out.println("Inserindo uma palavra: book");
raiz.inserirPalavra("book");
System.out.println(raiz);// exibir a arvore
// inserir outra palavra de teste
System.out.println("Inserindo uma palavra: table");
raiz.inserirPalavra("table");
System.out.println(raiz);// exibir a arvore
// para cada uma das palavras na lista
System.out.println("Inserindo a lista de palavras: " + palavras);
for (String p: palavras){
raiz.inserirPalavra(p);// inserir a palavra
System.out.println(raiz);// exibir a arvore
}
// exibir a arvore final
// parte 2:
// a) adicionar um contador de palavras na árvore
// b) criar um metodo para verificar se um prefixo existe na arvore
// c) criar um metodo para listar todas as palavras que contem um prefixo
// d) criar um método para excluir uma palavra da árvore
// e) criar um método para listar todas as palavras da árvore
// f) criar um metodo para encontrar a maior e menor palavras
// g) criar um método para encontrar o nó com a maior quantidade de descendentes
// h) criar um método para exibir a quantidade total de letras
// i) criar um método para exibir as palavras da árvore de forma invertida (ex. casa -> asac)
}
}
